Lecture 06

​

More Pattern Matching

Programming Languages

UW CSE 341 - Autumn 2022

Updates

• Homework 2 due Friday at 5PM!
• Audio didn’t record friday (bummer), but alternative posted on web.
• I’m back :D

Recursive variant types

Concise, elegant way to define different tree types

• Nodes are tagged with a constructor with children for carried data

So functions over expr will typically

use recursion over the tree structure

• See code examples

type expr =

| Constant of int

| Negate of expr

| Add of expr * expr

| Mul of expr * expr

​

Add(Constant 19,

Negate(Constant 4)

Defining our own option types

Using what we already know:

​

Using new feature of defining our own type constructor

​

Exactly how “built-in” options are defined (just in standard library):

​

type int_option = NoInt | OneInt of int

type 'a myoption = MyNone | MySome of 'a

​

type 'a option = None | Some of 'a

​

So use pattern-matching!

• None and Some are (just) constructors for 'a option

​

• Build with constructors and use with match expressions
• Do not use Option.get and Option.is_some any more (!)
• Get the advantages of variant types and pattern matching

Now lists

Can use the same features and self-reference for our own list type constructor

Build with constructors:

Use with match expressions:

type 'a my_list = Empty | Cons of 'a * 'a my_list

​

let xs = Cons(3, Cons (4, Cons (5, Empty)))

let ss = Cons("hi", Cons("bye", Empty))

let rec length xs =

match xs with

| Empty -> 0

| Cons(x,xs’) -> 1 + length xs’

​

OCaml’s built-in lists

• Could have done exactly what we just did
• But instead used special syntax
• Constructors are [] and :: with :: written infix
• And/but yes (!!) use match expressions to use lists, not List.hd, List.tl and e=[] anymore (!!)

let rec length xs =

match xs with

| [] -> 0

| x::xs’ -> 1 + length xs’

​

Why List.hd and List.tl?

• Occasionally convenient
• Including for passing functions to other functions (next week)
• A stepping stone for us to the more elegant and less error-prone approach (match expressions warn on missing cases!)
• Again, do not use these functions on remaining homeworks
• Easy to define:

let hd xs =

match xs with

| [] -> failwith "list empty"

| x::xs’ -> x

​

let isEmpty xs =

match xs with

| [] -> true

| x::xs’ -> false

​

How languages define variant types

• OCaml built powerful pattern-matching into the language and used it as the fundamental primitive to use one-of types

​

• Other languages make other choices. For example OCaml could have:
• Kept variant type definitions as-is
• Had them automatically introduce functions like isEmpty and hd

More pattern-matching

OCaml also has pattern-matching for each-of types

• Pattern (x,y,z) matches triples (v1,v2,v3)
• Similar for any width tuple, naturally
• Similar patterns {f1=x1; …; fn=xn} for records

Useful for nested patterns (next lecture)

But also useful to make let expressions more powerful

Do NOT do this

One-branch match expressions make semantic sense but are BAD / SILLY style

​

let sum_triple tr =

match tr with

| (x,y,z) -> x+y+z

​

​

New feature

Let expression syntax is actually let p = e1 in e2

• Where p is a pattern

(Top-level let bindings can also do this)

Great for extracting multiple pieces of data at once

• No more need for fst, snd, fst3, snd3, thd3, ...

​

let sum_triple tr =

let (x,y,z) = tr in

x+y+z

​

​

Another new feature

Function arguments can also use patterns

• Function call semantics: pattern-match the argument, extracting data for body

let sum_triple tr =

let (x,y,z) = tr in

x+y+z

​

​

let sum_triple (x,y,z) =

x+y+z

​

​

let ten = sum_triple (5,2,3)

Hmm… 😊

Compare:

A function that takes a triple and sums its int components:

​

A function that takes three ints and sums them:

​

let sum_triple (x,y,z) =

x+y+z

let sum_triple (x,y,z) =

x+y+z

​

​

See the difference? (Me neither.) 😊🎉😊🎉😊

The truth about functions

In OCaml, every function takes exactly one argument

We can simulate multiple arguments with tuples and tuple-patterns

• Elegant, compositional design

Enables sometimes-convenient things

• Return a tuple from one function and pass it like multiple arguments to another

Next unit will see a different and more common way to simulate multiple arguments that also has built-in syntactic support