“Pascal [Java] is for building pyramids – imposing, breathtaking, static structures built by armies pushing heavy blocks into place. Lisp [Haskell] is for building organisms – imposing, breathtaking, dynamic structures built by squads fitting fluctuating myriads of simpler organisms into place.
…
the pyramid must stand unchanged for a millennium; the organism must evolve or perish.”
– Alan J. Perlis, Foreword to “Structure and Interpretation of Computer Programs”, 1985, 1996
©D. Poole 2019
CPSC 312 — Lecture 10 1 / 5
The plan going forward
This week: algebraic data types and IO.
Assignment 3 due on Sunday night provides some templates for possible projects (algebraic types, reading files, user interaction)
Project (groups of 2 or 3):
Proposal: 12 February
Final Project Due: 12 February
Project Demos: March 1-5 (by appointment with TAs)
In class: worked example (games in Haskell) Midterm March 1
Then Logic Programming!!
CPSC 312 — Lecture 10 2 / 5
©D. Poole 2019
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 10 3 / 5
©D. Poole 2019
Input-Output (see IOAdder.hs)
IO t is a type that does input output Output putChar, putStr, putStrLn Input getChar, getLine
Do:
do v1 <- a1
v2 <- a2
...
vn <- an
return (f v1 v2 ... vn)
Evaluates each ai in turn, save value in vi vi <- is optional if you don’t want to save returns value of (f v1 v2 ... vn)
do could end with calling another function that has a return
CPSC 312 — Lecture 10 4 / 5
©D. Poole 2019
Input-Output (see IOAdder2.hs)
IO t is a type for input and output type IO t = World -> (t,World)
where World contains information about state of world.
do v1 <- a1 ...
vn <- an
return (f v1 ... vn)
Each ai is of type IO ti for some type ti
vi is of type ti
ai gets world from ai−1, gives value to vi and world to ai+1
Type of do expression is IO t where t is return type of f
To define a new value use
let v = exp
where type of v is type of exp
CPSC 312 — Lecture 10 5 / 5
©D. Poole 2019