PFP Laboratory 5

User defined data types and type classes

Consider following representation of expressions

data Expr = Num Int
          | Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Div Expr Expr
          | Var Char
	  deriving (Eq)

• Create function eval that evaluates expresions.

eval :: Expr -> Int

*Main> eval (Add (Num 1) (Num 2))
3
*Main> eval (Mul (Add (Num 1) (Num 2)) (Num 3))
9

eval :: Expr -> Int
eval (Num x) = x
eval (Add l r) =  (eval l) + (eval r)
eval (Sub l r) =  (eval l) - (eval r)
eval (Mul l r) =  (eval l) * (eval r)
eval (Div l r) =  (eval l) `div` (eval r)

• Create function showExpr that shows expression as a String.

showExpr :: Expr -> String

*Main> showExpr (Add (Num 1) (Num 2))
"1+2"
*Main> showExpr (Mul (Add (Num 1) (Num 2)) (Num 3))
"(1+2)*3"
*Main> showExpr (Mul (Add (Num 1) (Mul (Num 2) (Var 'x'))) (Mul (Num 3) (Var 'x')))
"(1+2*x)*3*x"
*Main> showExpr (Mul (Num 2) (Mul (Var 'x') (Var 'x')))                            
"2*x*x"

showExpr :: Expr -> String
showExpr expr = showExpr' expr NoOp

data Operation = Hi | HiDiv | Lo | LoSub | NoOp deriving (Eq)

showExpr' :: Expr -> Operation -> String
showExpr' (Num x) _ = show x
showExpr' (Var x) _ =  [x]
showExpr' (Add l r) op = let
  x = showExpr' l Lo ++"+"++showExpr' r Lo
  in if op == Hi || op == HiDiv || op==LoSub 
     then "(" ++ x ++")"
     else x
showExpr' (Sub l r) op = let
  x = showExpr' l Lo ++"-"++showExpr' r LoSub
  in if op == Hi || op == HiDiv || op==LoSub 
     then "(" ++ x ++")"
     else x     
showExpr' (Mul l r) op = let
  x = showExpr' l Hi ++"*"++showExpr' r Hi
  in if op == HiDiv
     then "(" ++ x ++")"
     else x
showExpr' (Div l r) op = let
  x = showExpr' l Hi ++"/"++showExpr' r HiDiv
  in if op == HiDiv
     then "(" ++ x ++")"
     else x

• Extend class Show to be usable with our expressions.

*Main> Add (Num 1) (Num 2)
"1+2"
*Main> Mul (Add (Num 1) (Num 2)) (Num 3)
"(1+2)*3"
*Main> Mul (Add (Num 1) (Mul (Num 2) (Var 'x'))) (Mul (Num 3) (Var 'x'))
"(1+2*x)*3*x"
*Main> Mul (Num 2) (Mul (Var 'x') (Var 'x'))           
"2*x*x"

instance (Show Expr) where
  show = showExpr

• Create function derivation representing symbolic derivation of a given expression.

deriv :: Expr-> Char -> Expr

*Main> deriv (Add (Num 1) (Num 2)) 'x'
0+0
*Main> deriv (Mul (Num 2) (Mul (Var 'x') (Var 'x'))) 'x'
0*x*x+2*(1*x+x*1)
*Main> deriv (Mul (Num 2) (Mul (Var 'x') (Var 'x'))) 'x'
0*x*x+2*(1*x+x*1)

deriv :: Expr-> Char -> Expr
deriv (Num _) _ = (Num 0)     
deriv (Var x) y | x==y = (Num 1)
                | otherwise = (Num 0)
deriv (Add l r) x = Add (deriv l x) (deriv r x)                
deriv (Sub l r) x = Sub (deriv l x) (deriv r x)
deriv (Mul l r) x = Add (Mul (deriv l x) r) (Mul l (deriv r x))
deriv (Div l r) x = 
   Div
    (Sub (Mul (deriv l x) r) (Mul l (deriv r x)))
    (Mul r r)

Binary Trees

• Create a data type Tree that defines binary tree where values are stored in leaves and also in branches.

data Tree a = Leaf a 
            | Branch a (Tree a) (Tree a) deriving (Show)

• Prepare an example of a binary tree.

testTree1 :: Tree Int            
testTree1 = Branch 12 (Branch 23 (Leaf 34) (Leaf 45)) (Leaf 55)

testTree2 :: Tree Char            
testTree2 = Branch 'a' (Branch 'b' (Leaf 'c') (Leaf 'd')) (Leaf 'e')

• Create a function that sums all values stored in the tree.

sum' :: Tree Int -> Int

sum' :: Tree Int -> Int
sum' (Leaf x) = x
sum' (Branch x l r) = sum' l + x + sum' r

• Create a function that extracts all values from the tree into an list.

toList :: Tree a -> [a]

toList :: Tree a -> [a]
toList (Leaf x) = [x]
toList (Branch x l r) = toList l ++ [x] ++ toList r

• One possibility how to represent a tree in a textual form is a(b(d,e),c(e,f(g,h))). Create functions that are able to read and store a tree in such a notation.

toString :: Show a => Tree a -> String
fromString :: Read a => String -> Tree a

toString :: Show a => Tree a -> String
toString (Leaf x) = show x
toString (Branch x l r) = show x ++ "(" ++ (toString l) ++ "," ++ (toString r) ++ ")"

fromString :: Read a => String -> Tree a
fromString inp = fst (fromString' inp) where
  fromString' :: Read a => String -> (Tree a,String)
  fromString' inp = 
    let
      before = takeWhile (\x ->  x /='(' &&  x /=',' &&  x/=')') inp 
      after = dropWhile (\x ->  x /='(' &&  x /=',' && x/=')') inp
      value = read before
    in if null after || head after /= '(' then (Leaf value, after) else 
        let
          (l,after') = fromString' (tail after)
          (r,after'') = fromString' (tail after') 
        in (Branch value l r, tail after'')