Michael Saelee

March 6, 2019

```
data List a = Cons a (List a) | Empty deriving Show
head' :: List a -> a
head' Empty = error "Empty list"
head' (Cons x _) = x
tail' :: List a -> List a
tail' Empty = error "Empty list"
tail' (Cons _ xs) = xs
takel :: Int -> List a -> List a
takel 0 _ = Empty
takel n (Cons x xs) = Cons x $ takel (n-1) xs
repeatl :: a -> List a
repeatl x = Cons x $ repeatl x
mapl :: (a -> b) -> List a -> List b
mapl _ Empty = Empty
mapl f (Cons x xs) = Cons (f x) (mapl f xs)
foldrl :: (a -> b -> b) -> b -> List a -> b
foldrl f z Empty = z
foldrl f z (Cons x xs) = f x $ foldrl f z xs
suml :: Num a => List a -> a
suml = foldrl (+) 0
```

```
data BinTree a = Node (BinTree a) a (BinTree a) | Leaf a
deriving Show
eTree :: BinTree Char
eTree = Node (Node (Leaf '3') '+' (Leaf '5')) '*' (Leaf '9')
treeElem :: Eq a => a -> BinTree a -> Bool
treeElem x (Leaf y) = x == y
treeElem x (Node l y r) = x == y || treeElem x l || treeElem x r
flatten :: BinTree a -> [a]
flatten (Leaf x) = [x]
flatten (Node l x r) = flatten l ++ [x] ++ flatten r
infTree :: BinTree Integer
infTree = t 1
where t n = Node (t (n*2)) n (t (n*2+1))
prune :: Int -> BinTree a -> BinTree a
prune 1 (Node _ x _) = Leaf x
prune n (Node l x r) = Node (prune (n-1) l) x (prune (n-1) r)
mapT :: (a -> b) -> BinTree a -> BinTree b
mapT f (Leaf x) = Leaf $ f x
mapT f (Node l x r) = Node (mapT f l) (f x) (mapT f r)
foldrT :: (a -> b -> b) -> b -> BinTree a -> b
foldrT f b (Leaf x) = f x b
foldrT f b (Node l x r) = let b' = foldrT f b r
b'' = f x b'
in foldrT f b'' l
```