haskell - ツリーの一般化されたfoldr関数?

Question

一般的な Haskell ツリー用の一般化された folderr 関数を作成するにはどうすればよいですか?

data (Eq a, Show a) => Tree a = Void | Node a [Tree a]
    deriving (Eq, Show)

treefold :: (Eq a, Show a) => (a -> [b] -> b) ->  b -> Tree a -> b

私は最初の引数の定義で立ち往生しています...

編集:リストの使用を避けて、より一般化されたバージョンはどうですか? 詳細はこちら

score 1 · Accepted Answer

data Tree a = Void | Node a [Tree a]
    deriving (Eq, Show)

インスタンスコンテキストは必要ありません。deriving正しいことを行います（およびを作成instance (Eq a) => Eq (Tree a)しinstance (Show a) => Show (Tree a)ます）。

あなたの型シグネチャは問題ないように見え、自然に実装可能です。

treefold :: (a -> [b] -> b) ->  b -> Tree a -> b
treefold _ k Void = k
treefold f k (Node a ts) = f a $ map (treefold f k) ts

同様のインスピレーションについては、 Data.Traversableを参照してください。

1 に答える 1