title: Fold for Binary Tree
body: <p>I have to make an implementation of a Binary Tree instantiate a typeclass:</p>
  
  <pre><code>class Set s where
      add :: (Eq a) =&gt; a -&gt; s a -&gt; s a
      remove :: (Eq a) =&gt; a -&gt; s a -&gt; s a
      exists :: (Eq a) =&gt; a -&gt; s a -&gt; Bool
      fold :: (a -&gt; b -&gt; b) -&gt; s a -&gt; b -&gt; b
  
  data BTree k v = Empty | Node k v (BTree k v) (BTree k v) deriving (Show)
  </code></pre>
  
  <p>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: <code>(a -&gt; b -&gt; b)</code> . I've implemented a fold but the function signature for my anonymous function has 1 accumulator and 2 values:</p>
  
  <pre><code>foldBST :: (v -&gt; a -&gt; a -&gt; a) -&gt; a -&gt; (BTree k v) -&gt; a
  foldBST _ startval Empty = startval
  foldBST f startval (Node k v left right) = f v (foldBST f startval left) (foldBST f startval right)
  </code></pre>
  
  <p>How can I have the anonymous function have a signature like <code>(a -&gt; b -&gt; b)</code> ? 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 <code>a</code>. </p>
  
  <p>How would I go about doing this?</p>