CSE 341�Section 4

Higher-Order Functions

​

Winter 2021

Today’s Agenda

• HWs
• Parameterized Variant Types
• Anonymous Functions
• Higher-Order Functions

CSE 341: Programming Languages

2

Homework 1 Recap &

Homework 2 due Friday 5 pm

• From now on, we’ll only take off boolean zen points for
• if e then true else false, if e then false else true,�e = true, e = false
• Unnecessary parentheses: eg, foo (x) (y) (z)
• Check style guide!!!!!
• Do not accept submissions after 2 late days
• Look at provided tests and lecture codes
• Include comment (problem #) for each function and tests

Parameterized Variants

​

• Worksheet Q1: Consider the following variant type binding that represents a binary tree:

type ('a, 'b) tree = � Leaf of 'a �| Node of 'b * ('a, 'b) tree � * ('a, 'b) tree

What expressions could this variant type support, and what are their types?

Anonymous Functions

fun pattern -> expression

• An expression that creates a new function with no name.
• Usually used as an argument to a higher-order function.
• Almost equivalent to the following:

let name pattern = expression in name

What’s the difference? What can you do with one that you can’t do with the other?

• The difference is that anonymous functions cannot be recursive!!!

Unnecessary Function Wrapping

What's the difference between the following two expressions?

(fun xs -> List.tl xs) vs. List.tl�

STYLE POINTS!

• Other than style, these two expressions result in the exact same thing.
• However, one creates an unnecessary function to wrap tl.
• This is very similar to this style issue:

(if ex then true else false) vs. ex

Let’s practice! (Worksheet Q2 and Q3)

Higher-Order Functions

• Pass functions around like any data
• Closures: functions capture references to their environment
• Lexical scoping: variables are captured at time of creation
• Functions that are no different from any program data.
• An extremely powerful feature! The “defining feature” of functional programming.*

* debatable

Higher-order function idioms

fold, map, filter, etc.

Fold: Returns a “thing” that is the accumulation of the first argument applied to the third argument’s elements stored in the second argument.

let rec fold f a l =

match l with

[] -> a

| h::t -> f (fold f a t) h

Example:

fold (fun a b -> a + b) 0 [1;2;3] = 6

Higher-order function - Fold

let rec fold f a l =

match l with

[] -> a

| h::t -> f (fold f a t) h

• What is the type of fold?

('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

Higher-Order Function - Fold

• In what order does fold process its elements?

Back to front!

• Is there the one true type for a fold function? Why/Why not?

No

Let’s practice! (Worksheet Q5)

Higher-Order Functions

Let’s look at an association list representation of a map and some operations (Emacs)

Association Lists

k1

v1

k2

v2

k3

v3

...

Closure-Based Representation

• The function (map!) returned by add captures:
• the inserted key (k)
• the inserted value (v)
• the original map (m)

Closure-Based Representation

fn =>

...

k1

v1

m

fn =>

...

k2

v2

m’

fn =>

...

k3

v3

m’’

...

Does this look familiar?

Closure-Based Representation

fun ->

...

k1

v1

m

fun ->

...

k2

v2

m’

fun ->

...

k3

v3

m’’

...

k1

v1

k2

v2

k3

v3

...

Benefits of this representation

• Remove is O(1)
• Map is O(1) (kinda!)
• Only ends up transforming values accessed later (emacs)
• Although the result can be more expensive computationally (why?)