1

Haskell を使用して、ツリーの葉の総数をカウントする関数を作成しています。ツリーを次のように定義しました。

data Tree a = Leaf | Node a (Tree a) (Tree a)

これを行う関数を次のように記述します。

countL :: Tree a -> Int
countL Leaf = 1
countL (Node x tL tR) = (countL tL) + (countL tR)

これは機能しますが、fold 関数を使用して同じことを行うことで、さらに一歩進めたいと思います。私は次のようにして定義したツリーの作業折りたたみ関数を持っています:

mytFold :: (a -> b -> b -> b) -> b -> Tree a -> b
mytFold f g Leaf = g
mytFold f g (Node a xl xr) = f a (mytFold f g xl) (mytFold f g xr)

折り畳み関数を含めようとしました（これを実行して定義したヘルパー関数も使用しました：

countL' :: Tree a -> Integer
countL' Leaf = 1
countL' = mytFold leafy 0 where
        leafy tL tR = tL + tR

しかし、私はいくつかの奇妙なエラーが発生しています。誰が何が悪いのかについての洞察を持っていますか?

4

1 に答える 1

5

2つの構文/タイプの問題があります。まず、すべてのトップレベルのバインディングには同じ数の引数が必要です。

countL' Leaf = ..
countL' = ..

は無効です。1つの解決策は

countL' Leaf = ..
countL' tree = mytFold leafy 0 tree

これを実行すると、GHCは次のようなエラーを表示します

    Couldn't match expected type `Integer -> Integer'
                with actual type `Integer'
    Expected type: Integer -> Integer -> Integer -> Integer
      Actual type: Integer -> Integer -> Integer
    In the first argument of `mytFold', namely `leafy'
    In the expression: mytFold leafy 0 tree

これはmytFold、最初の引数として3つの引数の関数が必要であり、leafy2をとるだけだからです。を使用してこれを修正しleafy _ tL tR = tL + tRます。

ただし、これを実行すると、間違った答えが返されることがわかりますcountL' (Node 1 Leaf Leaf) == 0。解決策を明確にする方法は、ケースを削除し、折り目としてcountL' Leaf書き込もうとすることです。countLすなわち

countL'' = mytFold f a

どこに何があるかを決定しfますa（ヒント：すでに持っていますf == leafy == const (+)）。考えてみてくださいmytFold leafy a Leaf。

于 2012-10-19T18:34:22.317 に答える