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




11.1 Topics



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]]]
    -}


11.4 Haskell standard functions

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