効率的なリストの追加/補完関数の構成

数か月前、私はO（1）の別のリストにリストを追加したり、）結果のリスト効率的なリストの追加/補完関数の構成

残念ながら、私はこの記事のソースまたは（存在する場合）この手法/アプローチの名前を覚えていません。あなたはそれについての参考文献を持っていますか？

2012-07-04 Riccardo T.

（おそらく）最初の出現は、John Hughesの「リストの新しい表現と関数へのその応用を逆転する」（これは前に伝承であったと私は信じている） - したがって、それらは「ヒューズリスト」とも呼ばれている。 ** HackageのDListパッケージは_introspection_をサポートするAPIを持っていますが、イントロスペクションを実装するためには、正規のリストに変換してもう一度やり直す必要があります。これは非効率的です。あなたがイントロスペクションをしたいのであれば、別の構造が必要です。 –

イントロスペクションが不要な場合は十分にトレードオフです。それを指摘していただきありがとうございます。私は今使用するデータ構造を探しているわけではありませんが、私は違い/ヒューズリストの実装を勉強したいと思っていました。 –

データ構造は差分リスト（略してDList）と呼ばれます。そのデフォルト実装はin a library available on Hackageです。

前述のとおり、完全な説明はa chapter in Real World Haskell on the subjectから集めることができます。

出典

2012-07-04 13:25:35 dflemstr

よかった、ありがとう！それはまさに私が探していたものです。 'DList'のためにちょっと調べてみたら、私は実際にDon Stewartの" Real World Haskell "の第13章を探していたことがわかりました。ここでそのリストの仕組みに関する完全な説明があります：http：// book。 realworldhaskell.org/read/data-structures.html#data.dlist 将来の参考資料として、この書籍のリンクを回答に入れてください。ありがとう –

それはLYAHでも言及されています：http://learnyouahaskell.com/for-a-few-monads-more、 "Difference lists" – efie

@Riccardoオリジナルの差異リストは当然Prologで生まれ、何も構成されていません最後のコンスセルへのポインタを持ち歩く単一リンクリスト以上のものであるため、効率的に拡張することができます。 Haskellのような非バックトラッキングのPrologでは、ポインタが設定されるとそれを変更することはできません。これはC言語で簡単に実装され、別のデータフィールド* length *をデータ構造体に追加することで不変に見えるようにすることができ、その点を越えるアクセスは許可されません。これを拡張すると、新しい長さで同じ基本的なリストのコピーが作成されます。（implementers、NB！）:) –

あなたはShowSとPreludeの友達を考える必要があります。 hereを参照してください。

出典

2012-07-04 13:14:24 jberryman

効率的なリストの追加/補完関数の構成

答えて

関連する問題