CMPUT 325 Schedule and Outcomes
11. Week 9 - Mar 10

## 11.1 Topics

• Background material for actual midterm questions

• Study questions for Midterm 2

## 11.2 Background Material for Question 1 on Midterm 2

The first question on the midterm is going to use these data types and functions. Read and study them carefully. Assuming that you have already been look at a variant of the chain question below, you will see that these definitions and functions are much cleaner.
code/Week09/chain-question.hs

 `    ``{- ` `    ``    chain a sequence of actions such that if one fails, ` `    ``    all the the remaining ones fail.` `    ``-}` `    `` ` `    ``-- the state of a computation action is either OK, in which case the resulting` `    ``-- current state a is passed on, or it fails and Failure is passed on` `    ``data State a = OK a | Failure` `    ``    deriving (Show, Eq)` `    `` ` `    ``-- an action is a function from state to state` `    `` ` `    ``-- examples of actions that result in a state` `    ``myAction :: (Integral a, Eq a) => State a -> State a` `    ``myAction (OK 0) = Failure` `    ``myAction (OK x) = OK (x - 1)` `    ``myaction Failure = Failure` `    ``myaction _ = Failure` `    `` ` `    ``myAction2 :: (Integral a, Eq a) => State a -> State (a, String)` `    ``myAction2 (OK 0) = Failure` `    ``myAction2 (OK x) = case x `mod` 2 of` `    ``    0 -> OK (x, "Even")` `    ``    1 -> OK (x, "Odd")` `    ``myaction2 _ = Failure` `    `` ` `    ``-- we chain actions togeter using thenWe, which has infix form `thenWe`` `    `` ` `    ``thenWe :: State a -> (State a -> State b) -> State b` `    ``thenWe (OK x) f = f (OK x)` `    ``thenWe Failure _ = Failure` `    `` ` `    ``-- try testIt 3 and testIt 0 and testIt 1` `    ``testIt i = ` `    ``    -- we need to start an action with an initial state` `    ``    OK i `thenWe` ` `    ``    myAction `thenWe` ` `    ``    myAction2` `    `` ` `    ``-- compose a function n >= 0 times with itself` `    ``composeN :: Int -> (a -> a) -> (a -> a)` `    ``composeN 0 f = id` `    ``composeN n f = f . (composeN (n-1) f)` `    `` ` `    ``-- function actNTimes that creates a new action consisting of ` `    ``-- performing action f n times.` `    ``actNTimes :: Int -> (State a -> State a) -> (State a -> State a)` `    ``actNTimes n f = composeN n (`thenWe` f)` `    `` ` `    ``testIt' :: Integral a => a -> State (a, String)` `    ``testIt' x = ` `    ``    (OK x) `thenWe`` `    ``    (actNTimes 7 myAction) `thenWe` ` `    ``    myAction2` `    `` ` `    ``-- return the state the predicate succeeded on, or Failure ` `    ``actUntilFound :: (State a -> Bool) -> (State a -> State a) -> State a -> State a` `    ``actUntilFound pred f curState = case curState of` `    ``    Failure -> Failure` `    ``    _ -> case pred curState of` `    ``        True -> curState` `    ``        False -> actUntilFound pred f (f curState)` `    `` ` `    ``{- Example` `    ``    *Main> actUntilFound (\s -> (s == (OK 4) || s == (OK 0) )) myAction (OK 10)` `    ``    OK 4` `    ``    *Main> actUntilFound (\s -> (s == (OK 4) || s == (OK 0) )) myAction (OK 3)` `    ``    OK 0` `    ``-}` `    `` ` `    ``-- return the state just before the predicate failed` `    ``actUntilFail pred f curState = actUntilFail' pred f Failure curState` `    `` ` `    ``{- Example` `    ``    *Main> actUntilFail (/= (OK 4))  myAction (OK 20) ` `    ``    OK 5` `    ``    *Main> actUntilFail (/= (OK 4))  myAction (OK 20) `thenWe` myAction` `    ``    OK 4` `    `` ` `    ``    *Main> actUntilFail (/= (OK 4))  myAction (OK (2))` `    ``    OK 0` `    ``    *Main> actUntilFail (/= (OK 4))  myAction (OK (2)) `thenWe` myAction` `    ``    Failure` `    ``-}` `    `` ` `    ``-- recursor helper that has a previous state in addition to the current` `    ``-- satte so that the predicate can fail on the current state.` `    `` ` `    ``actUntilFail' :: (State a -> Bool) -> (State a -> State a) -> ` `    ``    State a -> State a -> State a` `    `` ` `    ``actUntilFail' pred f prevState curState = case curState of` `    ``    Failure -> prevState` `    ``    _ -> case pred curState of` `    ``        -- move to next state and recurse` `    ``        True -> actUntilFail' pred f curState (f curState)` `    ``        -- we failed, return the previous successful state` `    ``        False -> prevState` `    `` ` `    ``-- version that has the helper defined inside, and thus does not need` `    ``-- to propagate pred or f into the helper through paramaters` `    ``actUntilFail2 pred f curState = actUntilFail2' Failure curState` `    ``    where` `    ``        actUntilFail2' prevState curState = case curState of` `    ``            Failure -> prevState` `    ``            _ -> case pred curState of` `    ``                -- move to next state and recurse` `    ``                True -> actUntilFail2' curState (f curState)` `    ``                -- we failed, return the previous successful state` `    ``                False -> prevState`

## 11.3 Background Material for Question 2 on Midterm 2

The second question on the midterm is going to use these data types and functions. Read and study them carefully.
code/Week09/trees-question.hs

 `    ``{-` `    ``    A ManyTree over type a, is a tree that consists of leaves with values` `    ``    of type a, and internal vertices which consist of lists of 0 or more` `    ``    ManyTree subtrees.` `    ``-}` `    `` ` `    ``data ManyTree a = Leaf a | Internal [ ManyTree a ]` `    ``    deriving (Eq, Show)` `    `` ` `    ``-- deconstructors, sometimes easier than using a pattern match` `    ``getLeaf (Leaf x) = x` `    ``getSubtrees (Internal subtrees) = subtrees` `    `` ` `    `` ` `    ``-- example trees` `    ``t1 :: ManyTree Int` `    ``t1 = Internal [ Leaf 1, Leaf 2, Leaf 3]` `    `` ` `    ``l2 :: [Int]` `    ``l2 = (map getLeaf (getSubtrees t1))` `    ``t2 = Internal (map (\x -> Leaf (x *10))  l2)` `    `` ` `    ``-- since trees are functional, you can have the same sub tree appearing` `    ``-- in multiple places` `    ``t3 = Internal [t1, t2]` `    ``t4 = Internal [t1, t2, Leaf 42, Internal [t1, t2]]` `    `` ` `    ``-- do a depth first left to right traversal of tree t` `    ``dfslr :: ManyTree a -> [a]` `    ``dfslr (Leaf x) = [x]` `    ``dfslr (Internal subTrees) = foldl (++) [] (map dfslr subTrees)` `    `` ` `    ``-- do a dfs over the tree, but output the path to each leaf` `    `` ` `    ``{- Examples:` `    ``    *Main> dfslr t1` `    ``    [1,2,3]` `    ``    *Main> dfslr t2` `    ``    [10,20,30]` `    ``    *Main> dfslr t3` `    ``    [1,2,3,10,20,30]` `    ``-}` `    `` ` `    `` ` `    ``-- transforms on trees` `    `` ` `    ``-- apply a transform f to each leaf returning a tree of a different type` `    ``mapLeaf :: (a->b) -> (ManyTree a) -> (ManyTree b)` `    ``mapLeaf f (Leaf x) = Leaf (f x)` `    ``mapLeaf f (Internal subTrees) = Internal ( map (mapLeaf f) subTrees )` `    `` ` `    ``{- Examples:` `    ``    *Main> mapLeaf (\x -> x * 10 ) t2` `    ``    Internal [Leaf 100,Leaf 200,Leaf 300]` `    `` ` `    ``    *Main> mapLeaf (* 10 ) t2` `    ``    Internal [Leaf 100,Leaf 200,Leaf 300]` `    `` ` `    ``    *Main> mapLeaf (\x -> (show x)++"x" ) t2` `    ``    Internal [Leaf "10x",Leaf "20x",Leaf "30x"]` `    ``    *Main> mapLeaf (\x -> (show x)++"x" ) t4` `    ``    Internal [Internal [Leaf "1x",Leaf "2x",Leaf "3x"],` `    ``        Internal [Leaf "10x",Leaf "20x",Leaf "30x"],` `    ``        Leaf "42x",Internal [Internal [Leaf "1x",Leaf "2x",Leaf "3x"],` `    ``        Internal [Leaf "10x",Leaf "20x",Leaf "30x"]]]` `    ``-}` `    `` ` `    ``-- apply a transform to each internal vertex ` `    ``mapInternal :: ([ManyTree a] -> [ManyTree a]) -> ManyTree a -> ManyTree a` `    ``mapInternal f (Leaf x) = Leaf x` `    ``mapInternal f (Internal subTrees) = ` `    ``    Internal (f (map (mapInternal f) subTrees))` `    `` ` `    ``{- Examples:` `    `` ` `    ``    *Main> mapInternal (\st -> drop 1 st) t3` `    ``    Internal [Internal [Leaf 20,Leaf 30]]` `    `` ` `    ``    *Main> mapInternal (drop 1) t3` `    ``    Internal [Internal [Leaf 20,Leaf 30]]` `    `` ` `    ``    *Main> mapInternal (drop 1) t4` `    ``    Internal [Internal [Leaf 20,Leaf 30],Leaf 42,` `    ``            Internal [Internal [Leaf 20,Leaf 30]]]` `    ``-}`

A good way to study the core aspects of Haskell is to re-implement many of the standard functions in the prelude library. For example,
```zipWith foldl foldl1 foldr foldr1 break drop dropWhile filter - do with both list comprehension and without map - do with both list comprehension and without replicate reverse - do with a fold, and with an accumulator span splitAt take until zipWith (!!) - indexing into a list (.) - function composition (\$) - right associative operator (++) - append ```
The ones we did for Racket like
```shuffle compose prefix ```
Some more creative ones. These may not have a perfect answer, so make you own decisions.
```everyNth n list - returns every n'th element of a finite or infinite list polynomial c x - given a possibly infinite sequence of coefficients compute the polynomial c_0 x^0 + c_1 x^ 1 + ... . Can you use Horner's rule here? What if you know the sequence of corfficients is finite? Can you tell? ```

## 11.5 Data Types

1. A type that represents a seqence of coefficients, and tells you if it is infinite or finite. What kind of operations on such sequences make sense?

2. Arbitrary branching factor trees. A node in a tree can have one or more subtrees.

3. Define a SuperTree typeclass. That is, identify the kinds of operations that make sense to perform on a tree (including arbitray branching factors) and express this as a type class.

4. Annotated trees. Given a type that is an instance of SuperTree, create an AnnotatedSuperTree that lets you attach a value of a given type to the vertices and leaves of the tree.

## 11.6 Challenge Problems

1. What would map and fold look like for trees.

2. Consider this code that is motivated by the chaining example we did in racket. code/Week09/chain.hs

 `    ``{- ` `    ``    chain a sequence of actions such that if one fails, ` `    ``    all the the remaining ones fail.` `    `` ` `    ``-}` `    `` ` `    ``-- the state of a computation action is either OK, in which case the resulting` `    ``-- current state a is passed on, or it fails and Failure is passed on` `    ``data State a = OK a | Failure` `    ``    deriving (Show, Eq)` `    `` ` `    ``-- examples of actions that result in a state` `    ``myAction :: (Integral a, Eq a) => a -> State a` `    ``myAction 0 = Failure` `    ``myAction x = OK (x - 1)` `    `` ` `    ``myAction2 :: (Integral a, Eq a) => a -> State (a, String)` `    ``myAction2 0 = Failure` `    ``myAction2 x = case x `mod` 2 of` `    ``    0 -> OK (x, "Even")` `    ``    1 -> OK (x, "Odd")` `    `` ` `    ``-- we chain actions togeter using thenWe, which has infix form `thenWe`` `    ``thenWe :: State a -> (a -> State b) -> State b` `    ``thenWe (OK a) f = (f a)` `    ``thenWe Failure _ = Failure` `    `` ` `    `` ` `    ``-- try testIt 3 and testIt 0 and testIt 1` `    ``testIt i = ` `    ``    -- we need to start an action with an initial state` `    ``    OK i `thenWe` ` `    ``    myAction `thenWe` ` `    ``    myAction2` `    `` ` `    ``composeN :: Int -> (a -> a) -> (a -> a)` `    ``composeN 0 f = f` `    ``composeN n f = f . (composeN (n-1) f)` `    `` ` `    ``-- write a function actN that composes action f on initial state i, n times.` `    ``actN :: Int -> (a -> State a) -> State a -> State a` `    ``actN n f = composeN n (`thenWe` f)` `    `` ` `    ``testIt' :: Integral a => a -> State (a, String)` `    ``testIt' x = ` `    ``    (OK x) `thenWe`` `    ``    (actN 7 myAction) `thenWe` ` `    ``    myAction2`

Implement the function `actN`

 11. Week 9 - Mar 10 CMPUT 325 Schedule / Version 2.31 2014-04-04