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 ライブラリでmanyfromControl.Applicativeが定義されている場所がわかりません。baseHackage のドキュメントが指し示している場所なので、そこにあると思いましたが、そのような運はありません。

また、Haskell でサイズ変更可能な配列ほど便利なものが見つからないため、ここで使用するデータ構造を決定するのに苦労していますが、効率の悪いツリー ベースの構造は使用したくありません。

Attoparsec をスキップして ST モナド内にパーサー全体を実装するという選択肢もありますが、最後の手段以外では避けたいと思います。

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

いくつかのアイデア:

データ構造

Ints のリストに使用する最も実用的なデータ構造は、 のようなものだと思い[Vector Int]ます。各コンポーネント ベクトルが十分に長い場合 (つまり、長さが 1k の場合)、スペースを節約できます。それをトラバースするには、独自の「リスト操作」を作成する必要がありますが、単一のVector Int.

リストの代わりにデキューを使用することも検討してください。

ステートフル解析

Parsec とは異なり、Attoparsec はユーザー状態を提供しません。runScannerただし、関数(リンク)を利用できる場合があります。

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

（また、解析された ByteString も返しますが、これは非常に大きくなるため、問題になる可能性があります。おそらく、これを行わない代替バージョンを作成できます。）

unsafeFreezeとunsafeThawを使用すると、Vector を段階的に埋めることができます。データ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]を使用することもできますDequeue (Vector Int)。

ただし、解析関数がすべての文字に対して呼び出されるため、このアプローチは遅くなると思います。

リストを単一のトークンとして表す

Parsec を使用してトークンのストリームを解析できるので、独自のトークナイザーを作成して、Parsec に AST を作成させるのはどうでしょうか。

重要なアイデアは、これらの Int の大きなシーケンスを単一のトークンとして表すことです。これにより、それらを解析する方法の自由度が大幅に高まります。

変換の据え置き

解析時に数値を Int に変換する代わりにparseManyNumbers、ByteString を返して、実際に値が必要になるまで変換を延期します。これにより、値を実際のリストとして具体化することを避けることができます。

于 2016-08-05T17:31:06.333 に答える