オーバーレイデータ構造？

Question

私はネストされた相互の再帰を持っています データ構造, 、そして、計算高価な値をいくつかのノードに関連付けたい。実際、私は一時的にブロックをリンクしたい パンドク そのブロックで発生する単語のリストにドキュメント。

私が避けたい魅力のないオプション：

• ブロックデータ型を拡張して、単語リストを含むようにします。これは、多くの（脆弱な）ボイラープレートコードを備えた新しい拡張パンドクデータ型の作成に要約されることになります。

• ワードリストにブロックをマッピングします。ブロックが複雑すぎてキーとして効率的に機能することができないため、これは最適ではありません

私が解決策を求めている方向は、拡張ブロックを含む何らかのオーバーレイデータ構造ですが、基礎となるデータ型が触れられていないため、広範なPandocライブラリを使用できます。しかし、おそらくこれはハスケルの考え方ではありません...

Scriptum 2011-06-12を投稿します:

コメントが示すように、私はおそらく、間違った仮定に一部基づいて、マップアプローチのコストを過大評価していました。確かに：「明らかな事実ほど欺cept的なものはありません」。

とにかく、拡張可能なデータ型を作成する方法を示しているため、Hammarの答えを受け入れます。

ありがとう

Answer 1

既存のデータ型が拡張可能になるように設計されていない場合、既存のデータ型に追加を追加することはできないため、Aなどの外部構造に依存する必要があります。 Map 単語リストを各ブロックに関連付けるには。

ただし、データタイプを変更できれば、データ型の再帰を一般化することにより、拡張可能にすることができます。次のような再帰データ型があるとしましょう。

data Tree = Leaf | Fork String Tree Tree

再帰的な使用法のパラメーターを追加できます Tree:

data GenTree t = Leaf | Fork String t t

さて、オリジナルのようなプレーンな木を手に入れるには、このタイプの固定点を取ります。

data Fix a = Fix (a (Fix a))
type Tree = Fix GenTree

これで、各再帰サイトで追加データを使用してタイプを拡張できます。ラベル付きツリーのタイプを作成する方法は次のとおりです。

data Labelled t = Labelled Int (GenTree t)
type LabelledTree = Fix Labelled

strLength :: GenTree t -> Int
strLength Leaf = 0
strLength (Fork str _ _) = length str

label :: Tree -> LabelledTree
label (Fix tree) = Fix $ Labelled (strLength tree) (fmap label tree)

instance Functor GenTree where
    fmap f Leaf = Leaf
    fmap f (Fork s l r) = Fork s (f l) (f r)