cse130
file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
32 of 46
2/2/21, 8:56 AM
e0, e1, e2 :: Expr
e0 = Add (Num 4.0) (Num 2.9)
e1 = Sub (Num 3.78) (Num 5.92)
e2 = Mul e0 e1
EXERCISE: Expression Evaluator
Write a function to evaluate an expression.
— >>> eval (Add (Num 4.0) (Num 2.9))
MIDTERM ON
am
Tue
— 6.9
eval :: Expr -> Float
eval e = ???
218 Monday 218
219
data pr quay g¦Ì t 8am
Recursion is…
MONDAY
cse130
file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
Building solutions for big problems from solutions for sub-problems
Base case: what is the simplest version of this problem and how do I solve it?
Inductive strategy: how do I break down this problem into sub-problems?
1 2,3
Lists aren¡¯t built-in! They are an algebraic data type like any other:
Lists
data List
= Nil — ^ base constructor
| Cons Int List — ^ inductive constructor
Iff
or ti
Inductive case: how do I solve the problem given the solutions for
subproblems?
List [1, 2, 3] is represented as Cons 1 (Cons 2 (Cons 3 Nil)) D
Built-in list constructors [] and (:) are just fancy syntax for Nil and Cons
23c
Functions on lists follow the same general strategy:
I
Conseccons2cons3nilD
33 of 46 2/2/21, 8:56 AM
O D
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
length :: List -> Int
length Nil = 0 — base case length (Cons _ xs) = 1 + length xs — inductive case
EXERCISE: Appending Lists
What is the right inductive strategy for appending two lists?
— >>> append (Cons 1 (Cons 2 (Cons 3 Nil))) (Cons 4 (Cons 5 (Cons
6 Nil)))
— (Cons 1 (Cons 2 (Cons 3 (Cons 4 (Cons 5 (Cons 6 Nil))))))
append :: List -> List -> List
append xs ys = ??
34 of 46 2/2/21, 8:56 AM
cse130
file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
Trees
Lists are unary trees with elements stored in the nodes: has one child
a
NO CHILDRE
Lists are unary trees
data List = Nil | Cons Int List
How do we represent binary trees with elements stored in the nodes? 0
35 of 46
let
2/2/21, 8:56 AM
cse130
I fiIle:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes… OtO
s
r
1
oo
Binary trees with data at nodes
O
O
O
data Tree t
Node butfreettifreet
I Leaf
QUIZ: Binary trees I
What is a Haskell datatype for binary trees with elements stored in the nodes?
36 of 46 2/2/21, 8:56 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
Binary trees with data at nodes
(A) data Tree = Leaf | Node Int Tree
(B) data Tree = Leaf | Node Tree Tree
(C) data Tree = Leaf | Node Int Tree Tree
(D) data Tree = Leaf Int | Node Tree Tree
(E) data Tree = Leaf Int | Node Int Tree Tree
37 of 46 2/2/21, 8:56 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
Binary trees with data at nodes
data Tree = Leaf | Node Int Tree Tree
t1234 = Node 1
(Node 2 (Node 3 Leaf Leaf) Leaf)
(Node 4 Leaf Leaf)
Functions on trees
38 of 46 2/2/21, 8:56 AM
cse130
file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
depth :: Tree -> Int
depth t = ??
QUIZ: Binary trees II
What is a Haskell datatype for binary trees with elements stored in the leaves?
x x
Binary trees with data at leaves
x
(A) data Tree = Leaf | Node Int Tree 39 of 46 x
2/2/21, 8:56 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
(B) data Tree = Leaf | Node Tree Tree
(C) data Tree = Leaf | Node Int Tree Tree i (D) data Tree = Leaf Int | Node Tree Tree
too
(E) data Tree = Leaf Int | Node Int Tree Tree
data Tree = Leaf Int | Node Tree Tree
t12345 = Node
(Node (Node (Leaf 1) (Leaf 2)) (Leaf 3))
(Node (Leaf 4) (Leaf 5))
treemay
40 of 46 agree 2/2/21, 8:56 AM
wa
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
Why use Recursion?
1. Often far simpler and cleaner than loops But not always…
2. Structure often forced by recursive data
O
3. Forces you to factor code into reusable units (recursive functions)
maplredufjg.at Why Onot use Recursion?
1. Slow
2. Can cause stack overflow
taitrecarynon HI
festfoop
41 of 46
2/2/21, 8:56 AM
cse130
file:///Users/rjhala/teaching/130-wi21/docs/lectures/03-datatypes…
42 of 46
2/2/21, 8:56 AM
Example: factorial
fac :: Int -> Int
fac n
|n<=1 =1
| otherwise = n * fac (n - 1)
Lets see how fac 4 is evaluated:
==> <4 *
i
— recursively call `fact 3`
— recursively call `fact 2`
— recursively call `fact 1`
— multiply 2 to result
— multiply 3 to result
— multiply 4 to result
==> <4 *<3 ==> <4 *<3 ==> <4 *<3 ==> <4 *<3 ==> <4 *6> ==> 24
*
* <2 *
* 2>>
Each function call <> allocates a frame on the call stack expensive
the stack has a finite size
Can we do recursion without allocating stack frames?