<![CDATA[
# Higher-order Programming
In today's lab, we'll practice using higher-order functions.
## Higher-order functions
##### Exercise: twice, no arguments [✭]
Consider the following definitions:
```
let double x = 2*x
let square x = x*x
let twice f x = f (f x)
let quad = twice double
let fourth = twice square
```
Use the toplevel to determine what the types of `quad` and `fourth` are.
Explain how it can be that `quad` is not syntactically written as a
function that takes an argument, and yet its type shows that it is in
fact a function.
□
##### Exercise: mystery operator 1 [✭✭]
What does the following operator do?
```
let ($) f x = f x
```
*Hint: investigate `square $ 2 + 2` vs. `square 2 + 2`.*
□
##### Exercise: mystery operator 2 [✭✭]
What does the following operator do?
```
let (@@) f g x = x |> g |> f
```
*Hint: investigate `String.length @@ string_of_int` applied to `1`, `10`, `100`, etc.*
□
##### Exercise: repeat [✭✭]
Generalize `twice` to a function `repeat`, such that `repeat f n x`
applies `f` to `x` a total of `n` times. That is,
* `repeat f 0 x` yields `x`
* `repeat f 1 x` yields `f x`
* `repeat f 2 x` yields `f (f x)` (which is the same as `twice f x`)
* `repeat f 3 x` yields `f (f (f x))`
* ...
□
## Map, fold, and filter
Review the [OCaml List library][listdoc] documentation of `map`, `fold_left`,
`fold_right`, and `filter`. Recall that
* `map` applies a function to each element of a list individually
* the `fold_X` functions combine all the elements of a list with a function
* `filter` removes elements of a list that do not satisfy a function
[listdoc]: http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html
##### Exercise: product [✭]
Use `fold_left` to write a function `product_left` that computes the product
of a list of floats. The product of the empty list is `1.0`. *Hint:
recall how we implemented `sum` in just one line of code in lecture.*
Use `fold_right` to write a function `product_right` that computes the product
of a list of floats. *Same hint applies.*
□
##### Exercise: sum_cube_odd [✭✭]
Write a function `sum_cube_odd n` that computes the sum of the cubes of all
the odd numbers between `0` and `n` inclusive. Do not write any new recursive
functions. Instead, use the functionals map, fold, and filter, and the `(--)`
operator defined in the lecture notes.
□
##### Exercise: sum_cube_odd pipeline [✭✭]
Rewrite the function `sum_cube_odd` to use the pipeline operator `|>`
as shown in the lecture notes for this lab in the section
titled "Pipelining".
□
## Three ways
We've now seen three different ways for writing functions that manipulate lists:
directly as a recursive function that pattern matches against the empty list and
against cons, using `fold` functions, and using other library functions.
Let's try using each of those ways to solve a problem, so that we can
appreciate them better.
Consider writing a function `lst_and: bool list -> bool`, such that
`lst_and [a1; ...; an]` returns whether all elements of the list are
`true`. That is, it evaluates the same as `a1 && a2 && ... && an`.
When applied to an empty list, it evaluates to `true`.
Here are three possible ways of writing such a function. We give
each way a slightly different function name for clarity.
```
let rec lst_and_rec = function
| [] -> true
| h::t -> h && lst_and_rec t
let lst_and_fold =
List.fold_left (fun acc elt -> acc && elt) true
let lst_and_lib =
List.for_all (fun x -> x)
```
##### Exercise: exists [✭✭]
Consider writing a function `exists: ('a -> bool) -> 'a list -> bool`,
such that `exists p [a1; ...; an]` returns whether at least one element
of the list satisfies the predicate `p`. That is, it evaluates the same
as `(p a1) || (p a2) || ... || (p an)`. When applied to an empty list,
it evaluates to `false`.
Write three solutions to this problem, as we did above:
* `exists_rec`, which must be a recursive function that does not use the
`List` module,
* `exists_fold`, which uses either `List.fold_left` or `List.fold_right`, but
not any other `List` module functions nor the `rec` keyword, and
* `exists_lib`, which uses any combination of `List` module functions other
than `fold_left` or `fold_right`, and does not use the `rec` keyword.
Also write a test suite similar to the one above. Make sure your implementations
pass your test suite.
□
## Currying
We've already seen that an OCaml function that takes two arguments of types
`t1` and `t2` and returns a value of type `t3` has the type `t1 -> t2 -> t3`.
We use two variables after the function name in the let expression:
```
# let add x y = x + y;;
val add : int -> int -> int
```
Another way to define a function that takes two arguments is to write a function
that takes a tuple:
```
# let add' t = (fst t) + (snd t)
val add' : int * int -> int
```
Instead of using `fst` and `snd`, we could use a tuple pattern in the
definition of the function, leading to a third implementation:
```
# let add'' (x,y) = x + y
val add'' : int * int -> int
```
Functions written using the first style (with type `t1 -> t2 -> t3`) are
called *curried* functions, and functions using the second style (with
type `t1 * t2 -> t3`) are called *uncurried*. Metaphorically, curried
functions are "spicier" because you can partially apply them (something
you can't do with uncurried functions: you can't pass in half of a
pair). Actually, the term curry does not refer to spices, but to a
logician named [Haskell Curry][curry] (one of a very small set of people
with programming languages named after both their first and last names).
[curry]: https://en.wikipedia.org/wiki/Haskell_Curry
Sometimes you will come across libraries that offer an uncurried version
of a function, but you want a curried version of it to use in your own
code; or vice versa. So it is useful to know how to convert between
the two kinds of functions. The next couple exercises explore how to do that.
They are also good exercises for improving your understanding of the types
of higher-order functions.
##### Exercise: library uncurried [✭✭]
Here is an uncurried version of `List.nth`:
```
let uncurried_nth (lst,n) = List.nth lst n
```
In a similar way, write uncurried versions of these library functions:
- `List.append`
- `Char.compare`
- `Pervasives.max`
□
When many functions share a common pattern, you can often write a single
higher-order function to capture the common structure.
##### Exercise: uncurry [✭✭]
Write a function `uncurry` that takes in a curried function and returns
the uncurried version of that function. Remember that curried functions
have types like `'a -> 'b -> 'c`, and the corresponding uncurried
function will have the type `'a * 'b -> 'c`. Therefore `uncurry` should
have the folowing type:
```
val uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c
```
If your solution is correct, you can use it to reimplement the previous exercise
as follows:
```
let uncurried_nth = uncurry List.nth
let uncurried_append = uncurry List.append
let uncurried_compare = uncurry Char.compare
let uncurried_max = uncurry max
```
□
##### Exercise: curry [✭✭]
Write the inverse function `curry`. It should have the following type:
```
val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c
```
□
## Additional exercises
##### Exercise: terse product [✭✭, advanced]
How terse can you make your solutions to the **product** exercise?
*Hints: you need only one line of code for each, and you do not need
the `fun` keyword. For `fold_left`, your function definition does not even need
to explicitly take a list argument. If you use `ListLabels`, the same
is true for `fold_right`.*
□
##### Exercise: map composition [✭✭✭]
Show how to replace any expression of the form `List.map f (List.map g lst)`
with an equivalent expression that calls `List.map` only once.
□
##### Exercise: more list fun [✭✭✭]
Write functions that perform the following computations. Each function
that you write should use one of `List.fold`, `List.map` or `List.filter`.
To choose which of those to use, think about what the computation is doing:
combining, transforming, or filtering elements.
* Find those elements of a list of strings whose length is strictly greater than 3.
* Add `1.0` to every element of a list of floats.
* Given a list of strings `strs` and another string `sep`, produce the string
that contains every element of `strs` separated by `sep`. For example,
given inputs `["hi";"bye"]` and `","`, produce `"hi,bye"`, being sure not
to produce an extra comma either at the beginning or end of the result string.
□
##### Exercise: tree map [✭✭✭]
Using the following defintion of `tree`:
```
type 'a tree =
| Leaf
| Node of 'a * 'a tree * 'a tree
```
Write a function `tree_map : ('a -> 'b) -> 'a tree -> 'b tree` that
applies a function to every node of a tree, just like `List.map` applies
a function to every element of a list.
Use your `tree_map` function to implement a function `add1 : int tree ->
int tree` that increments every node in an `int tree`.
□
##### Exercise: association list keys [✭✭✭]
Recall that an association list is an implementation of a dictionary in terms of
a list of pairs, in which we treat the first component of each pair as a key and the
second component as a value.
Write a function `keys: ('a * 'b) list -> 'a list` that returns a list
of the unique keys in an association list. Since they must be unique, no
value should appear more than once in the output list. The order of
values output does not matter. How compact and efficient can you make your
solution? We know of one solution that (i) would fit in a single line of code,
(ii) uses only library functions—not any user-defined functions, not even
anonymous functions, (iii) requires sub-linear stack space, and (iv) requires
sub-quadratic time. *Hint: merge sort.*
□
## Challenge exercises: Matrices
A mathematical *matrix* can be represented with lists.
In *row-major* representation, this matrix
$$ \left[ \begin{array}{c} 1 & 1 & 1 \\\\ 9 & 8 & 7 \end{array} \right] $$
would be represented as the list `[ [1; 1; 1]; [9; 8; 7] ]`. Let's
represent a *row vector* as an `int list`. For example, `[9; 8; 7]` is
a row vector.
For the remaining exercises, start a new file `matrix.ml` in which you put your
code and `matrix_test.ml` in which you write unit tests.
##### Exercise: valid matrix [✭✭✭]
A *valid* matrix is an `int list list` that has at least one row, at least one column,
and in which every column has the same number of rows. There are many values of type
`int list list` that are invalid, for example,
* `[]`
* `[ [1;2]; [3] ]`
Implement a function `is_valid_matrix: int list list -> bool` that returns whether the
input matrix is valid. Unit test the function.
□
##### Exercise: row vector add [✭✭✭]
Implement a function `add_row_vectors: int list -> int list ->
int list` for the element-wise addition of two row vectors.
For example, the addition of `[1; 1; 1]` and `[9; 8; 7]` is
`[10; 9; 8]`. If the two vectors do not have the same number
of entries, the behavior of your function is *unspecified*—that is,
it may do whatever you like. *Hint: there is an elegant one-line solution
using `List.map2`.* Unit test the function.
□
##### Exercise: matrix add [✭✭✭, advanced]
Implement a function `add_matrices: int list list -> int list list ->
int list list` for [matrix addition][matadd]. If the two input matrices
are not the same size, the behavior is unspecified. *Hint: there is an
elegant one-line solution using `List.map2` and `add_row_vectors`.*
Unit test the function.
[matadd]: http://mathworld.wolfram.com/MatrixAddition.html
□
##### Exercise: matrix multiply [✭✭✭✭, advanced]
Implement a function `multiply_matrices: int list list -> int list list
-> int list list` for [matrix multiplication][matmult]. If the two input
matrices are not of sizes that can be multiplied together, the behavior
is unspecified. Unit test the function. *Hint: define functions for
matrix transposition and row vector dot product.*
[matmult]: http://mathworld.wolfram.com/MatrixMultiplication.html
□
]]>