CMPUT 325 Schedule and Outcomes
9. Week 7 - Feb 24

## 9.1 Topics

• Instead of a makeup exam we will have a makeup assignment, the mark on which will replace your midterm mark.

• Introduction to Haskell

• Hoogle - a Haskell function search engine! http://www.haskell.org/hoogle

• A much faster Fibonacci sequence generator than the usual recursive one.
code/Week07/fib-fast.hs

 `    ``-- computing fibonacci in linear time` `    `` ` `    ``-- shifted sum of a list` `    ``-- ugly version: ssum lst@(h:rest) = zipWith (+) lst rest` `    ``-- elegant version:` `    `` ` `    ``ssum lst = zipWith (+) lst (drop 1 lst)` `    `` ` `    ``-- make sure full precision integers` `    ``fib_seq :: [Integer]` `    `` ` `    ``-- recursive equation for the sequence` `    ``fib_seq = [0, 1] ++ ssum fib_seq` `    `` ` `    ``fib n = fib_seq !! n`

## 9.2 Flipped Work

• Download and read the Haskell Cheat Sheet by Justin Bailey. You can find it at http://cheatsheet.codeslower.com

• Figure out how modules work in Haskell by making an expression tree module and then using it in a program in a different source file.

## 9.3 Creating New Types

Type Synonyms

In order to improve the readability of your code, you can introduce type synonyms or aliases using `type`. This does not introduce a new type, but just gives an alternative name.

code/Week07/synonym-1.hs

 `    ``-- type synonym that indicates a function from Int to Int that increments` `    ``type Inc = Int -> Int` `    `` ` `    ``inc1 :: Inc` `    ``inc1 x = x + 1` `    `` ` `    ``inc2 :: Inc` `    ``inc2 x = x + 2` `    `` ` `    ``twice :: Inc -> Inc` `    ``-- could do this: twice i x = (i (i x))` `    ``-- but this is beter` `    ``twice i = i . i` `    `` ` `    ``nof :: Inc -> Int -> Inc` `    ``nof i 0 x = x` `    ``nof i n x = (i (nof i (n-1) x))` `    `` ` `    ``-- rewrite nof using composition like twice, without x` `    `` ` `    ``-- :t nof (\x -> x + 3)` `    `` ` `    ``-- any Int -> Int function will do` `    ``inc3 :: Int -> Int` `    ``inc3 x = x + 3`

Simple New Types

With `newtype` you can introduce a new type, that uses existing types for its values, but tags the type so that the type checker can distiguish between the different uses of the value. These new types have no additional computational overhead since they have only one type constructor. code/Week07/newtype-1.hs

 `    ``-- this new type indicates an a Int wrapped as a parameter, so that not just` `    ``-- any Int can be used.` `    `` ` `    ``newtype Param = P Int deriving Show` `    `` ` `    ``type Inc = Param -> Param` `    `` ` `    ``x :: Param` `    ``x = P 1` `    `` ` `    ``inc1 :: Inc` `    ``inc1 (P y) = P (y + 1)` `    `` ` `    ``twice :: Inc -> Inc` `    ``twice i =  i . i` `    `` ` `    ``-- now any Int -> Int function will not do` `    ``inc3 :: Int -> Int` `    ``inc3 x = x + 3` `    `` ` `    ``-- twice inc3 0`

Algebraic Data Types

`data` is used to create new kinds of values in the form of new data structures with operations on them. Constructors tell you how to combine things to make a new value, pattern matchnig tells you how to take the values apart, these two let you build new operations.

For example, a pair of `Int`. Note how the `Show` and `Eq` subclass properties (see below) are derived from the corresponding classes of the types used to build the new type.

code/Week07/pair-1.hs

 `    ``data Pair = P Int Int deriving (Show, Eq)` `    `` ` `    ``pairFst (P x y ) = x` `    ``pairSnd (P x y ) = y`

Generalize to a pair of anything of the same type, and introduce an ordering on pairs to make it also a subclass of `Ord`.

code/Week07/pair-2.hs

 `    ``--` `    ``-- pairs of things of type a` `    ``--` `    `` ` `    ``data Pair a = P a a deriving (Show, Eq)` `    `` ` `    ``pairFst (P x y ) = x` `    ``pairSnd (P x y ) = y` `    `` ` `    ``-- ordering on pairs of the same type of thing` `    `` ` `    ``instance Ord a => Ord (Pair a) where` `    ``  compare (P x1 y1) (P x2 y2) = ` `    ``    case compare x1 x2 of EQ -> compare y1 y2` `    ``                          LT -> LT` `    ``                          GT -> GT`

Generalize to a pair of two potentially differnt types of things, and derive the "natural" lexigographic ordering on pairs.

code/Week07/pair-3.hs

 `    ``--` `    ``-- pairs of things of type a and b, automatic deriving` `    ``--` `    `` ` `    ``data Pair a b = P a b deriving (Show, Eq, Ord)` `    `` ` `    ``pairFst (P x y ) = x` `    ``pairSnd (P x y ) = y` `    `` ` `    ``-- :t (<) P 1 2` `    ``-- :t (<) P 1 'a'` `    ``-- :t (<) P 1 "a"` `    `` ` `    `` `

Parameterized New Types

`newtype` can also be paramterized like `data`

code/Week07/newtype-2.hs

 `    ``newtype Param a = P a deriving Show` `    `` ` `    ``type Inc a = Param a -> Param a` `    `` ` `    ``twice :: Inc a -> Inc a` `    ``twice i =  i . i` `    `` ` `    ``x :: Param Int` `    ``x = P 1` `    `` ` `    ``y :: Param String` `    ``y = P "fred"` `    `` ` `    ``inc1 :: Num a => Inc a` `    ``inc1 (P y) = P (y + 1)` `    `` ` `    ``-- we could declare inc2 :: Inc [Int]` `    ``-- but actually it's more general derived type is Param [a] -> Param [a]` `    ``inc2 (P y) = P (y ++ y)` `    `` ` `    ``-- try: twice inc1 \$ P 3` `    `` ` `    ``-- now any Int -> Int function will not do` `    ``inc3 :: Int -> Int` `    ``inc3 x = x + 3` `    `` ` `    ``-- try: twice inc2 \$ P [ 1 , 2]` `    `` ` `    ``-- twice inc3 0`

code/Week07/newtype-3.hs

 `    ``newtype Param a = P a deriving Show` `    `` ` `    ``newtype Inc a = I (Param a -> Param a)` `    `` ` `    ``twice :: Inc a -> Inc a` `    ``twice (I i) =  I ( i . i )` `    `` ` `    ``ap (I f) x = f x` `    `` ` `    ``x :: Param Int` `    ``x = P 1` `    `` ` `    ``y :: Param String` `    ``y = P "fred"` `    `` ` `    ``-- IMPORTANT TRICK: when confused by the type signature, just define your` `    ``-- function, then use :t to extract its type.` `    `` ` `    ``inc1 :: Inc Integer` `    ``inc1 = I f where` `    ``    f (P y) = P (y+1)` `    `` ` `    ``-- we could declare inc2 :: Inc [Int]` `    ``-- but actually it's more general derived type is` `    ``inc2 :: Inc [ a ]` `    ``inc2 = I f where` `    ``    f (P y) = P (y ++ y)` `    `` ` `    ``-- try: twice inc1 \$ P 3` `    ``-- try:` `    ``-- let g = twice inc1` `    ``-- ap g (P 3)` `    ``-- try: ap (twice inc2) \$ P [ 1 , 2]` `    `` ` `    ``-- now any Int -> Int function will not do, try this declaration` `    ``-- inc3 = I f where` `    ``--     f x = x + 3`

Expression Trees

code/Week07/exptree.hs

 `    ``-- Now lets build expression trees` `    ``-- a is the type of the values in the tree, ` `    ``-- f is the type of the operations performed on the values` `    `` ` `    ``data ExpTree a f = V a | Op f (ExpTree a f) (ExpTree a f) deriving (Eq, Show)` `    `` ` `    ``t1 = (Op (+) (V 10) (V 20))` `    `` ` `    ``t2 = (Op (*) (V 4) (V (- 1)))` `    `` ` `    ``t3 = (Op (+) t1 t2)` `    `` ` `    ``-- and here is an evaluator on expression trees` `    ``evalExp (V n) = n` `    ``evalExp (Op f e1 e2) = (f (evalExp e1) (evalExp e2))` `    `` ` `    ``-- evalExp t1` `    ``-- evalExp t2` `    ``-- evalExp t3` `    `` ` `    ``-- Note that the trees are functions of the types, so here is a tree containing` `    ``-- lists, and operations between lists` `    `` ` `    ``tl1 = (V [1, 2, 3])` `    ``tl2 = (V [4, 5, 6, 7])` `    ``tl3 = (Op (++) tl1 tl2)` `    `` ` `    ``-- evalExp tl1` `    ``-- evalExp tl2` `    ``-- evalExp tl3` `    `` ` `    ``-- Now try ` `    ``-- tm1 = (Op (++) tl3 t3)` `    `` `

Qualified Types and Type Classes

The `data` keyword lets you introduce new values. Haskell type classes let you package the new values with associated operations. This is done with the `class` keyword.

But first some notation we have been using. The `=>` arrow is a type qualifier. When we have a type, say like this `g :: a -> a` we read this as function over any type `a`. Or more precisely, for all types `a`, `g` is a function of type `a->a`.

But many times this is too general. This function
`g x = x + 1 `
only makes sense on values that have a `+` operation. So we might want to restrict it to numbers. What are numbers? In Haskell, there is a class called `Num`, and so we can restrict our function definition to only be on number-like instances:
```g :: Num a => a -> a g x = x + 1 ```
which can be read as for any type `a` that is a member of the class `Num`, the function `g` has type `a -> a`.

There are some very important type classes:

• Show - provides the ability to print values

• Eq - provides the ability to test for equality

• Ord - provides ordering on values
When you generate a new data type, you often want to establish that the new datatype is an instance of the these type classes. See the pair example above. In many cases, Haskell can derive the required instance information by induction on the constructors used to create the new values.

Modules

code/Week07/treemodule.hs

 `    ``module Tree ( Tree(Leaf,Branch), fringe ) where` `    `` ` `    ``data Tree a = Leaf a | Branch ( Tree a ) ( Tree a )  deriving (Eq, Show)` `    `` ` `    ``fringe :: Tree a -> [a]` `    ``fringe ( Leaf x )            = [x]` `    ``fringe ( Branch left right ) = fringe left ++ fringe right`

 9. Week 7 - Feb 24 CMPUT 325 Schedule / Version 2.31 2014-04-04