:::warning Announcements - Help hours 3:45-5:15pm here - A5 late deadline midnight tomorrow - Quiz 2 next Monday: - Content through Mutation (to be finished today) - A6 out tomorrow - Parts 1 & 2 include Quiz 1 material (4 problems) - Schedule updates ::: :::success Agenda for today - Mutation - Mutable arrays - Loops - Mutation practice problem - Quiz 2 logistics, questions - Start next topic: - Lazy evaluation, thunks ::: # Mutable arrays Arrays in OCaml are similar to primitive arrays in Java or C: they are ordered sequences of elements with constant-time access and mutation. In OCaml, array sizes must be specified at construction and cannot be changed. `array` is a type constructor, used in the same ways as `list`, e.g., `int array`. `[|v1; v2; …; vn|]` is an array literal. Note the vertical bar characters after the open square bracket and before the close square bracket. Otherwise the syntax is identical to list literals. For example: ``` let a = [| 1; 2; 3|] ``` We can access and change array elements with indexing. - `a.(i)` returns the ith element of the array `a`. It throws an exception if `i` is out of bounds. Note: parens needed. - `a.(i) <- v` overwrites the ith element of the array a with a new value `v`. Throws an exception if `i` is out of bounds. `Array.make n d` allocates an array of length `n` where every element is equal to `d`. `Array.length a` returns the length of the array `a`. ### Evaluation and typing rules for `array`s Constructing arrays :::info **Construct with**: `[|v1; v2; …; vn|]` or `Array.make n d` **Type rules** - If `ei : t` for all the `ei`, then ``[|e1; e2; ...; en|] : t array`. - If `d : t` in `Array.make n d`, then the result has type `t array`. **Eval rules** - Evaluate each element to a value. - Allocate new space for an array of length `n`, and store each value in the array at its index. ::: Accessing an element at index :::info **Use with**: `e1.(e2)` **Type rules** - If `e1 : t array` and `e2 : int`, then `e1.(e2) : t`. **Eval rules** - Evaluate `e1` to an array value `v1`. - Evaluate `e2` to an integer `v2`. - If `v2` is not within the bounds of the array (`0` to `n-1`), raise an `Invalid_argument` exception. Otherwise, return the value at index `v2`, ::: Mutating an element at index :::info **Use with**: `e1.(e2) <- e3` **Type rules** - If `e1 : t array` and `e2 : int` and `e3 : t`, then `e1.(e2) <- e3 : unit` **Eval rules** - Evaluate `e1` to an array value `v1`. - Evaluate `e2` to an integer `v2`. - Evaluate `e3` to a value `v3` of type `t`. - If `v2` is not within the bounds of the array (`0` to `n-1`), raise an `Invalid_argument` exception. Otherwise, set the element of `v1` at index `v2` to be `v3`. ::: # Loops OCaml offers several ways to work with arrays. The standard library provides functions like `Array.fold_left`, similar to lists. :::success What type should we expect `Array.fold_left` to have? ::: ```ocaml utop # Array.fold_left ;; - : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a = <fun> ``` `Array.iter` works like map, but it performs side effects instead of returning a new list. :::success What type should we expect `Array.iter` to have? ::: ```ocaml utop # Array.iter ;; - : ('a -> unit) -> 'a array -> unit = <fun> ``` Because `Array.iter` works to perform side effects, the function it takes in first is one that returns `unit` and the overall return type for `iter` is `unit`. We can also explicitly use *loops*, like other less-functional languages you are more familiar with. For example: ``` while e1 do e2 done for x = e1 to e2 do e3 done ``` :star: Note that `for` loop bounds are *inclusive*: `x` starts as `e1` in the first iteration and is `e2` in the last iteration. As explained [in the documentation](https://ocaml.org/docs/loops-recursion), `for` loops are just syntactic sugar for a series of `let` statements. ## Silly loop example Here is a silly example to show loops with less straighforward structure: write a function that adds 1 to just the first multiple of 3 in an OCaml array. ```ocaml (* This version assumes there is at least one multiple *) let change_first_mul3_while1 a = let i = ref 0 in while a.(!i) mod 3 > 0 do i := !i + 1 done; a.(!i) <- a.(!i) + 1 (* This version handles the case where there is no multiple found *) let change_first_mul3_while2 a = let n = Array.length a in let i = ref 0 in while (!i < n) && a.(!i) mod 3 > 0 do i := !i + 1 done; if !i < n then a.(!i) <- a.(!i) + 1; ``` # Group exercise: mutable arrays :::success Warmup question (and interview practice!): you've given a large array of integers, but you know it's already partially sorted. What's the best sorting algorithm to use? Why? ::: Answer: insertion sort, because it's fast (linear time) if the array is already sorted. It also does not require a new array (it can be done in place), for which we (in OCaml) need to use mutable arrays, not lists. :::success Implement insertion sort on a mutable array of intergers in OCaml. :::: ```ocaml (* Only loops, shifts all values over then moves the current value *) let insertion_sort_loop a = let n = Array.length a in for curr_idx = 1 to (n - 1) do let curr_val = a.(curr_idx) in let switch_idx = ref (curr_idx - 1) in while !switch_idx > 0 && a.(!switch_idx) > curr_val do a.(!switch_idx + 1) <- a.(!switch_idx); switch_idx := !switch_idx - 1 done; a.(!switch_idx + 1) <- curr_val done (* Only recursion *) let rec insert a curr_val switch_idx = if switch_idx >= 0 && a.(switch_idx) > curr_val then ( a.(switch_idx + 1) <- a.(switch_idx); insert a curr_val (switch_idx - 1)) else a.(switch_idx + 1) <- curr_val let rec insertion_sort_helper a i n = if i < n then ( insert a a.(i) (i - 1); insertion_sort_helper a (i + 1) n) let insertion_sort a = let n = Array.length a in insertion_sort_helper a 1 n ``` :::info This is the end of material for Quiz 2! See the Quiz 2 logistics page for more details. ::: --- # Thunks Say you wanted to define a debugging version of `if` that always printed its condition. Here is one potential implementation: ```ocaml let dbg_if (c : bool) (t : 'a) (e : 'a) : 'a = print_endline (string_of_bool c); match c with | true -> t | false -> e ``` Would this function work as expected? No! This has the same issue as our `choose` from Quiz 1. It would cause problems because function calls evaluate their arguments before their body in OCaml. This is known as _eager_ evaluation. Arguments to function calls are evaluated eagerly (before call. The branches of an if are evaluated _lazily_ (not eager). ## Delayed evaluation :::success How could we implement a version of `dbg_if` correctly, without changing the OCaml langugae semantics? Have we seen any ways to delay computation? That is, save a chunk of work to be done for later? ::: Yes, function bodies! We can delay computation by wrapping in an “unnecessary” function. - The only purpose is to delay evaluation - Zero argument function used to delay evaluation are called **thunks** More next time!