haskell - 折叠二叉树

我必须使二叉树的实现实例化一个类型类:

class Set s where
    add :: (Eq a) => a -> s a -> s a
    remove :: (Eq a) => a -> s a -> s a
    exists :: (Eq a) => a -> s a -> Bool
    fold :: (a -> b -> b) -> s a -> b -> b

data BTree k v = Empty | Node k v (BTree k v) (BTree k v) deriving (Show)

一切都很顺利，直到我不得不为二叉树实现折叠。我遇到的问题是我真的不知道如何使用这样的签名来保留我的函数的类型声明: (a -> b -> b) 。我已经实现了一个折叠，但我的匿名函数的函数签名有 1 个累加器和 2 个值:

foldBST :: (v -> a -> a -> a) -> a -> (BTree k v) -> a
foldBST _ startval Empty = startval
foldBST f startval (Node k v left right) = f v (foldBST f startval left) (foldBST f startval right)

我怎样才能让匿名函数具有像 (a -> b -> b) 这样的签名？除了在左右 child 上递归调用折叠之外，我不能以任何其他方式进行处理，但这将返回 a 类型的值。

我该怎么做呢？

最佳答案

你可以引入一个中间结果:

foldBST f startval (Node k v left right) = f v i
  where i = foldBST f j left
        j = foldBST f startval right

如果你不喜欢中间结果，你可以内联它们。

关于haskell - 折叠二叉树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19566101/