5 
data Tree a = Tree a [Tree a]

空のツリーは許可されないことに注意してください。葉はサブツリーの空のリストを持つツリーです。

treeFold :: (a -> [b] -> b) -> Tree a -> b
treeFold f (Tree x s) = f x (map (treeFold f) s)

上記の情報を考えると、サブツリーに折り畳み操作を再帰的に適用し、ルートのラベルに関数を適用し、サブツリーから返される結果を適用することによって、ツリーの折り畳み関数が結果を返す方法がわかりません。

また、マップ関数に引数として渡され、適切にコンパイルおよび実行されるときに 、ツリー Fold 関数が 2 つではなく 1 つの引数しかとらない方法もわかりません。

たとえば、以下のツリー サイズ関数は、ツリーのノードをカウントします。

treeSize :: Tree a -> Int
treeSize = treeFold (\x ys -> 1 + sum ys)

したがって、treeSize treeを実行tree = Tree 4 [Tree 1 [Tree 2 [], Tree 3 []]]すると、ツリーのサイズが 4 になります。

上記のツリー サイズ関数では、ツリー フォールド関数にも 2 つではなく 1 つの引数が渡されます。また、tree fold 関数に渡される x はどこでも使用されていないため、なぜそこで必要なのですか。これを削除すると、プログラムがコンパイルされなくなり、次のエラー メッセージが表示されます。

 Couldn't match type `a' with `[[Int] -> Int]'
      `a' is a rigid type variable bound by
          the type signature for treeSize :: Tree a -> Int
          at treeFold.hs:15:1
    In the first argument of `sum', namely `ys'
    In the second argument of `(+)', namely `sum ys'
    In the expression: 1 + sum ys

どんな助けでも大歓迎です。

4

2 に答える 2

10

未使用の引数

まず、変数を未使用として明示的にマークする方法は、変数を に置き換えることです_。だからあなたは本当に欲しかった：

treeFold (\_ ys -> 1 + sum ys)

次のように記述したため、コンパイラ エラーが発生しました。

treeFold (\ys -> 1 + sum ys)

...これは同じではありません。

ひだ

treeSize次に、魔法のようなことが起こっていないことがわかるように、サンプル ツリーを手で評価します。

treeSize (Tree 1 [Tree 2 [], Tree 3 []])

-- Inline definition of 'treeSize'
= treeFold (\_ ys -> 1 + sum ys) (Tree 1 [Tree 2 [], Tree 3 []])

-- Evaluate treeFold
= (\_ ys -> 1 + sum ys) 1 (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []])

-- Apply the anonymous function
= 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []])

-- Apply the 'map' function
= 1 + sum [ treeFold (\_ ys -> 1 + sum ys) (Tree 2 [])
          , treeFold (\_ ys -> 1 + sum ys) (Tree 3 [])
          ]

-- Apply both 'treeFold' functions
= 1 + sum [ (\_ ys -> 1 + sum ys) 2 (map (treeFold (\_ ys -> 1 + sum ys)) [])
          , (\_ ys -> 1 + sum ys) 3 (map (treeFold (\_ ys -> 1 + sum ys)) [])
          ]

-- Apply the anonymous functions
= 1 + sum [ 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [])
          , 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [])
          ]

-- map f [] = []
= 1 + sum [ 1 + sum []
          , 1 + sum []
          ]

-- sum [] = 0
= 1 + sum [1 + 0, 1 + 0]
= 1 + sum [1, 1]

-- Apply 'sum'
= 1 + 2
= 3

ただし、仕組みを覚える簡単な方法がありますtreeFold。Tree各コンストラクターを、提供する関数に置き換えるだけです。

あなたが持っている場合：

Tree 1 [Tree 2 [Tree 3 [], Tree 4[]], Tree 5 [Tree 6 [], Tree 7 []]]

...そしてそれに適用treeFold fすると、次のように評価されます。

f 1 [f 2 [f 3 [], f 4 []], f 5 [f 6 [], f 7 []]]

treeSumは、次の特殊なケースf = (\_ ys -> 1 + sum ys)です。

1 + sum [1 + sum [1 + sum [], 1 + sum []], 1 + sum [1 + sum [], 1 + sum []]]

= 7

カリー

最後のポイントは、Haskell でのカリー化のしくみです。次のような関数を定義すると:

foo x y = x + y

...コンパイラは実際にそれを2つのネストされた関数に脱糖します:

foo = \x -> (\y -> x + y)

これが、Haskell で関数を 1 つの引数だけに部分的に適用できる理由です。と書くfoo 1と、次のように変換されます。

foo 1

= (\x -> (\y -> x + y)) 1

= \y -> 1 + y

つまり、1 つの引数の新しい関数を返します。

Haskell では、すべての関数が厳密に 1 つの引数を取り、新しい関数を返すことで複数の引数の関数をシミュレートします。この手法は「カリー化」として知られています。

より伝統的な主流言語の複数引数アプローチを好む場合は、関数がタプル引数を受け入れるようにすることで、それをシミュレートできます。

f (x, y) = x + y

ただし、これは Haskell の慣用句ではありません。また、パフォーマンスが向上することはありません。

于 2013-04-26T04:18:57.407 に答える
1

最初の質問は少しトリッキーです。これは再帰の問題だからです... 教師が言うように、「再帰を理解するには、再帰がどのように機能するかを学ばなければなりません」。:-P ちょっとしたアドバイス:treeFold単一のツリーまたは内部に 1 つのツリーを含むツリーを適用して、自分で (紙などで) 評価してみてください。そうすれば、何が起こっているのかを感じることができると思います... (もちろん、treeFold の引数として単純な関数を使用します。そのように、treeSize が使用します)。

treeFoldmapは、 からの関数を必要としa->b、treeFoldタイプがであるため、マップ本体で 1 つの引数のみを取得します(a -> [b] -> b) -> Tree a -> b.。そのため、2 つの引数を渡す場合map、値のみを渡すことになり、失敗が発生します。(わかりやすい例: (+) には 2 つの引数が必要です。(+1) はリスト内の各要素に適用されるため、書くmap (+1) [1,2,3]と が得られます[2,3,4] (また、(+1) にはtreeFold f上記のように明らかにもう 1 つの引数が必要です)

あなたの例 treeSize :あなたが言うとき、それは1つの引数しか取得しないというのは正しくありません。あなたは書くことができます

treeSize t = treeFold (\x ys -> 1 + sum ys) t

上記の定義の代わりに。x は、カウントには役に立たないため使用されません。ただし、2 つの引数を取る関数がtreeFold 必要なので、x を指定します。それが唯一の理由です。他の値を渡すことができます。

于 2013-04-26T01:57:23.643 に答える