Обобщенная функция складывания для деревьев?

Question

Как я могу написать обобщенную функцию foldr для общих деревьев Haskell?

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

Я застрял в определении первого аргумента...

РЕДАКТИРОВАТЬ: как насчет более обобщенной версии, избегая использования списков? Больше здесь

Answer 1

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 для аналогичного вдохновения.