Generic Trie Haskellの実装

Question

ハスケルの汎用Trieの実装が必要でしたが、何も見つかりませんでした。

私はmy own functionsを実装しました（ここではキーのみ、Trieではデータは必要ありませんでした）。私はHaskellでTrieを実装しています（私は新人のhaskellerです）。

Data.Trieが見つかりましたが、キーはByteStringです。

Data.Trieは正しいオプションですか？ （そして、私はそれを使用する方法を知らない）

ありがとう!!! ：D要求によってコメントから移動

Answer 1

...私は私の頭の上からの知って

ザ・ごく一般的なトライの実装はthe list-tries packageです。それはいつも私を打ち負かすように打ち負かされましたが、ある人の「過度の複雑さ」は別の人の「フル機能のもの」です。また、パッケージは積極的に維持されているようですが、これは良いことです。

ああ、このパッケージは明示的にどこにでも書かれているわけではありません。「Patricia trie」バージョンは、単一分岐ノードのシーケンスを共通鍵プレフィックスを格納する単一ノードに圧縮するトライです。だから、鍵 "aabb"と "aabc"に対しては、 "aab"を持つノードを取得し、次に "b"と "c"を分岐させます。標準トライは常に一度に1つの要素を分岐します。

Answer 2

MemoTrieパッケージon Hackageとon GitHubを確認してください。 単純な背景については、&の美しい基礎理論については、Haskell wiki page on memoizationを参照してください。これには、ラルフ・ヒンゼの論文が1つ、私のものはsome blog postsです。

もう1つのトライ/メモ化パッケージはファンクタコンボで、on Hackageとon GitHubです。 このパッケージには、Elegant memoization with higher-order typesと他のブログ投稿に記載されているアイデアの実装が組み込まれています。

いくつかの他の関連するパッケージ：

• エドワードKmettのrepresentable-tries
• ルーク・パーマーのdata-memocombinators

Answer 3

http://hackage.haskell.org/package/TrieMapは戻って一日の私の仕事の一部でした。 は "generic"で意味しますが、TrieMapは多かれ少なかれ任意の（再帰的、偶数！）代数データ型をサポートしています。バイナリツリー、トライキーとして。