:::warning
Announcements
- Quiz 1 grades released
- A4 due Thursday
- Help hours 3:45-5:15pm here
:::

:::success
Agenda for today
- Quiz 1 discussion, what happens when
- Currying: _the one weird trick_
- Every function takes exactly one argument
- Group exercise: revisit any, all
- (Next time)Exceptions, mutation
:::

# Quiz 1: summary

I wanted to go over a question that was frequently missed on the quiz: the `choose` problem.
This gets at the "what happens when" question: in that it's important to remember that function arguments are evaluated (to values) *before* the a function call/application.

E.g., in wanting to support the example:

(choose 
  (let ([x (+ 1 2)])
    (print "hello")
    x)
  (let ([y (+ 2 3)])
    (print "world")
    y))

as

  (define (choose option1 option2)
          (if (random-bool) option1 option2))

The problem with this approach is that **the function application** starting at line 1 requires that both `let` statements be evaluated, including *both* print statements. We only want a single print statement.

# Currying: recall from last time

## The truth about functions

You may not have noticed, but there is something a bit odd about how we called `List.fold_left`: we passed the arguments with spaces in between, but no commas. Isn't it also a bit strange that the syntax for tuples `(a, b, c)`, is the same syntax as tuples? Isn't that odd?

The truth is: this whole time, I've been *lying to you*. (In my defense: almost everyone who teaches OCaml tells the same lie!)

:::warning
**The lie is that OCaml functions can take multiple arguments.** In actuality, every OCaml function only takes **a single argument**!
:::

There are two ways functions that OCaml functions take a single-argument (e.g., all functions!) *appear to* take multiple arguments:
1. Earlier functions we wrote, with commas, like `max (1, 2)`, actually took a single argument of type *tuple*.
2. `List.filter` and `List.map` are _curried_ functions: in short, they define single-argument functions that return other single-argument functions!

In OCaml, every function takes **exactly one argument**! This is an elegant, compositional design that also has built-in syntactic support!

## More on option 1: tuples as arguments

Consider the similarity between tuples and the comma function syntax:

(* Recall that a pair is a 2-tuple. We can pattern match in a let *)
(* Example: tuple with 2 ints , sum them *)
let sum_pair p = let (x, y) = p in x + y

We could have written this as:

let sum_pair_sugar (x, y) = x + y

Which we can now see is really that `sum_pair_sugar` takes in a single argument, a tuple, that then binds `x` and `y` to the first and second element of the tuple.

## More on option 2: currying

The other way to pretend to have multi-argument functions: Take one argument and return a function that takes another argument and ...

This is called “currying” after logician Haskell Curry.

**Currying** is the more common, preferred way to write OCaml code. We didn't start with it, because the function types are more complicated, but it is what you should default to using moving forward.

### Example of currying

let sorted3 = fun x -> fun y -> fun z -> 
                z >= y && y >= x
let t = ((sorted3 1) 2) 3

Calling `(sorted3 7)` returns a closure with:
- Code `fun y -> fun z -> z >= y && y >= x`
- Environment maps `x` to `1`
Calling that closure with `2` returns a closure with:
- Code `fun z -> z >= y && y >= x`
- Environment maps `x` to `1`, `y` to `2`
Calling that closure with `3` returns `true`

In general, `e1 e2 e3 e4 ...`, means `(…((e1 e2) e3) e4)`
So instead of `((sorted3 1) 2) 3`, can write ` sorted3 1 2 3`

Callers can just think “multi-argument function with spaces instead of a tuple expression”

:::info
Note that this is different than tupling; caller and callee must use same technique (both must use a tuple, or both must use spaces that are desugared to currying).

See the [textbook chapter on Currying](https://cs3110.github.io/textbook/chapters/hop/currying.html?highlight=currying) for converting between the two strategies.
:::

(* Sorted 3 example *)
let sorted3 = fun x -> fun y -> fun z ->
  x <= y && y <= z
let t = ((sorted3 1) 2) 3

let sorted3_spaces_fun = fun x y z ->
  x <= y && y <= z
let _ = sorted3_spaces_fun 1 2 3

let sorted3 = fun x -> fun y -> fun z ->
  x <= y && y <= z

let sorted3_short x y z = z >= y && y >= x

let is_positive = sorted3_short 0 0

### Currying as syntactic sugar

In general, `let [rec] f p1 p2 p3 ... = e` means `let [rec] f p1 = fun p2 -> fun p3 -> … -> e`. (Note that here, you should interpret `[rec]` as meaning either `rec` is there syntactically, or it is not there.)
So can just write `let sorted3 x y z = z >=y && y >= x`

let sorted3 = fun x -> fun y -> fun z -> 
                z >= y && y >= x

let sorted3 x y z = z >= y && y >= x
let t = sorted3 1 2 3

## Curried fold

Let's consider the defintiion of `List.fold_left` from the OCaml standard library:

let rec fold_left f acc xs =
  match xs with
  | [] -> acc
  | x :: xs' -> fold_left f (f acc x) xs'

Consisder again our function from last week to sum a list of integers using `fold_left`

let sum_list_fold_op lst =
  List.fold_left ( + ) 0 lst

As we now know, `fold_left (fun acc x -> acc + x) 0`
evaluates to a closure that given `xs`, evaluates the match-expression with `f` bound to `(fun acc x -> acc + x)` and `acc` bound to `0`.

So we can leave off the `xs`!

let sum_list_fold_op_best = fold_left (+) 0

utop # sum_list_fold_op_best ;;
- : int list -> int = <fun>
utop # sum_list_fold_op_best [1; 2; 3];;
- : int = 6

## Partial evaluation

So far, we saw currying used to simulate multiple arguments.

But we also saw that it worked to pass "too few" arguments: we'd still get back a function value! Callers can intentionally provide "too few" arguments, to get back a closure "waiting for" the remaining arguments.
- This is called _partial evaluation_.
- Very convenient, but some restrictions when used with polymorphic types.

For example, we can partially evaluated `sorted3` with passing `1`:

utop # let sorted3_x_is_1 = sorted3_cur_ex 1 ;;
val sorted3_x_is_1 : int -> int -> bool = <fun>

And we get back a function, here bound to `sorted3_x_is_1`, that is still "waiting on" the second two arguments.

----

# Group exercise: write `any` and `all` using currying

(*
1. Consider our "any" function from Homework 2 using curring.
Updated definition:
Return true iff there exists some element e where (p e) is true.
  a. First, what should the curried type in OCaml be?
  b. Write a curried implementation (use a HOF)

2. Consider our "all" function from Homework 2 using curring.
Updated definition:
Return true iff for all elements, (p e) is true.
  a. First, what should the curried type in OCaml be?
  b. Write a curried implementation (without using "any")
*)

let any p = List.fold_left (fun acc x -> acc || p x) false
(* in the library as: List.exists *)


let all p = List.fold_left (fun acc x -> acc && p x) true
(* in the library as: List.for_all *)


let has_zero = List.exists (fun x -> x = 0)
let all_zeros =  List.for_all (fun x -> x = 0)