25

xsHaskellの一般的なイディオムである差分リストは、リストを値として表すことです(xs ++)。次に、 (.)「(++)」にidなり、「」になります[]（実際、これはすべてのモノイドまたはカテゴリで機能します）。一定時間で関数を作成できるので、これを追加することで効率的にリストを作成するための優れた方法が得られます。

残念ながら、型[a] -> [a]はフォームの関数の型よりもはるかに大きくなり(xs ++)ます。リスト上のほとんどの関数は、引数の前に追加する以外のことを行います。

これを回避する1つのアプローチ（で使用される）は、スマートコンストラクターを使用しdlistて特別な型を作成することです。DList（で使用されている）別のアプローチShowSは、どこにも制約を適用せず、最良のものを期待することです。しかし、正確に正しいサイズの型を使用しながら、差分リストのすべての必要なプロパティを保持するための優れた方法はありますか？

4

1 に答える 1

25

はい！

[a]無料のモナドインスタンスとして表示できますFree ((,) a) ()。

したがって、 EdwardKmettがFreeMonadsforLessで説明したスキームを適用できます。

取得するタイプは

newtype F a = F { runF :: forall r. (() -> r) -> ((a, r) -> r) -> r }

または単に

newtype F a = F { runF :: forall r. r -> (a -> r -> r) -> r }

だから私たちのリストrunFの関数に他なりません！foldr

これはBoehm-Berarducciエンコーディングと呼ばれ、元のデータ型（リスト）と同型です。したがって、これは可能な限り小さいものです。

ネスは言う：

したがって、このタイプはまだ「幅が広い」ので、接頭辞だけでなく、g関数の引数を制約しません。

foldr私が彼の議論を正しく理解していれば、彼は、 （またはrunF）関数をととは異なるものに適用できる[]と指摘しています(:)。

foldrしかし、 -encodingは連結にのみ使用できるとは決して主張しませんでした。確かに、この名前が示すように、あなたはそれを使って任意のフォールドを計算することができます—そしてそれはウィルネスが示したものです。

真のリストタイプが1つあることを少し忘れると、より明確になる可能性があります[a]。リストタイプはたくさんあるかもしれません—例えば私は1つを定義することができます

data List a = Nil | Cons a (List a)

とは異なりますが、と同型[a]です。

上記のfoldr-encodingは、List aまたはのようなリストのさらに別のエンコーディングです[a]。[a]また、関数\l -> F (\a f -> foldr a f l)と\x -> runF [] (:)、それらの構成（どちらの順序でも）が同一であるという事実からも明らかなように、と同型です。ただし、に変換する必要はありません。を使用して直接に[a]変換できます。List\x -> runF x Nil Cons

重要な点は、一部のリストF aの関数ではない要素が含まれていないことです。また、 （明らかに）複数のリストの関数である要素が含まれていないことも重要です。foldrfoldr

したがって、含まれる要素が少なすぎたり多すぎたりすることはありません。すべてのリストを正確に表すために必要な数の要素が正確に含まれています。

これは、差分リストエンコーディングには当てはまりません。たとえば、このreverse関数はどのリストの追加操作でもありません。

于 2012-11-12T15:52:30.630 に答える