“I think that it’s extraordinarily important that we in computer science keep fun in computing. When it started out, it was an awful lot of fun. Of course, the paying customers got shafted every now and then, and after a while we began to take their complaints seriously. We began to feel as if we really were responsible for the successful, error-free perfect use of these machines. I don’t think we are. I think we’re responsible for stretching them, setting them off in new directions and keeping fun in the house. I hope the field of computer science never loses its sense of fun.”
– Alan J. Perlis, 1977 (quoted in dedication to “Structure and Interpretation of Computer Programs”, 1985)
©D. Poole 2018
CPSC 312 — Lecture 9 1/7
Review
Haskell is a functional programming language Strongly typed, but with type inference
Bool
Num, Int, Integer, Fractional, Floating, Double Eq, Ord
Tuple, List, Function
Classes, type variables
List comprehension [f x | x<-list, cond x]
foldr ⊕ v [a1,a2,..an]=a1⊕(a2⊕(...⊕(an⊕v))) foldl ⊕ v [a1,a2,..an]=(((v⊕a1)⊕a2)⊕...)⊕an reduction
call-by-value, call-by-name, lazy evaluation
type, data
CPSC 312 — Lecture 9 2/7
©D. Poole 2018
Type and data
data defines new data structures (and a type) Example:
data FValue = BooleanF Bool
| NumberF Int
| StringF [Char]
| MissingF
defines
a new type: FValue
4 new constructors: BooleanF, NumberF, StringF, MissingF.
The constructors have dual roles:
constructors with arguments give functions that can create a
new value of that type
constructors with no arguments are constants
constructors can be used patterns for deconstructing the type
(accessors) on left side of = or in function definitions.
CPSC 312 — Lecture 9 3/7
©D. Poole 2018
Clicker Question
In the Prelude is the definition:
data Maybe t = Nothing
| Just t
Which of the following not true:
A Maybe Int is a type
B Nothing and Just are both functions of type Maybe C Nothing is a constant of type Maybe t for all types t D Just is a function from type t to Maybe t
©D. Poole 2018
CPSC 312 — Lecture 9 4/7
Clicker Question
Suppose the function
myfun Toves = 7
myfun (Slithy x) = x+2
has inferred type
myfun :: Gyre -> Integer
and compiles and never gives a runtime error. Which is not true:
A Gyre is a type
B Slithy is a function of type Integer -> Gyre
C Toves is a constant of type Gyre
D There must be a declaration data Gyre = Toves
| Slithy Integer
E One of the above is false.
(So if all A-D are true, this is the answer.)
©D. Poole 2018
CPSC 312 — Lecture 9 5/7
Recursive data types (BSTree.hs)
data definitions can be recursive: Example:
— a binary search tree that maps integers to strings
data BSTree = Empty
| Node Int String BSTree BSTree
defines a new type, BSTree, and two new constructors Empty and Node.
The constructors can be used as
constants (Empty) or functions (Node) to create a BSTree patterns for deconstructing the type
The data structures can be parametrized by types:
— a binary search tree
— k is the key type; v is the value type
data BSTree k v = Empty
| Node k v (BSTree k v) (BSTree k v)
CPSC 312 — Lecture 9 6/7
©D. Poole 2018
data (BSTree2.hs)
A binary search tree:
— a binary search tree
— k is the key type; v is the value type
data BSTree k v = Empty
| Node k v (BSTree k v) (BSTree k v) What should lookup key tree return?
What if the key isn’t in the tree?
How can insert key value tree also return the old value of key?
What is there wasn’t an old value?
CPSC 312 — Lecture 9 7/7
©D. Poole 2018