:::warning Announcements - Quiz 1 grades almost done - Happy to discuss individual problems at office hours - Assignment 3 due tonight (can resubmit to all 4) - Assignment 4 pair form out ::: :::success Agenda for today - More pattern matching + types - Pattern matching evaluation - More on variants: `Option` - Variant tree exercise - Records, tuples - Currying: _the one weird trick of OCaml functions_ - More on this next time! ::: :::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 most simple 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 kind of look like them. They are used for matching and to bind local variables within each branch/arm when they do match. ## Evaluation rules for pattern matching `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 ### 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). ## Examples of pattern matching ### Pattern matching on lists Pattern matching is the normal ML was to use lists. Let's revisit our prior, natural recursion function: ```ocaml let rec sum_list_before ls = if ls = [] then 0 else (List.hd ls) + sum_list_before (List.tl ls) ``` The pattern matching version ```ocaml (* pattern-matching is the normal ML way to use lists; let's revisit prior functions *) let rec sum_list_pat lst = match lst with | [] -> 0 | x::xs -> x + sum_list_pat xs ``` Though for `length`, what would be a better way, using the functional programming patterns we saw in Racket? Answer: higher-order function! In OCaml, it's called `List.fold_left`. We could rewrite `length` using a higher-order function! We need a way to write anonymous functions. In OCaml, the syntax 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 ``` ### Pattern matching on variants We can also pattern match on variants. #### Simple variants (a la enums) Here is an example of a simple variant with no contained data (similar to enums in other languages you may have seen): ```ocaml type class_year = C2028 | C2027 | C2026 | C2025 let print_year cy = let str = match cy with | C2028 -> "2028" | C2027 -> "2027" | C2026 -> "C2026" | C2025 -> "C2025" in print_endline str ``` We can use this as, for example: ```ocaml utop # #use "02-class-year.ml";; type class_year = C2028 | C2027 | C2026 | C2025 val print_year : class_year -> unit = <fun> utop # print_year C2028 ;; 2028 - : unit = () ``` `unit` is the empty type, with the empty value `()`. It's used here because `print_endline` does not return an actual value, it just has the side effect of printing. #### Option variants Like `plait`, OCaml has a built-in variant type for `Option`. It's defined by OCaml as: ```ocaml type 'a option = | None | Some of 'a ``` :::info Note: built-in OCaml types tend to be lower case and have the type parameter first, e.g., `'a list` and `'a option`. OCaml programmers sometimes pronounce the type variable as Greek letters, e.g., "alpha" in this case. ::: And can be used as, for example: ```ocaml let print_option_int oi = match oi with | None -> print_endline "no int :(" | Some i -> print_endline (string_of_int i) ``` Which we could then call this like so: ```ocaml let test = [None; Some 7; None; Some 2; Some 1] List.map print_option_int test ``` To get result: ```ocaml utop # List.map print_option_int test ;; no int :( 7 no int :( 2 1 ``` :::info **Student question**: why do we need the `None`s? **Answer:** there are many cases where it's natural to have "optional" data: for example, a linked list could have a `next` or could not. OCaml does not have a concept of `null` like C/Java. The optional type serves this purpose. Here, maybe our integer list comes from a user, and `None` corresponds to missing data entries. ::: :::info **Student question**: do the `Some x` values need to be integers? **Answer**: here, yes, because lists must have homogeneous element types in OCaml. To demonstrate this: ```ocaml utop # [None; Some ""; None; Some 2; Some 1] ;; Error: This expression has type int but an expression was expected of type string utop # [None; Some "hi"; Some "bye"] ;; - : string option list = [None; Some "hi"; Some "bye"] utop # [None] ;; - : 'a option list = [None] utop # [] ;; - : 'a list = [] ``` Note trying to mix `string option` and `int option` types fails with a static type error. But we have have a `string option list`. A list with just `None` has a polymorphic `list` type, but OCaml knows it must be an `'a option list` (as oppossed to the empty list, which could be any list type). ::: #### Recursive variants And of course we can pattern match on more complex, recursive variants, like we saw last lecture: ```ocaml (* Define the type MathExpr *) type math_expr = | ENum of int | EAdd of math_expr * math_expr (* Function to evaluate a math expression *) let rec calc expr = match expr with | ENum value -> value | EAdd (x, y) -> (calc x) + (calc y) ``` ## Group exercise: 3-part tree sums 1. Part 1: Define a variant data type for a binary tree where Nodes 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. ```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 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! More on this next time!