title: traversal of boolean AST in Haskell
body: <p>I am having trouble completing a task where I am to create a function that uses a generalised fold function to evaluate a boolean AST. I will show you some examples to illustrate. </p>
  
  <p>First, an example of what I want, but for an AST that sums integers: </p>
  
  <pre><code>data Expr = Val Int | Add Expr Expr deriving Show
  
  folde :: (Int -&gt; a) -&gt; (a -&gt; a -&gt; a) -&gt; Expr -&gt; a
  folde f g (Val x)   = f x
  folde f g (Add x y) = g (folde f g x) (folde f g y)
  
  eval :: Expr -&gt; Int
  eval expr = folde (\x -&gt; x) (\x y -&gt; x + y) expr
  </code></pre>
  
  <p>This works fine.</p>
  
  <p>Now for the boolean AST, and the folding function:</p>
  
  <pre><code>data Bexp = T | F | And Bexp Bexp | Or Bexp Bexp deriving (Ord, Eq)
  
  foldb :: a -&gt; a -&gt; (a -&gt; a -&gt; a) -&gt; (a -&gt; a -&gt; a) -&gt; Bexp -&gt; a
  foldb t f a o T         = t
  foldb t f a o F         = f 
  foldb t f a o (And x y) = a (foldb t f a o x) (foldb t f a o y)  
  foldb t f a o (Or x y)  = o (foldb t f a o x) (foldb t f a o y)
  </code></pre>
  
  <p>What I am having trouble with, is creating a function that does the same as the eval function does for the simple AST above, that is, using the foldb function with some lambdas to evaluate whether the <code>Bexp</code> expression is either <code>T</code> or <code>F</code>. </p>
  
  <p>I don't understand why this function doesn't work:</p>
  
  <pre><code>evb :: Bexp -&gt; Bool
  evb bexp = foldb (\_ -&gt; True) (\_ -&gt; False) (\x y -&gt; x == T &amp;&amp; y == T) (\x y -&gt; x == T || y == T) bexp
  </code></pre>
  
  <p>GHCi doesn't even wanna to compile it because of type error.</p>
  
  <p>Thanks in advance. </p>