Fold for Binary Tree

问题:

I have to make an implementation of a Binary Tree instantiate a typeclass:

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)

All went well until I had to implement a fold for a binary tree. The issue I'm having is that I don't really know how to keep the type declaration of my function with a signature like this: (a -> b -> b) . I've implemented a fold but the function signature for my anonymous function has 1 accumulator and 2 values:

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)

How can I have the anonymous function have a signature like (a -> b -> b) ? I can' thing of any other way than calling the fold recursively on the left and right child, but this will return a value of type a.

How would I go about doing this?

回答1:

You can introduce an intermediate result:

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

and if you don't like intermediate results, you can just inline them.