8

ネストされた相互再帰的なデータ構造があり、計算コストの高い値をいくつかのノードに関連付けたいと考えています。実際、 Pandocドキュメントのブロックをそのブロックで発生する単語のリストに一時的にリンクしたいと思います。

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

  • 単語リストを含むようにBlockデータ型を拡張します。これは、多くの（壊れやすい）ボイラープレートコードを含む新しい拡張Pandocデータ型を作成することになります。

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

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

スクリプトを投稿2011-06-12：

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

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

ありがとう

4

1 に答える 1

4

拡張可能に設計されていない場合、既存のデータ型にデータを追加することはできません。そのため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)
于 2011-06-11T15:09:43.030 に答える