9

私は Haskell でクラスを受講しています。次のように定義されたツリーの折り畳み操作を定義する必要があります。

data Tree a = Lf a | Br (Tree a) (Tree a)

「tfold」操作に関する情報や、実際に何をすべきかについての情報が見つからないようです。どんな助けでも大歓迎です。

4

4 に答える 4

11

私は常にフォールドを、コンストラクターを他の関数で体系的に置き換える方法と考えています。したがって、たとえば、自作Listタイプ ( として定義data List a = Nil | Cons a (List a)) がある場合、対応する折り畳みは次のように記述できます。

listfold nil cons Nil = nil
listfold nil cons (Cons a b) = cons a (listfold nil cons b)

または、より簡潔に言うと、次のようになります。

listfold nil cons = go where
    go Nil = nil
    go (Cons a b) = cons a (go b)

の型はlistfoldですb -> (a -> b -> b) -> List a -> b。つまり、2 つの「置換コンストラクター」が必要です。Nil値を に変換する方法を示すもの、コンストラクbターの別の置換コンストラクター (型)Consのコンストラクターの最初の値を型の値と組み合わせる方法を示すもの(なぜ? 折り畳みが既に再帰的に適用されているため! ) 新しい を生成し、最後に aに全体のシーバンを適用します - 結果は.ConsabbbList ab

あなたの場合、タイプは同様の推論によるものでtfoldなければなりません。(a -> b) -> (b -> b -> b) -> Tree a -> bうまくいけば、あなたはそこからそれを取ることができるでしょう!

于 2012-02-21T09:44:00.800 に答える
3

次の方法でツリーを表示する必要があると定義するとします。

<1 # <<2#3> # <4#5>>>

このようなツリーの折り畳みは、データ型の構成要素 (ここでは、ノードの 2 つの子ノードであり、それぞれがツリーである) に対して再帰的に実行された折り畳みの結果に対して実行される、実際に提供された操作で各分岐ノードを置き換えることを意味します。たとえば、と+、生産

(1 + ((2+3) + (4+5)))

したがって、葉の場合はそれらの内部の値を取得するだけでよく、枝の場合は 2 つの子ノードのそれぞれに折り畳みを再帰的に適用し、2 つの結果を提供された関数 (ツリーを折り畳んだ関数)と結合します。( edit: ) 葉から値を「取得」する場合、単項関数を適用してさらに変換することができます。したがって、一般に、折り畳みには2 つのユーザー提供の関数が必要です。1 つはleaf用でLf、もう 1 つは分岐ノードのツリー状の構成要素 (つまり枝) を再帰的に折り畳んだ結果を結合するためのものです。Br

ツリーのデータ型は別の方法で定義されている可能性があります。たとえば、葉が空の可能性があり、内部ノードも値を持っている場合などです。次に、空のリーフ ノードの代わりに使用するデフォルト値と、3 通りの組み合わせ操作を提供する必要があります。それでも、データ型定義の2 つのケースに対応する2 つの関数によって定義された折り畳みがあります。

ここで認識すべきもう 1 つの違いは、何をどのように折りたたむかです。つまり、ツリーを線形に折りたたむことも、線形(1+(2+(3+(4+5)))) == ((1+) . (2+) . (3+) . (4+) . (5+)) 0リストをツリーのように折りたたむこともできます((1+2)+((3+4)+5)) == (((1+2)+(3+4))+5)。結果の「式」をどのように括弧で囲むかがすべてです。もちろん、古典的な折り畳みでは、式の構造は折り畳まれるデータ構造の構造に従います。しかしバリエーションは存在します。また、結合操作は厳密ではない可能性があり、それが消費/生成する「結果」型は、複合 (リストなど) や原子 (数値など) の値を表現する可能性があることに注意してください。

(更新 2019-01-26)+結合操作が: のように連想的である場合、この再括弧化が可能です。このような連想操作と「ゼロ」要素 ( ) を組み合わせたデータ型は「モノイド」と呼ばれ、モノイドに「折り畳まれる」という概念は型クラスによってキャプチャされます。(a1+a2)+a3 == a1+(a2+a3)a+0 == 0+a == aFoldable

于 2012-02-21T21:45:30.713 に答える
1

フォールドは、操作を使用してデータ構造を単一の値に「圧縮」する操作です。開始値と実行順序があるかどうかによってバリエーションがあります（たとえば、、、、およびがあるリストの場合）。foldlしたがって、正しい実装は割り当てによって異なります。foldrfoldl1foldr1

tfold単純にすべてのリーフをその値に置き換え、すべてのブランチを特定の操作のアプリケーションに置き換える必要があると思います。いくつかの数字を使ってツリーの例を描きます。彼がのような操作を与えられた場合、彼は「崩壊」し(+)ます。この後、同じことを行う関数を簡単に作成できるはずです。

于 2012-02-21T08:35:28.223 に答える
1

リストの折りたたみは、リストを 1 つの要素に縮小することです。関数を受け取り、要素が 1 つになるまで、一度に 2 つの要素にその関数を適用します。例えば：

Prelude> foldl1 (+) [3,5,6,7]
21

...操作を1つずつ実行することで見つかります:

3 + 5 == 8
8 + 6 == 14
14 + 7 == 21

折り目が書ける

ourFold :: (a -> a -> a) -> [a] -> a
ourFold _         [a]        = a -- pattern-match for a single-element list. Our work is done.
ourFold aFunction (x0:x1:xs) = ourFold aFunction ((aFunction x0 x1):xs)

ツリー フォールドはこれを行いますが、ツリーの枝を上または下に移動します。これを行うには、最初にパターン マッチングを行って、リーフとブランチのどちらで操作しているかを確認する必要があります。

treeFold _ (Lf a)   = Lf a -- You can't do much to a one-leaf tree
treeFold f (Br a b) = -- ...

あとは宿題なので任せます。立ち往生している場合は、まず型がどうあるべきかを考えてみてください。

于 2012-02-21T03:50:03.483 に答える