CSE 341: Section 3

OCaml Pattern Matching and Tail Recursion

Reminders

• Homework 2 due tomorrow at 5 pm
• Midterm on Wednesday, 10/28
• That’s in less than 2 weeks!!

Agenda

• Variants & Records
• Pattern Matching
• Tail Recursion

Variants & Records

What is the difference?

Records: a new way to build each-of types

• Named types and named fields
• Similar to tuples

Variants: a new way to build custom one-of types

• Named types
• An enumeration is the simplest version of variants

What variable belongs to which type definition?

1. ​

b.

c.

What variable belongs to which type definition?

• Variant

b. Record

c. Variant

Pattern Matching

Why Pattern Match

Used to destruct variants

Why Pattern Match

Also a cleaner representation of different cases/patterns as opposed to if-else branches

Exercise - Problem 2 & 3

Create an appropriate pattern for the given types.

Use pattern matching to implement the remaining functions according to the spec.

Tail Recursion

Making functions tail-recursive

Sometimes we can rewrite our algorithm to be tail-recursive

​

​

​

​

Sometimes we can’t easily/profitably do so:

• Example: processing a tree (two recursive calls can’t both be tail calls)
• Example: if order matters in a resulting list

let factorial n =

let rec loop (n,acc) = if n=0 then acc else loop (n-1,acc*n) in

loop (n,1)

let x = factorial 3

Methodology

There is a methodology to guide the transformation to a tail-recursive function:

• Create a helper function that takes an accumulator
• Old base case becomes initial accumulator
• New base case becomes final accumulator

Methodology

1. Create a helper function that takes an accumulator
2. Old base case becomes initial accumulator
3. New base case becomes final accumulator

1

Methodology

• Create a helper function that takes an accumulator
• Old base case becomes initial accumulator
• New base case becomes final accumulator

1

2

Methodology

• Create a helper function that takes an accumulator
• Old base case becomes initial accumulator
• New base case becomes final accumulator

1

2

3

Tail Recursion

type expr =

| Constant of int

| Negate of expr

| Add of expr * expr

| Mul of expr * expr

let rec eval e =

match e with

| Constant i -> i

| Negate e1 -> - (eval e1)

| Add (e1, e2) -> (eval e1) + (eval e2)

| Mul (e1, e2) -> (eval e1) * (eval e2)

Why shouldn't we try to make eval tail-recursive?

​

​

Summary: Tail Recursion

A call that will be the caller’s answer “as is” is called a tail call

A recursive function where all recursive calls are tail calls is called “tail recursive”

Exercise - Problem 3

Use tail recursion to implement the following functions according to the spec.