66

単一リンクリストを考えてみましょう。それは何かのように見えます

data List x = Node x (List x) | End

のような折りたたみ関数を定義するのは自然なことです。

reduce :: (x -> y -> y) -> y -> List x -> y

ある意味で、 everyを に、everyをにreduce f x0置き換えます。これは、プレリュードがフォールドと呼んでいるものです。NodefEndx0

次に、単純な二分木を考えます。

data Tree x = Leaf x | Branch (Tree x) (Tree x)

のような関数を定義することも同様に自然です。

reduce :: (y -> y -> y) -> (x -> y) -> Tree x -> y

この削減にはまったく異なる特徴があることに注意してください。リストベースのものは本質的にシーケンシャルですが、この新しいツリーベースのものは、より分割統治の感覚があります。parそこにいくつかのコンビネータを投げることさえ想像できます。（リストバージョンのどこにそんなものを入れますか？）

私の質問: この機能はまだ「折り畳み」として分類されていますか、それとも別のものですか? （もしそうなら、それは何ですか？）

基本的に、誰かが折り畳みについて話すときはいつでも、本質的にシーケンシャルな折り畳みリストについて話します。「シーケンシャル」が折り畳みの定義の一部なのか、それともこれが最も一般的に使用される折り畳みの例の単なる偶然の特性なのか、疑問に思っています。

4

4 に答える 4

39

折り畳みは、すべてのコンストラクターを関数に置き換えます。

たとえば、 everyをandにfoldr cons nil置き換えます。(:)cons[]nil

foldr cons nil ((:) 1 ((:) 2 [])) = cons 1 (cons 2 nil)

ツリーの場合、 everyとeveryを次のようにfoldTree branch leaf置き換えます。BranchbranchLeafleaf

foldTree branch leaf (Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3))
    = branch (branch (leaf 1) (leaf 2)) (leaf 2)

これが、すべての折り畳みがコンストラクターとまったく同じ型を持つ引数を受け入れる理由です。

foldr :: (a -> list -> list) -> list -> [a] -> list

foldTree :: (tree -> tree -> tree) -> (a -> tree) -> Tree a -> tree
于 2013-05-08T04:34:20.253 に答える