Lecture 9: More Pattern Matching, Currying --- :::warning Announcements - **Please sit in the first 2 rows of the room**. - `A3: Interp` late deadline tomorrow - Quiz 1 Thursday - Logistics page [here](https://cs.wellesley.edu/~cs251/f25/notes/quiz1.html), including practice quiz. - Next help hours: - Mine 6:30-8:30pm tonight, L037 - Grace's 1-2pm Wednesday, Zoom - `A4: Static Types` out tomorrow, not due until Thursday 10/16 ::: :::success Agenda for today - Continuing pattern matching - Evaluation rules, type checking - HOFs in OCaml - Group exercise: pattern matching + HOFs - Currying: _the one weird trick OCaml loves_ - Every function takes exactly one argument - (next time) Group exercise: revisit any, all - (next time) Exceptions ::: :::info A general note: for the remainder of the course, the recommended (free, online) textbook is a great resource: [Functional Programming in OCaml](https://www.cs.cornell.edu/courses/cs3110/2020fa/textbook/) by Michael R. Clarkson et al. ::: --- # Pattern Matching and More on Types Recall that patterns are used to create bindings: ```ocaml let P = e1 in e2 ;; ``` Basic let bindings have the simplest pattern: a variable. That is, ```ocaml let x = 1 in (x + 2) ``` Binds the variable `x` in the pattern `x` to the value 1, and uses that updated environment in the body `(x + 2)`. OCaml also has more general match statements. These are one of the core features of OCaml; they are extremely powerful (and fun)! The general patterns have the form: ```ocaml match e1 with | P1 -> e2 | P2 -> e3 ``` Patterns are not expressions, even though they look a lot like them. Patterns describe the shape of data rather than compute values. They are used for matching and to bind local variables within each branch/arm when they do match. ## Evaluation rules for pattern matching :::info `match e with P1 -> e1 | ... | PN -> eN` - Evaluate `e` to some value, which might be an empty constructor `C` or a constructor with some data `C v` - Find the pattern `Pi` made with constructor `C`. - Create local bindings - `C` matching `C` creates no bindings. For example, for lists, in a match case `| [] -> 0`, the empty list `[]` creates no bindings in the branch/arm body (here, `0`). - `C v` matching `C x` creates `x` bound to `v`. For example, `|x::xs -> ...` matches on the constructor `::` (the list cons constructor) and binds `x` to the head of the list and `xs` to the tail of the list in the branch/arm body (`...`). - `C(v1,...,vn)` matching `C(x1,...,xn)` creates `x1` bound to `v1`, ... , `xn` bound to `vn` - Evaluate the corresponding `ei` using these local bindings to produce an overall result ::: ### Wildcards in pattern matching The wildcard, `_`, matches on anything. :::success How is that different, than, from a variable (e.g., `x`), that also matches on anything? ::: :::spoiler Think, then click! A variable pattern binds what is matched to that variable. A wildcard pattern does not create a binding. ::: ### Type checking match expressions. You can think of type checking `match` expressions as being a generalization of `if`: every branch must have the same result type. :::info As a reminder, OCaml *does not* allow different types in an `if`, for example, `if true then 0 else ""` produces an error. Similarly, all branch/match arms must produce the same type. ::: We also have the requirement that every variant matches one branch (though we can have default patterns, that match every variant). # HOFs in OCaml Last class, you wrote a tail-recursive list sum. An even better was to do this would be to use a HOF! In OCaml, the syntax for an anonymous function is `fun <arg> -> <body>`. For example: ```ocaml let sum_list_fold_anon lst = List.fold_left (fun acc x -> acc + x) 0 lst ``` Like in Racket, we can also be more concise, and pass a function directly. However, with infix operators, we'd get a syntax error by default: ```ocaml let sum_list_fold_op lst = List.fold_left + 0 lst File "list_patterns.ml", line 17, characters 2-16: 17 | List.fold_left + 0 lst ^^^^^^^^^^^^^^ Error: This expression has type ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a but an expression was expected of type int ``` But we can use the operator as a normal function by passing: ```ocaml let sum_list_fold_op lst = List.fold_left ( + ) 0 lst ``` # Group exercise: 3-part tree sums :::success Check with Alexa before your group moves on to the next part! 1. Part 1: Define a variant data type for a binary tree where `Node`s have `int` data and a left and right node. Write a function to `sum` the nodes in the tree. 2. Part 2: Modify your definitions such that the each node of the tree has an *optional* integer value. 3. Part 3: Modify your definitions such that the each node of the tree has a non-optional int value, but a *list* of children instead of just 2. Use HOFs to your advantage. ::: :::spoiler Think, then click! ```ocaml (* Part 1: define a variant data type for a binary tree where Nodes have int data and a left and right node. *) type tree1 = | Empty1 | Node1 of int * tree1 * tree1 let rec sum_tree1 t = match t with | Empty1 -> 0 | Node1 (v, left, right) -> v + sum_tree1 left + sum_tree1 right (* Part 2: modify your definitions such that the each node of the tree has an *optional* integer value *) type tree2 = | Empty2 | Node2 of int option * tree2 * tree2 let rec sum_tree2 t = match t with | Empty2 -> 0 | Node2 (Some v, left, right) -> v + sum_tree2 left + sum_tree2 right | Node2 (None, left, right) -> sum_tree2 left + sum_tree2 right (* Part 3: modify your definitions such that the each node of the tree has a non-optional int value, but a *list* of children instead of just 2 *) type tree3 = | Empty3 | Node3 of int * tree3 list let rec sum_tree3 t = match t with | Empty3 -> 0 | Node3 (v, children) -> v + List.fold_left (fun acc child -> acc + sum_tree3 child) 0 children let t1 = Node1 (1, Node1 (2, Empty1, Empty1), Node1 (3, Empty1, Empty1)) let t2 = Node2 ((Some 1), Node2 (None, Empty2, Empty2), Node2 ((Some 3), Empty2, Empty2)) let t3 = Node3 (1, [ Node3 (2, []); Node3 (3, []); Node3 (4, []) ]) ``` ::: ----- # Currying ## One weird trick: OCaml functions only take one (1!) argument! 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 function types with multiple args has multiple arrows, e.g., `int -> int -> int` 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**! ::: OCaml functions take a single-argument (e.g., all functions!) *appear to* take multiple arguments as *syntactic sugar*. Where you write `let f x y = ...`, this is a _curried_ functions. In short, a curried functions define single-argument functions that return other single-argument functions! The name “currying” is after logician Haskell Curry. ### Example of currying ```ocaml let sorted3 = fun x -> fun y -> fun z -> z >= y && y >= x let t = ((sorted3 1) 2) 3 ``` Calling `(sorted3 1)` 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. ::: ```ocaml (* 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 ``` ### 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` ```ocaml 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, partial evaluation Let's consider the defintiion of `List.fold_left` from the OCaml standard library: ```ocaml 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` ```ocaml 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`! ```ocaml let sum_list_fold_op_best = fold_left (+) 0 ``` ```ocaml utop # sum_list_fold_op_best ;; - : int list -> int = <fun> utop # sum_list_fold_op_best [1; 2; 3];; - : int = 6 ``` This idea, that it works to pass "too few" arguments, is the idea of ==partial evaluation==! :::info In a language with currying, when we pass "too few" arguments, we get back a usable a function value rather than an error. Cool! ::: Callers can intentionally provide "too few" arguments to get back a closure "waiting for" the remaining arguments. - Can be very useful/lead to beautiful code! - Some restrictions when used with polymorphic types. For example, we can partially evaluated `sorted3` with passing `0` twice: ```ocaml utop # let is_positive = sorted3_short 0 0;; val is_positive : int -> bool = <fun> ``` And we get back a function, here bound to `is_positive`, that is still "waiting on" the final argument. ---- # Group exercise: write `any` and `all` using currying :::success 1. Consider our `any` function from Homework 2: return true iff there exists some element 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: 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`). ::: We'll cover this next class!