CODEWITHSUNDEEP
haskellabstract-syntax-tree
clickedok
clickedok

Reputation: 47

traversal of boolean AST in Haskell

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.

First, an example of what I want, but for an AST that sums integers: 

data Expr = Val Int | Add Expr Expr deriving Show

folde :: (Int -> a) -> (a -> a -> a) -> Expr -> 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 -> Int
eval expr = folde (\x -> x) (\x y -> x + y) expr

This works fine.

Now for the boolean AST, and the folding function:

data Bexp = T | F | And Bexp Bexp | Or Bexp Bexp deriving (Ord, Eq)

foldb :: a -> a -> (a -> a -> a) -> (a -> a -> a) -> Bexp -> 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)

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 Bexp expression is either T or F.

I don't understand why this function doesn't work:

evb :: Bexp -> Bool
evb bexp = foldb (\_ -> True) (\_ -> False) (\x y -> x == T && y == T) (\x y -> x == T || y == T) bexp

GHCi doesn't even wanna to compile it because of type error.

Thanks in advance.

Upvotes: 1

Views: 291

Answers (2)

chi
chi

Reputation: 116174

If we want to use foldb to produce a Bool at the very end, we need to choose a = Bool in its type. So, we are now using

foldb :: Bool 
      -> Bool
      -> (Bool -> Bool -> Bool)
      -> (Bool -> Bool -> Bool)
      -> Bexp
      -> Bool

Hence, foldb (\_->True) (\_->False) ... is wrong since the first two arguments must be booleans, not functions. We need something like foldb True False .... The next two parameters must be boolean binary operators like \x y -> x && y, which can be written as (&&) for short.

We finally get:

evb :: Bexp -> Bool
evb bexp = foldb True False (&&) (||)

Upvotes: 1

Pawan Kumar
Pawan Kumar

Reputation: 1543

The code does't compile for few reasons.

-- Observe type signatures.
foldb :: a -> a -> (a -> a -> a) -> (a -> a -> a) -> Bexp -> a
evb bexp = foldb (\_ -> True) (\_ -> False) (\x y -> x == T && y == T) (\x y -> x == T || y == T) bexp

If foldb takes its first argument as a Function x -> Bool then from the type signature of foldb a is of type function but observe this (\x y -> x == T && y == T) here you used a as Bexp, which don't match at all.

a = Bexp from (\x y -> x == T && y == T)

a = x -> Bool from (\_ -> True)

And also the return type of evb is Bool, but from your argument passing to foldb a can be 2 things & the compiler is confused to pick the right type.

Upvotes: 3

Related Questions