## Expressions and types Give OCaml expressions that have the following types. * `int list` * `string -> string list` * `string list -> string` ## Patterns Using pattern matching, write three functions, one for each of the following properties. Your functions should return `true` if the input list has the property and `false` otherwise. * the list's first element is `"cs3110"` * the list has exactly two or four elements; do not use the `length` function * the first two elements of the list are equal ## Functions on lists * Write a function that returns the product of all the elements in a list. (The product of all the elements of an empty list is `1`.) * Write a function that concatenates all the strings in a list. (The concatenation of all the strings in an empty list is the empty string `""`.) ## Library functions Consult the [`List` standard library](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html) to easily implement the following functions: * Write a function that returns the last element of a list. *Hint:* this can be solved by combining two library functions, and without writing any pattern matching code of your own. If the list is empty, your function may throw an exception. * Write a function `any_zeroes : int list -> bool` that returns `true` if and only if the input list contains at least one `0`. *Hint:* this can be solved by using one library function, and without writing any pattern matching code of your own. Your solutions should need only about one line of code. ## Tail recursion * Write a function `take : int -> 'a list -> 'a list` such that `take n lst` returns the first `n` elements of `lst`. If `lst` has fewer than `n` elements, return all of them. * Write a function `drop : int -> 'a list -> 'a list` such that `drop n lst` returns all but the first `n` elements of `lst`. If `lst` has fewer than `n` elements, return the empty list. Your functions must be tail recursive. Test them on long lists with large values of `n` to see whether they run out of stack space. Here is code to produce a long list: ``` let (--) i j = let rec from i j l = if i>j then l else from i (j-1) (j::l) in from i j [] let longlist = 0 -- 1_000_000 ``` Note that code itself is tail recursive. ## More functions on lists * Write a function `is_unimodal : int list -> bool` that takes an integer list and returns whether that list is unimodal. A *unimodal list* is a list that monotonically increases to some maximum value then monotonically decreases after that value. Either or both segments (increasing or decreasing) may be empty. A constant list is unimodal, as is the empty list. * Write a function `powerset : int list -> int list list` that takes a set *S* represented as a list and returns the set of all subsets of *S*. The order of subsets in the powerset and the order of elements in the subsets do not matter. *Hint:* Consider the recursive structure of this problem. Suppose you already have `p`, such that `p = powerset s`. How could you use `p` to compute `powerset (x::s)`?