cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
let p = Text “Hey there!” incasepof
PText _ -> 1
PHeading _ _ -> 2
PList _ _ -> 3
A. Syntax error B. Type error C. Paragraph D. Int
E. Paragraph -> Int
Building data types
22 of 46 2/2/21, 8:56 AM
cse130
file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
23 of 46
Zero
one
F
T2 [done] T Cartesian product of two sets: v(T) = v(T1) × v(T2)
T and Tz
Three key ways to build complex types/values:
1. Product types (each-of): a value of T contains a value of T1 and a value of
2. Sum types (one-of): a value of T contains a value of T1 or a value of T2 [done]
Union (sum) of two sets: v(T) = v(T1) ! v(T2)
3. Recursive types: a value of T contains a sub-value of the same type T
Recursive types
Let’s define natural numbers from scratch: data Nat = ???
O
T
T
inside
T
or
Tz
too 2/2/21, 8:56 AM
three
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
data Nat = Zero | NSucecxNtat A Nat value is:
either an empty box labeled Zero
or a box labeled Succ with another Nat in it!
Some Nat values:
Zero
Succ Zero
Succ (Succ Zero)
Succ (Succ (Succ Zero)) — 3 …
— 0 — 1 — 2
Deo
ITIS
Functions on recursive types
24 of 46 2/2/21, 8:56 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
Recursive code mirrors recursive data
1. Recursive type as a parameter
data Nat = Zero — base constructor
| Succ Nat — inductive constructor
Step 1: add a pattern per constructor
toInt :: Nat -> Int
toInt Zero = … — base case toInt (Succ n) = … — inductive case
— (recursive call goes here)
Step 2: fill in base case:
toInt :: Nat -> Int
toInt Zero = 0 — base case toInt (Succ n) = … — inductive case
— (recursive call goes here)
Step 2: fill in inductive case using a recursive call:
toInt :: Nat -> Int
toInt Zero = 0 — base case toInt (Succ n) = 1 + toInt n — inductive case
25 of 46 2/2/21, 8:56 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
QUIZ
data Nat Zero 1 Sacc Nat
aka Next let foo i = if i <= 0 then Zero else SDucc (foo (i - 1))
infoo2
A. Syntax error
B. Type error
C. 2
D. Succ Zero
E. Succ (Succ Zero)
What does this evaluate to?
2. Recursive type as a result
26 of 46 2/2/21, 8:56 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes...
data Nat = Zero -- base constructor
| Succ Nat -- inductive constructor
fromInt :: Int -> Nat
fromInt n
|n<=0 = Zero -- base case
| otherwise = Succ (fromInt (n - 1)) -- inductive case
-- (recursive call goes her
e)
EXERCISE: Putting the two together
data NOat = Zero -- base constructor
| Succ Nat -- inductive constructor
add :: NatD
-> Nat -> Nat
add n m = ???
sub :: Nat -> Nat -> Nat
sub n m = ???
27 of 46 2/2/21, 8:56 AM
add
cse130 add file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
EXE3RCISE: Putting the two together data Nat = Zero — base constructor
| Succ Nat — inductive constructor
add :: Nat -> Nat -> Nat
add n m = ???
28 of 46 2/2/21, 8:56 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
data Nat = Zero — base constructor
| Succ Nat — inductive constructor
add :: Nat -> Nat -> Nat
add Zero m = ??? — base case
add (Succ n) m = ??? — inductive case
EXERCISE: Putting the two together
data Nat = Zero — base constructor
| Succ Nat — inductive constructor
sub :: Nat -> Nat -> Nat
sub n m = ???
29 of 46 2/2/21, 8:56 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
sub :: Nat -> Nat -> Nat
sub n Zero = ???
sub Zero _ = ???
sub (Succ n) (Succ m) = ???
— base case 1
— base case 2
— inductive case
Lesson: Recursive code mirrors recursive data
Which of multiple arguments should you recurse on? Key: Pick the right inductive strategy!
(easiest if there is a single argument of course…)
30 of 46 2/2/21, 8:56 AM
cse130
file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
31 of 46
2/2/21, 8:56 AM
Example: Calculator
I want to implement an arithmetic calculator to evaluate expressions like:
Ea
4.0 + 2.9
3.78 – 5.92
(4.0 + 2.9) * (3.78 – 5.92)
What is a Haskell datatype to represent these expressions? data Expr = ???
B Mum Double Mul
sabpq pg.attddpg.PT
data Expr = Num Float
| Add Expr Expr
| Sub Expr Expr
| Mul Expr Expr
We can represent expressions as