Week 9: Notes

This week we studied more Haskell topics:

• type synonyms

• folds

• datatypes

• derived instances

• recursive data structures

You can review these topics in chapters 6 and 8 of the Learn You a Haskell book.

foldr

foldr :: (b → a → a) → a → [b] → a

The function passed to foldr takes two arguments: a list element and an accumulator. The accumulator is the second argument: it comes from the right, as you can see in the examples below. The accumulator is combined with the last list element.

foldr f a [x₁, x₂, x₃, x₄, …, x_n] = f x₁ (f x₂ (f x₃ (f x₄ (… (f x_n a) …)))

foldr (+) 0 [2, 4, 6, 8, …, 20] = 2 + (4 + (6 + (8 + … (20 + 0) … )))

foldr (:) [] [2, 4, 6, 8, …, 20] = 2 : 4 : 6 : 8 : … : 20 : []

foldr captures the pattern of recursion that occurs when we write functions directly recursively. For example, instead of

sum :: Num a => [a] -> a
sum [] = 0
sum (x : xs) = x + sum xs

we may write

sum :: Num a => [a] -> a
sum = foldr (+) 0

foldl

foldl :: (a → b  → a) → a → [b] → a

The function passed to foldl takes two arguments: an accumulator and a list element. The accumulator is the first argument: it comes from the left, as you can see in the examples below. The accumulator is combined with the first list element.

foldl f a [x₁, x₂, x₃, x₄, …, x_n] = f (… (f (f (f a x₁) x₂) x₃) … x_n)

foldl (+) 0 [2, 4, 6, 8, …, 20] = (… ((((0 + 2) + 4) + 6) + 8) … + 20)

foldl captures the pattern of recursion that occurs when we write functions using a helper function with an extra accumulator argument. For example, instead of

rev :: [a] -> [a]
rev list =
    let f [] a = a
        f (x : xs) a = f xs (x : a)
    in f list []

we may write

rev :: [a] -> [a]
rev = foldl (\a v -> v : a) []

tutorial

Here are some exercises we solved in the tutorial.

mapping and filtering

Write map and filter using foldl and/or foldr.

map :: (a -> b) -> [a] -> [b]
map f = foldr (\x a -> f x : a) []

filter :: (a -> Bool) -> [a] -> [a]
filter f = foldr (\x a -> if f x then x : a else a) []

tree values

Write a function treeVals that takes a binary search tree and returns a list of all its values in order.

This direct implementation runs in O(N^2) in the worst case:

treeVals :: Ord a => Tree a -> [a]
treeVals Nil = []
treeVals (Node left x right) = treeVals left ++ [x] ++ treeVals right

This version uses a helper function with an extra accumulator argument, and runs in O(N):

treeVals :: Ord a => Tree a -> [a]
treeVals tree =
    -- (f tree acc) will find all values in the given tree and _prepend_ them
    -- to the given accumulator
    let f :: Tree a -> [a] -> [a]
        f Nil acc = acc
        f (Node left x right) acc =
            let rlist = f right acc  -- values in the right subtree, prepended to acc
            in f left (x : rlist)
    in f tree []

algebraic expressions

Design a data type Exp that can represent any arithmetic expression involving integer constants, named variables, and the +, - and * operators.

data Op = Plus | Minus | Times

data Expr = Const Int | Var String | OpExpr Expr Op Expr

Write a function that evaluates an expression given an environment, which is an association list that holds the variables of the variables in the expression.

opfun :: Op -> (Int -> Int -> Int)
opfun Plus = (+)
opfun Minus = (-)
opfun Times = (*)

eval :: Expr -> [(String, Int)] -> Int
eval expr env = case expr of
    Const n -> n
    Var v -> fromJust (lookup v env)
    OpExpr left op right ->
        let l = eval left env
            r = eval right env
        in opfun op l r

lists

Pretend that Haskell does not have a built-in list type. Implement lists using an abstract data type DList a.

data DList a = Nil | Cons a (DList a)
  deriving (Eq, Ord)

Write a function that computes the sum of all values in a DList Int.

dsum :: DList Int -> Int
dsum Nil = 0
dsum (Cons x rest) = x + dsum rest

Write a function that performs a right fold over a DList a.

dfoldr :: (b -> a -> a) -> a -> DList b -> a
dfoldr _ a Nil = a
dfoldr f a (Cons x rest) = f x (dfoldr f a rest)