CSE341: Programming Languages��Section 4

​

Spring 2023

CSE 341: Programming Languages

Reminders

• Homework 3 due Tuesday; Midterm is the following Monday
• Check the style guide on the course website
• Anonymous functions and higher-order functions
• Avoid unnecessary function wrappings
• fun xs -> List.length xs (* Bad style *)
• List.length

Harder to see with currying:

• 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

2

Today’s Agenda

• Currying
• Revisit map, filter, and fold practice
• Mutual Recursion
• Higher-order function practice [old midterm problems]

CSE 341: Programming Languages

3

Currying

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

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 xs =

match xs with

[] -> acc

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

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

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

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

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

Currying

Let’s practice! Currying on Worksheet

Mutual Recursion

CSE 341: Programming Languages

9

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

10

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'

Defining higher-order functions

You too can define useful higher-order functions

• Often have polymorphic types
• Often over recursive data structures (may or may not be lists)

​

Questions from old midterms are good practice and instructive…