CSE341: Programming Languages��Section 4

​

Autumn 2021

CSE 341: Programming Languages

Reminders

• Homework 1 grades are out
• Check our feedback
• Make sure to implement feedback in next HW
• Homework 2 due tomorrow

CSE 341: Programming Languages

2

Reminders

• Homework 3 due next Friday, 10/29 at 5 PM PST
• Check the style guide !
• A lot of anonymous functions and higher-order functions
• Avoid unnecessary function wrappings
• fun ls -> List.length ls (* Bad style *)
• List.length

​

• fun x y -> g (x + 1) y (* Unnecessary argument y *)
• (fun x -> g (x + 1))
• let f x y = g (x + 1) y
• let f x = g (x + 1)

CSE 341: Programming Languages

3

Today’s Agenda

• Higher-order functions: map and filter
• Currying
• Mutual Recursion (maybe)

CSE 341: Programming Languages

4

Higher-order Functions

CSE 341: Programming Languages

A function that takes or returns functions is called higher-order.

Two useful Higher-order functions: map

CSE 341: Programming Languages

(*

(‘a -> ‘b) * ‘a list -> ‘b list

*)

let rec map (f, xs) =

match xs with

| [] -> []

| x :: xs' -> (f x) :: (map (f,xs'))

• Use map when you want to create a new list with an operation applied to each element

Two useful Higher-order functions: map

CSE 341: Programming Languages

let rec map (f, xs) =

match xs with

| [] -> []

| x :: xs' -> (f x) :: (map (f, xs'))

(* map example *)

let add_one x = x + 1

​

let add_one_to_all xs = map (add_one, xs)

Two useful Higher-order functions: filter

CSE 341: Programming Languages

• Use filter when you want a new list where all the elements satisfy a given condition

(*

(‘a -> bool) * ‘a list -> ‘a list

*)

let rec filter (f, xs) =

match xs with

| [] -> []

| x :: xs' -> if f x

then x :: filter (f, xs')

else filter (f, xs')

Two useful Higher-order functions: filter

CSE 341: Programming Languages

let rec filter (f, xs) =

match xs with

| [] -> []

| x :: xs' -> if f x

then x :: filter (f, xs')

else filter (f, xs')

(* filter example *)

let is_nonzero x = (x <> 0)

​

let remove_zeros xs = filter (is_nonzero, xs)

Anonymous Functions

CSE 341: Programming Languages

let nums = [1;2;3]

​

let double x = 2 * x

​

let doubled_list1 =

map (double, nums) (* = [2;4;6] *)

​

​

let doubled_list2 =

map ((fun x -> 2 * x), nums) (* = [2;4;6] *)

Two useful Higher-order functions:

Map and Filter

CSE 341: Programming Languages

let rec map (f, xs) =

match xs with

| [] -> []

| x :: xs' -> (f x) :: (map (f, xs'))

let rec filter (f, xs) =

match xs with

| [] -> []

| x :: xs' -> if f x

then x :: filter (f,xs')

else filter (f,xs')

(* map example *)

let add_one x =

x + 1

​

let add_one_to_all xs =

map (add_one, xs)

​

​

(* filter example *)

let is_nonzero x =

x <> 0

​

let remove_zeros xs = _ filter (is_nonzero, xs)

Currying

• Have a function take the (conceptually) first argument and return another function that takes the (conceptually) second argument and so on.

Functions returning functions

CSE 341: Programming Languages

let double_or_triple f =

if f 7

then fun x -> 2 * x

else fun x -> 3 * x

let roundabout_mystery1 = double_or_triple (fun x -> x - 3 = 4)

​

let roundabout_mystery2 = (double_or_triple (fun x -> x = 42)) 3

​

Currying

Recall every OCaml function takes exactly one argument

Without Currying:

let sub (x,y) = x - y

​

​

�With Currying:

let sub x y = x - y

​

​

​

sub

x

y

x - y

sub

x

sub x

y

x - y

Currying–reading function types

​

​

Type: int -> int -> int -> int

Type: int -> (int -> (int -> int))

let curried_fun x y z =

x + y + z

Currying

Currying is particularly convenient for creating similar functions with iterators.

let rec fold f acc l =

match l with

[] -> acc

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

Now we could use this fold to define a function that sums a list elements like this:

let sum1 xs = fold (fun x y -> x+y) 0 xs

But that is unnecessarily complicated compared to just using partial application:

let sum2 = fold (fun x y -> x+y) 0

Currying

Let’s practice! Currying on Worksheet

Mutual Recursion

CSE 341: Programming Languages

18

let rec start xs =

match xs with

| [] -> true

| i::xs' -> if i mod 2 = 0 then saw_even xs' else saw_odd xs'

and saw_even xs =

match xs with

| [] -> true

| i::xs' -> i mod 2 <> 0 && saw_odd xs'

and saw_odd xs =

match xs with

| [] -> true

| i::xs' -> i mod 2 = 0 && saw_even xs'

​

Mutual Recursion

CSE 341: Programming Languages

19

let saw_even2 f xs =

match xs with

| [] -> true

| i::xs' -> i mod 2 <> 0 && f xs'

let rec saw_odd2 xs =

match xs with

| [] -> true

| i::xs' -> i mod 2 = 0 && saw_even2 saw_odd2 xs'

let start2 xs =

match xs with

| [] -> true

| i::xs' -> if i mod 2 = 0 then saw_even2 saw_odd2 xs' else saw_odd2 xs'