cse130

Abstracting Code Patterns

a.k.a. Don’t Repeat Yourself

Lists

data List a
  = []
  | (:) a (List a)

Rendering the Values of a List

-- >>> incList [1, 2, 3]
-- ["1", "2", "3"]

showList        :: [Int] -> [String]
showList []     =  []
showList (n:ns) =  show n : showList ns

Squaring the values of a list

-- >>> sqrList [1, 2, 3]
-- 1, 4, 9

sqrList        :: [Int] -> [Int]
sqrList []     =  []
sqrList (n:ns) =  n^2 : sqrList ns

Common Pattern: `map` over a list

Refactor iteration into mapList

mapList :: (a -> b) -> [a] -> [b]
mapList f []     = []
mapList f (x:xs) = f x : mapList f xs

Reuse map to implement inc and sqr

showList xs = map (\n -> show n) xs

sqrList  xs = map (\n -> n ^ 2)  xs

Trees

data Tree a
  = Leaf
  | Node a (Tree a) (Tree a)

Incrementing and Squaring the Values of a Tree

-- >>> showTree (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf))
-- (Node "2" (Node "1" Leaf Leaf) (Node "3" Leaf Leaf))

showTree :: Tree Int -> Tree String
showTree Leaf         = ???
showTree (Node v l r) = ???

-- >>> sqrTree (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf))
-- (Node 4 (Node 1 Leaf Leaf) (Node 9 Leaf Leaf))

sqrTree :: Tree Int -> Tree Int
sqrTree Leaf         = ???
sqrTree (Node v l r) = ???

QUIZ: `map` over a Tree

Refactor iteration into mapTree! What should the type of mapTree be?

mapTree :: ???

showTree t = mapTree (\n -> show n) t
sqrTree  t = mapTree (\n -> n ^ 2)  t

{- A -} (Int -> Int)    -> Tree Int -> Tree Int
{- B -} (Int -> String) -> Tree Int -> Tree String
{- C -} (Int -> a)      -> Tree Int -> Tree a
{- D -} (a -> a)        -> Tree a   -> Tree a
{- E -} (a -> b)        -> Tree a   -> Tree b

Lets write `mapTree`

mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f Leaf         = ???
mapTree f (Node v l r) = ???

QUIZ

Wait … there is a common pattern across two datatypes

mapList :: (a -> b) -> List a -> List b    -- List
mapTree :: (a -> b) -> Tree a -> Tree b    -- Tree

Lets make a class for it!

class Mappable t where
  map :: ???

What type should we give to map?

{- A -} (b -> a) -> t b    -> t a
{- B -} (a -> a) -> t a    -> t a
{- C -} (a -> b) -> [a]    -> [b]
{- D -} (a -> b) -> t a    -> t b
{- E -} (a -> b) -> Tree a -> Tree b

Reuse Iteration Across Types

Haskell’s libraries use the name Functor instead of Mappable

instance Functor [] where
  fmap = mapList

instance Functor Tree where
  fmap = mapTree

And now we can do

-- >>> fmap (\n -> n + 1) (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf))
-- (Node 4 (Node 1 Leaf Leaf) (Node 9 Leaf Leaf))

-- >>> fmap show [1,2,3]
-- ["1", "2", "3"]

Exercise: Write a `Functor` instance for `Result`

data Result  a
  = Error String
  | Ok    a

instance Functor Result where
  fmap f (Error msg) = ???
  fmap f (Ok val)    = ???

When you’re done you should see

-- >>> fmap (\n -> n ^ 2) (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf))
-- (Node 4 (Node 1 Leaf Leaf) (Node 9 Leaf Leaf))

-- >>> fmap (\n -> n ^ 2) (Error "oh no") 
-- Error "oh no"

-- >>> fmap (\n -> n ^ 2) (Ok 9) 
-- Ok 81

Next: A Class for Sequencing

Recall our old Expr datatype

data Expr
  = Number Int
  | Plus   Expr Expr
  | Div    Expr Expr
  deriving (Show)

eval :: Expr -> Int
eval (Number n)   = n
eval (Plus e1 e2) = eval e1   +   eval e2
eval (Div  e1 e2) = eval e1 `div` eval e2

-- >>> eval (Div (Number 6) (Number 2))
-- 3

But, what is the result

-- >>> eval (Div (Number 6) (Number 0))
-- *** Exception: divide by zero

A crash! Lets look at an alternative approach to avoid dividing by zero.

The idea is to return a Result Int (instead of a plain Int)

If a sub-expression had a divide by zero, return Error "..."
If all sub-expressions were safe, then return the actual Result v

eval :: Expr -> Result Int
eval (Number n)   = Value n
eval (Plus e1 e2) = case e1 of
                      Error err1 -> Error err1
                      Value v1   -> case e2 of
                                      Error err2 -> Error err2
                                      Value v1   -> Result (v1 + v2)
eval (Div e1 e2)  = case e1 of
                      Error err1 -> Error err1
                      Value v1   -> case e2 of
                                      Error err2 -> Error err2
                                      Value v1   -> if v2 == 0 
                                                      then Error ("yikes dbz:" ++ show e2)
                                                      else Value (v1 `div` v2)

The good news, no nasty exceptions, just a plain Error result

λ> eval (Div (Number 6) (Number 2))
Value 3
λ> eval (Div (Number 6) (Number 0))
Error "yikes dbz:Number 0"
λ> eval (Div (Number 6) (Plus (Number 2) (Number (-2))))
Error "yikes dbz:Plus (Number 2) (Number (-2))"

The bad news: the code is super duper gross

Lets spot a Pattern

The code is gross because we have these cascading blocks

case e1 of
  Error err1 -> Error err1
  Value v1   -> case e2 of
                  Error err2 -> Error err2
                  Value v1   -> Result (v1 + v2)

but really both blocks have something common pattern

case e of
  Error err -> Error err
  Value v   -> {- do stuff with v -}

Evaluate e
If the result is an Error then return that error.
If the result is a Value v then do further processing on v.

Lets bottle that common structure in two functions:

>>= (pronounced bind)
return (pronounced return)

(>>=) :: Result a -> (a -> Result b) -> Result b
(Error err) >>= _       = Error err
(Value v)   >>= process = process v

return :: a -> Result a
return v = Value v

NOTE: return is not a keyword; it is just the name of a function!

A Cleaned up Evaluator

The magic bottle lets us clean up our eval

eval :: Expr -> Result Int
eval (Number n)   = return n
eval (Plus e1 e2) = eval e1 >>= \v1 ->
                      eval e2 >>= \v2 ->
                        return (v1 + v2)
eval (Div e1 e2)  = eval e1 >>= \v1 ->
                      eval e2 >>= \v2 ->
                        if v2 == 0
                          then Error ("yikes dbz:" ++ show e2)
                          else return (v1 `div` v2)

The gross pattern matching is all hidden inside >>=

Notice the >>= takes two inputs of type:

Result Int (e.g. eval e1 or eval e2)
Int -> Result Int (e.g. The processing function that takes the v and does stuff with it)

In the above, the processing functions are written using \v1 -> ... and \v2 -> ...

NOTE: It is crucial that you understand what the code above is doing, and why it is actually just a “shorter” version of the (gross) nested-case-of eval.

A Class for `>>=`

Like fmap or show or jval or ==, or <=, the >>= operator is useful across many types!

Lets capture it in an interface/typeclass:

class Monad m where
  (>>=)  :: m a -> (a -> m b) -> m b
  return :: a -> m a

Notice how the definitions for Result fit the above, with m = Result

instance Monad Result where
  (>>=) :: Either a -> (a -> Either b) -> Either b
  (Error err) >>= _       = Error err
  (Value v)   >>= process = process v

  return :: a -> Result a
  return v = Value v

Syntax for `>>=`

In fact >>= is so useful there is special syntax for it.

Instead of writing

e1 >>= \v1 ->
  e2 >>= \v2 ->
    e3 >>= \v3 ->
      e

you can write

do v1 <- e1
   v2 <- e2
   v3 <- e3
   e
...

Thus, we can further simplify our eval to:

eval :: Expr -> Result Int
eval (Number n)   = return n
eval (Plus e1 e2) = do v1 <- eval e1
                       v2 <- eval e2
                       return (v1 + v2)
eval (Div e1 e2)  = do v1 <- eval e1
                       v2 <- eval e2
                       if v2 == 0
                         then Error ("yikes dbz:" ++ show e2)
                         else return (v1 `div` v2)

Generalizing `Result` to Many Values

We can generalize Result to “many” values, using List

data Result a = Err String | Result a
data List   a = Nil        | Cons   a (List a)

The Err is like [] except it has a message too,
The tail of type (List a) lets us hold many possible a values

We can now make a Monad instance for lists as

instance Monad [] where
  return = returnList 
  (>>=)  = bindList 

returnList :: a -> [a]
returnList x = [x]

bindList :: [a] -> (a -> [b]) -> [b]
bindList []     f = []
bindList (x:xs) f = f x ++ bindList xs f

Notice bindList xs f is like a for-loop:

for each x in xs we call,
f x to get the results
and concatenate all the results

so,

bindList [x1,x2,x3,...,xn] f ==>
  f x1 ++ f x2 ++ f x3 ++ ... ++ f xn

This has some fun consequences!

silly xs = do
  x <- xs
  return (x * 10)

produces the result

-- >>> silly [1,2,3]
-- [10,20,30]

and

foo xs ys = do
  x <- xs
  y <- ys
  return (x, y)

produces the result

-- >>> foo ["1", "2", "red", "blue"] ["fish"]
-- [("1","fish"),("2","fish"),("red","fish"),("blue","fish")]

behaves like Python’s

for x in xs:
  for y in ys:
    yield (x, y)

EXERCISE

Fill in the blanks to implement mMap (i.e. map using monads)

mMap :: (a -> b) -> [a] -> [b]
mMap f xs = do
  _fixme

EXERCISE

Fill in the blanks to implement mFilter (i.e. filter using monads)

mFilter :: (a -> Bool) -> [a] -> [a]
mFilter f xs = do
  _fixme

Abstracting Code Patterns

Lists

Rendering the Values of a List

Squaring the values of a list

Common Pattern: map over a list

Trees

Incrementing and Squaring the Values of a Tree

QUIZ: map over a Tree

Lets write mapTree

QUIZ

Reuse Iteration Across Types

Exercise: Write a Functor instance for Result

Next: A Class for Sequencing

But, what is the result

Lets spot a Pattern

A Cleaned up Evaluator

A Class for >>=

Syntax for >>=

Generalizing Result to Many Values

EXERCISE

EXERCISE

Common Pattern: `map` over a list

QUIZ: `map` over a Tree

Lets write `mapTree`

Exercise: Write a `Functor` instance for `Result`

A Class for `>>=`

Syntax for `>>=`

Generalizing `Result` to Many Values