# Exercises

# 3.14. Exercises#

Solutions to most exercises are available. Fall 2022 is the first public release of these solutions. Though they have been available to Cornell students for a few years, it is inevitable that wider circulation will reveal improvements that could be made. We are happy to add or correct solutions. Please make contributions through Github.

**Exercise: list expressions [★]**

Construct a list that has the integers 1 through 5 in it. Use the square bracket notation for lists.

Construct the same list, but do not use the square bracket notation. Instead use

`::`

and`[]`

.Construct the same list again. This time, the following expression must appear in your answer:

`[2; 3; 4]`

. Use the`@`

operator, and do not use`::`

.

**Exercise: product [★★]**

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`

.

**Exercise: concat [★★]**

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 `""`

.

**Exercise: product test [★★]**

Unit test the function `product`

that you wrote in an exercise above.

**Exercise: 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

`"bigred"`

the list has exactly two or four elements; do not use the

`length`

functionthe first two elements of the list are equal

**Exercise: library [★★★]**

Consult the `List`

standard library to solve these exercises:

Write a function that takes an

`int list`

and returns the fifth element of that list, if such an element exists. If the list has fewer than five elements, return`0`

.*Hint:*`List.length`

and`List.nth`

.Write a function that takes an

`int list`

and returns the list sorted in descending order.*Hint:*`List.sort`

with`Stdlib.compare`

as its first argument, and`List.rev`

.

**Exercise: library test [★★★]**

Write a couple OUnit unit tests for each of the functions you wrote in the previous exercise.

**Exercise: library puzzle [★★★]**

Write a function that returns the last element of a list. Your function may assume that the list is non-empty.

*Hint: Use two library functions, and do not write any pattern matching code of your own.*Write a function

`any_zeroes : int list -> bool`

that returns`true`

if and only if the input list contains at least one`0`

.*Hint: use one library function, and do not write any pattern matching code of your own.*

Your solutions will be only one or two lines of code each.

**Exercise: take drop [★★★]**

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.

**Exercise: take drop tail [★★★★]**

Revise your solutions for `take`

and `drop`

to be tail recursive, if they aren’t
already. Test them on long lists with large values of `n`

to see whether they
run out of stack space. To construct long lists, use the `--`

operator from
the lists section.

**Exercise: unimodal [★★★]**

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.

**Exercise: powerset [★★★]**

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)`

?

**Exercise: print int list rec [★★]**

Write a function `print_int_list : int list -> unit`

that prints its input list,
one number per line. For example, `print_int_list [1; 2; 3]`

should result in
this output:

```
1
2
3
```

Here is some code to get you started:

```
let rec print_int_list = function
| [] -> ()
| h :: t -> (* fill in here *); print_int_list t
```

**Exercise: print int list iter [★★]**

Write a function `print_int_list' : int list -> unit`

whose specification is the
same as `print_int_list`

. Do not use the keyword `rec`

in your solution, but
instead to use the List module function `List.iter`

. Here is some code
to get you started:

```
let print_int_list' lst =
List.iter (fun x -> (* fill in here *)) lst
```

**Exercise: student [★★]**

Assume the following type definition:

```
type student = {first_name : string; last_name : string; gpa : float}
```

Give OCaml expressions that have the following types:

`student`

`student -> string * string`

(a function that extracts the student’s name)`string -> string -> float -> student`

(a function that creates a student record)

**Exercise: pokerecord [★★]**

Here is a variant that represents a few Pokémon types:

```
type poketype = Normal | Fire | Water
```

Define the type

`pokemon`

to be a record with fields`name`

(a string),`hp`

(an integer), and`ptype`

(a`poketype`

).Create a record named

`charizard`

of type`pokemon`

that represents a Pokémon with 78 HP and Fire type.Create a record named

`squirtle`

of type`pokemon`

that represents a Pokémon with 44 HP and Water type.

**Exercise: safe hd and tl [★★]**

Write a function `safe_hd : 'a list -> 'a option`

that returns `Some x`

if the
head of the input list is `x`

, and `None`

if the input list is empty.

Also write a function `safe_tl : 'a list -> 'a list option`

that returns the
tail of the list, or `None`

if the list is empty.

**Exercise: pokefun [★★★]**

Write a function `max_hp : pokemon list -> pokemon option`

that, given a list of
`pokemon`

, finds the Pokémon with the highest HP.

**Exercise: date before [★★]**

Define a *date-like triple* to be a value of type `int * int * int`

. Examples of
date-like triples include `(2013, 2, 1)`

and `(0, 0, 1000)`

. A *date* is a
date-like triple whose first part is a positive year (i.e., a year in the common
era), second part is a month between 1 and 12, and third part is a day between 1
and 31 (or 30, 29, or 28, depending on the month and year). `(2013, 2, 1)`

is a
date; `(0, 0, 1000)`

is not.

Write a function `is_before`

that takes two dates as input and evaluates to
`true`

or `false`

. It evaluates to `true`

if the first argument is a date that
comes before the second argument. (If the two dates are the same, the result is
`false`

.)

Your function needs to work correctly only for dates, not for arbitrary date-like triples. However, you will probably find it easier to write your solution if you think about making it work for arbitrary date-like triples. For example, it’s easier to forget about whether the input is truly a date, and simply write a function that claims (for example) that January 100, 2013 comes before February 34, 2013—because any date in January comes before any date in February, but a function that says that January 100, 2013 comes after February 34, 2013 is also valid. You may ignore leap years.

**Exercise: earliest date [★★★]**

Write a function `earliest : (int*int*int) list -> (int * int * int) option`

. It
evaluates to `None`

if the input list is empty, and to `Some d`

if date `d`

is
the earliest date in the list. *Hint: use is_before.*

As in the previous exercise, your function needs to work correctly only for dates, not for arbitrary date-like triples.

**Exercise: assoc list [★]**

Use the functions `insert`

and `lookup`

from the
section on association lists to construct an association list that
maps the integer 1 to the string “one”, 2 to “two”, and 3 to “three”. Lookup the
key 2. Lookup the key 4.

**Exercise: cards [★★]**

Define a variant type

`suit`

that represents the four suits, ♣ ♦ ♥ ♠, in a standard 52-card deck. All the constructors of your type should be constant.Define a type

`rank`

that represents the possible ranks of a card: 2, 3, …, 10, Jack, Queen, King, or Ace. There are many possible solutions; you are free to choose whatever works for you. One is to make`rank`

be a synonym of`int`

, and to assume that Jack=11, Queen=12, King=13, and Ace=1 or 14. Another is to use variants.Define a type

`card`

that represents the suit and rank of a single card. Make it a record with two fields.Define a few values of type

`card`

: the Ace of Clubs, the Queen of Hearts, the Two of Diamonds, the Seven of Spades.

**Exercise: matching [★]**

For each pattern in the list below, give a value of type `int option list`

that
does *not* match the pattern and is not the empty list, or explain why that’s
impossible.

`Some x :: tl`

`[Some 3110; None]`

`[Some x; _]`

`h1 :: h2 :: tl`

`h :: tl`

**Exercise: quadrant [★★]**

Complete the `quadrant`

function below, which should return the quadrant of the
given `x, y`

point according to the diagram on the right (borrowed from
Wikipedia).
Points that lie on an axis do not belong to any quandrant. *Hints: (a) define a
helper function for the sign of an integer, (b) match against a pair.*

```
type quad = I | II | III | IV
type sign = Neg | Zero | Pos
let sign (x:int) : sign =
...
let quadrant : int*int -> quad option = fun (x,y) ->
match ... with
| ... -> Some I
| ... -> Some II
| ... -> Some III
| ... -> Some IV
| ... -> None
```

**Exercise: quadrant when [★★]**

Rewrite the quadrant function to use the `when`

syntax. You won’t need your
helper function from before.

```
let quadrant_when : int*int -> quad option = function
| ... when ... -> Some I
| ... when ... -> Some II
| ... when ... -> Some III
| ... when ... -> Some IV
| ... -> None
```

**Exercise: depth [★★]**

Write a function `depth : 'a tree -> int`

that returns the number of nodes in
any longest path from the root to a leaf. For example, the depth of an empty
tree (simply `Leaf`

) is `0`

, and the depth of tree `t`

above is `3`

. *Hint:
there is a library function max : 'a -> 'a -> 'a that returns the maximum of
any two values of the same type.*

**Exercise: shape [★★★]**

Write a function `same_shape : 'a tree -> 'b tree -> bool`

that determines
whether two trees have the same shape, regardless of whether the values they
carry at each node are the same. *Hint: use a pattern match with three branches,
where the expression being matched is a pair of trees.*

**Exercise: list max exn [★★]**

Write a function `list_max : int list -> int`

that returns the maximum integer
in a list, or raises `Failure "list_max"`

if the list is empty.

**Exercise: list max exn string [★★]**

Write a function `list_max_string : int list -> string`

that returns a string
containing the maximum integer in a list, or the string `"empty"`

(note, not the
exception `Failure "empty"`

but just the string `"empty"`

) if the list is empty.
*Hint: string_of_int in the standard library will do what its name suggests.*

**Exercise: list max exn ounit [★]**

Write two OUnit tests to determine whether your solution to **list max exn**,
above, correctly raises an exception when its input is the empty list, and
whether it correctly returns the max value of the input list when that list is
nonempty.

**Exercise: is_bst [★★★★]**

Write a function `is_bst : ('a*'b) tree -> bool`

that returns `true`

if and only
if the given tree satisfies the binary search tree invariant. An efficient
version of this function that visits each node at most once is somewhat tricky
to write. *Hint: write a recursive helper function that takes a tree and either
gives you (i) the minimum and maximum value in the tree, or (ii) tells you that
the tree is empty, or (iii) tells you that the tree does not satisfy the
invariant. Your is_bst function will not be recursive, but will call your
helper function and pattern match on the result. You will need to define a new
variant type for the return type of your helper function.*

**Exercise: quadrant poly [★★]**

Modify your definition of quadrant to use polymorphic variants. The types of your functions should become these:

```
val sign : int -> [> `Neg | `Pos | `Zero ]
val quadrant : int * int -> [> `I | `II | `III | `IV ] option
```