Thought for the day
“…there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated there are no obvious deficiencies. The first method is far more difficult.”
— Tony Hoare, 1980 ACM Turing Award Lecture
©D. Poole 2019
CPSC 312 — Lecture 4 1 / 17
Review
Haskell Types:
Bool (&&, ||, not) Num (+, −, ∗, abs)
Integral (div, mod) Int
Integer Fractional (/)
Floating (log, sin, exp, …) Double
Eq (==, /=)
Ord (>, >=, <=, <)
List ([] 🙂 Char
String
CPSC 312 — Lecture 4
2 / 17
©D. Poole 2019
Types Revisited
Type declaration:
exp :: cc => te
exp is an expression,
cc is a (tuple of) class constraint of form C a where C is a class (e.g, Num, Integral,…) and a is a type variable.
te is a type expression. Afunctionfromtypebtotypecisoftype b -> c
A list of type b is of type [b]
A 3-tuple (triple) of elements of type b, c, d is of type
(b, c, d). (Similarly for other-length tuples).
What is the type of length that takes a list and returns an Int? length :: [a] -> Int
What is the type of + that adds two numbers?
(+) :: Num a => a -> a -> a
What is the type of div (integer division)?
div :: Integral a => a -> a -> a
CPSC 312 — Lecture 4
3 / 17
©D. Poole 2019
Types (cont)
What is the inferred type of numeq?
numeq _ [] = 0
numeq x (h:t)
| x==h = 1+numeq x t
| otherwise = numeq x t
numeq :: (Num a, Eq a1) => a1 -> [a1] -> a
Note: a and a1 could be same or different types. What is the inferred type of numc?
numc _ [] = 0
numc c (h:t)
| c h = 1+numc c t
| otherwise = numc c t
numc :: Num a => (t -> Bool) -> [t] -> a
CPSC 312 — Lecture 4
4 / 17
©D. Poole 2019
Clicker Question
The inferred type of numeq is
numeq :: (Num p, Eq t) => t -> [t] -> p What is the inferred type of numless:
numless _ [] = 0
numless x (h:t)
| h
D numless :: t -> [t] -> p
E numless :: Int -> [Int] -> Int
©D. Poole 2019
CPSC 312 — Lecture 4 5 / 17
Clicker Question
What is the inferred type of myelem defined by
myelem _ [] = False
myelem e (h:t)
| e==h = True
| otherwise = myelem e t
A myelem :: Eq a => a -> [b] -> Bool
B myelem :: Eq t => t -> [t] -> Bool
C myelem :: a -> [b] -> Bool
D myelem :: a -> [b]
E I have no idea
See
http://cs.ubc.ca/~poole/cs312/2018/haskell/Lists2.pl
©D. Poole 2019
CPSC 312 — Lecture 4 6 / 17
Clicker Question
What is the inferred type of mytake defined by
mytake 0 _ = []
mytake _ [] = []
mytake n (x:xs) = x : mytake (n-1) xs
A mytake :: Int -> [Int] -> [Int]
B mytake :: (Num a, Eq a) => a -> [t] -> [t]
C mytake :: (Num a, Eq a) => a -> [t] -> t
D mytake :: (Num a, Eq a) => a -> t -> t
E I have no idea
See
http://cs.ubc.ca/~poole/cs312/2018/haskell/Lists2.pl
©D. Poole 2019
CPSC 312 — Lecture 4 7 / 17
Clicker Question
What is the inferred type of numeqh defined by
numeqh _ [] n = n
numeqh x (h:t) n
| x==h = numeqh x t (n+1)
| otherwise = numeqh x t n
A numeqh :: (Num b, Eq a) => (a, [a], b) -> b
B numeqh :: (Num a, Eq a) => a -> [a] -> a -> a C numeqh :: (Eq a) => a -> [a] -> Int -> Int
D numeqh :: (Num b, Eq a) => a -> [a] -> b -> b E I have no idea
©D. Poole 2019
CPSC 312 — Lecture 4 8 / 17
Clicker Question
What is the inferred type of flip defined by flip f a b = f b a
A flip :: (t1 -> t2) -> t2 -> t1
B flip :: (t -> t -> t) -> t -> t -> t
C flip :: (t -> t) -> t -> t
D flip :: (t1 -> t2 -> t) -> t2 -> t1 -> t E I have no idea
©D. Poole 2019
CPSC 312 — Lecture 4 9 / 17
Clicker Question
Consider the functions flip and hh defined by flip f a b = f b a
hh x y z = 10000*x + 100*y + z
What is the value of
flip hh 3 5 7
(It does not give an error.)
A 30507 B 70503 C 50307 D 30705 E 70305
©D. Poole 2019
CPSC 312 — Lecture 4 10 / 17
Clicker Question
Consider the functions flip and hh defined by flip f a b = f b a
hh x y z = 10000*x + 100*y + z
What is the value of
flip (hh 3) 5 7
(It does not give an error.)
A 30507 B 70503 C 50307 D 30705 E 70305
©D. Poole 2019
CPSC 312 — Lecture 4 11 / 17
Clicker Question
filter defined by
filter _ [] = []
filter c (h:t)
| c h = h:filter c t
| otherwise = filter c t
has type:
A filter :: t -> Bool -> [t] -> [t]
B filter :: ([t] -> Bool) -> [t] -> [t]
C filter :: (t -> Bool) -> t -> t
D filter :: (t -> Bool) -> [t] -> [t]
E it does not have a legal type (and will result in a type error)
©D. Poole 2019
CPSC 312 — Lecture 4 12 / 17
Clicker Question
filter, even are defined by:
filter _ [] = []
filter c (h:t)
| c h = h:filter c t
| otherwise = filter c t
even n = 0 == mod n 2
what is the result of
filter even [1,2,3,4,5,6]
A [2,4,6]
B [2,4,6,8,10,12]
C3
D [False,True,False,True,False,True] E It gives a type error
©D. Poole 2019
CPSC 312 — Lecture 4 13 / 17
Clicker Question
Given the definitions:
filter _ [] = []
filter c (h:t)
| c h = h:filter c t
| otherwise = filter c t
even n = 0 == mod n 2
nums = [1,2,4,5,6,7,8,10,11]
Which query will return the number of even elements of nums
A length filter even nums
B filter length even nums
C length (filter even nums) D filter even nums length
E None of the above
©D. Poole 2019
CPSC 312 — Lecture 4 14 / 17
Some Predefined list definitions (Lists2.hs)
[e1..en] is the list of elements from e1 to en (inclusive) [e1,e2..em] is the list of elements from e1 to em, where e2 − e1 gives step size
[e..] is the list of all numbers from e
take n lst
head lst tail lst
lst !! n
lst1 ++ lst2 append lst1 and lst2
sum [a1,a2,..an]=a1+a2+…+an
zip [a1,a2,…,an] [b1,b2,…,bn] = [(a1,b1),(a2,b2),…,(an,bn)] map f [a1,a2,…,an] = [f a1,f a2,…,f an]
first n elements of lst
is the first element of lst is the rest of the list
nth element of lst
CPSC 312 — Lecture 4 15 / 17
©D. Poole 2019
Lambda
How can we find elements of a list that are less than 3 or greater than 7 (using filter)?
Lambda lets us define a function without giving it a name. \ x -> (x < 3) || (x > 7)
is a function true of numbers less than 3 or greater than 7
filter (\ x -> (x < 3) || (x > 7)) [1..10]
is easy to read and work out what it is saying A definition
foo x = exp
is an abbreviation for
foo = \ x -> exp
foo x y = exp
foo = \ x -> \y -> exp
foo = \ x y -> exp
myadd = \x y -> x+y
is an abbreviation for alsowritten
CPSC 312 — Lecture 4 16 / 17
©D. Poole 2019
©D. Poole 2019
CPSC 312 — Lecture 4 17 / 17