我必须实现二叉树实例化类型类:
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)
的签名?除了在左右子级上递归调用折叠之外,我可以采用任何其他方式,但这将返回 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/