CMPUT 325 Schedule and Outcomes - 9. Week 7

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.

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

9.1 Topics

9.2 Flipped Work

9.3 Creating New Types