For the OCaml part today we covered roughly Hickey chap.3.1.2-3.3,4,5.
For this afternoon's exercise session I ask you to consider the following:
* Write a recursive function bitwidth : int -> int
that determines how many bits its argument needs.
Hint: use repeated right-shifting lsr (or division by 2)
For example bitwidth 5 = 3 (since 5 is represented as ...00101)
bitwidth 2 = 2 (since 2 is represented as ...00010)
bitwidth 0 = 0 (since 0 is represented as ...00000)
(in class after recursive function slides)
* Implement fst and snd with pattern matching
(in class after pattern-matching slides)
* a. Write a recursive function merge : int list -> int list -> int list
that merges two sorted lists into a new sorted list, e.g.:
merge [] [42] = [42]
merge [1,2,3] [0,0,1,3,7] = [0,0,1,1,2,3,7]
b. What property should hold of merge?
List.sort : ('a -> 'a -> int) -> 'a list -> 'a list
from the standard library may be useful here
(it accepts a comparison function as its first argument, you can just pass it compare : 'a -> 'a -> int))
c. QuickCheck your implementation of merge based on your answer to b.
* a. Write an implementation of Euclid's algorithm (Hickey, Ex.3.4, p.25/35)
Ignore the stuff about writing it as an inline operator,
just implement a recursive, two-argument function
eu_gcd : int -> int -> int
we can call as "eu_gcd 15 10"
b. QuickCheck your implementation against Hickey's algorithm (on p.2/12)
c. Do they differ?
* Test the following different versions of the fibonacci function for
agreement:
- the traditional recursive formulation
- an iterative, bottom-up, linear-time algorithm
- a sub-linear algorithm (a challenge for the daring)
* Exercise 3.6 (impl. string-int dictionary)
* Test String.uppercase (what properties should it have?)