1 
{-# LANGUAGE OverloadedStrings #-}

import Data.Attoparsec.Text
import Control.Applicative(many)
import Data.Word

parseManyNumbers :: Parser [Int] -- I'd like many to return a Vector instead
parseManyNumbers = many (decimal <* skipSpace)

main :: IO ()
main = print $ parseOnly parseManyNumbers "131 45 68 214"

上面只是一个例子，但是我需要在 Haskell 中解析大量的原始值，并且需要使用数组而不是列表。这在F# 的 Fparsec中是可能的，所以我已经研究了 Attoparsec 的源代码，但我想不出办法。事实上，我无法弄清楚Haskell 库中many从哪里Control.Applicative定义的。base我认为它会在那里，因为那是关于 Hackage 的文档指向的地方，但没有这样的运气。

另外，我在决定在这里使用什么数据结构时遇到了麻烦，因为我在 Haskell 中找不到像可调整大小的数组那样方便的东西，但我宁愿不使用效率低下的基于树的结构。

我的一个选择是跳过 Attoparsec 并在 ST monad 中实现整个解析器，但我宁愿避免它，除非作为最后的手段。

4

3 回答 3

2

Haskell 中有一个可增长的向量实现，它基于伟大的 AMT 算法：“persistent-vector”。不幸的是，到目前为止，该图书馆在社区中并不为人所知。然而，为了让您了解算法的性能，我会说它是驱动 Scala 和 Clojure 中标准向量实现的算法。

我建议您在列表专用实现的影响下围绕该数据结构实现解析器。这里的功能是，顺便说一句：

-- | One or more.
some :: f a -> f [a]
some v = some_v
  where
    many_v = some_v <|> pure []
    some_v = (fmap (:) v) <*> many_v

-- | Zero or more.
many :: f a -> f [a]
many v = many_v
  where
    many_v = some_v <|> pure []
    some_v = (fmap (:) v) <*> many_v
于 2016-08-05T19:22:31.853 回答
1

Vectors 是数组，在引擎盖下。数组的棘手之处在于它们是固定长度的。您预先分配了一个特定长度的数组，扩展它的唯一方法是将元素复制到一个更大的数组中。

这使得链表更擅长表示可变长度序列。（这也是为什么命令式语言中的列表实现通过分配具有额外空间的数组并仅在空间用完时才复制来分摊复制成本的原因。）如果您事先不知道将有多少元素，那么最好的选择是使用一个列表（如果需要，也可以将列表复制到Vector之后使用）。fromList这就是many返回列表的原因：它会尽可能多地运行解析器，而事先不知道会有多少。

另一方面，如果您碰巧知道要解析多少个数字，那么 aVector可能会更有效。也许你知道总是有数字的先验n，或者协议可能在序列开始之前指定会有多少数字。然后您可以使用它replicateM来有效地分配和填充向量。

于 2016-08-05T17:00:41.997 回答
1

一些想法：

数据结构

我认为用于 Ints 列表的最实用的数据结构类似于[Vector Int]. 如果每个分量向量足够长（即长度为 1k），您将获得良好的空间经济性。您必须编写自己的“列表操作”来遍历它，但您将避免重新复制您必须执行的数据以在单个Vector Int.

还可以考虑使用Dequeue而不是列表。

状态解析

与 Parsec 不同，Attoparsec 不提供用户状态。但是，您也许可以使用该runScanner功能（链接）：

runScanner :: s -> (s -> Word8 -> Maybe s) -> Parser (ByteString, s)

（它还返回已解析的 ByteString，在您的情况下可能会出现问题，因为它会非常大。也许您可以编写一个不这样做的替代版本。）

使用unsafeFreeze和unsafeThaw可以增量填充向量。您的s数据结构可能类似于：

data MyState = MyState 
             { inNumber   :: Bool           -- True if seen a digit
             , val        :: Int            -- value of int being parsed
             , vecs       :: [ Vector Int ] -- past parsed vectors 
             , v          :: Vector Int     -- current vector we are filling
             , vsize      :: Int            -- number of items filled in current vector
             }

也许[Vector Int]你使用 a 而不是 a Dequeue (Vector Int)。

但是，我想这种方法会很慢，因为您的解析函数将为每个字符调用。

将列表表示为单个标记

Parsec 可用于解析标记流，那么编写自己的标记器并让 Parsec 创建 AST 怎么样。

关键思想是将这些大型 Int 序列表示为单个标记。这为您解析它们的方式提供了更多的自由度。

延迟转换

无需在解析时将数字转换为 Ints，只需parseManyNumbers返回一个 ByteString 并将转换推迟到您真正需要这些值。这使您可以避免将值具体化为实际列表。

于 2016-08-05T17:31:06.333 回答