Here I’ll post the code for my solutions to the 1st chapter of the book.

1.1

1

let g n = n + 4

1.2

1

let h (x, y) = System.Math.Sqrt(x * x + y * y)

1.3

The function expression for g is of type int -> int and the function expression for h is (float * float) -> float

1.4

The recusion formula for the following problem is:

1
2

0 = 0
n = n + (n - 1) for n > 0

The code for the assignment:

1
2
3
4

let rec f =
    function
    | 0 -> 0
    | n -> n + f (n - 1)

The evaluation for f 3 is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

~> f 3
~> 3 + f (n - 1)
~> 3 + f 2
~> 3 + (2 + f(2 - 1)) 
~> 3 + (2 + f 1)
~> 3 + (2 + (1 + f(1 - 1))
~> 3 + (2 + (1 + f 0))
~> 3 + (2 + (1 + 0))
~> 3 + (2 + 1)
~> 3 + 3
~> 6

1.5

The naive implementation of the solution to the problem would look like the code below. This solutions is however problematic because the recursion tree would expand exponentially. This due to the fact you call fib (n -1) + fib (n -2) and thus you do two recursive calls for each level (if you imangine it as a tree) of your fibonacci sequence.

1
2
3
4

let rec fib = function
  | 0 -> 0
  | 1 -> 1
  | n -> fib (n - 1) + fib (n - 2)

A better approach would be to utilize the concept of tail-recusion when solving the task, but this is unlikely the reader knows that at this point in the book. This would convert the recursive call into simple goto statements and thus avoid the exponetial stack growth as the previous solution. The new solution would the look something like this:

1
2
3
4
5
6

let fib n = 
  let rec inner_fib n a b =
    match n with
    | 0 -> a
    | _ -> inner_fib (n - 1) b (a + b)
  inner_fib n 0 1

The evaluation for fib 4 is as follows for the naive solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

~> fib 4 
~> fib (4 - 1) + fib (4 - 2)
~> fib 3 + fib 2
~> (fib (3 - 1) + fib (3 - 2)) + (fib (2 - 1) + fib (2 - 2))
~> (fib 2 + fib 1) + (fib 1 + fib 0)
~> ((fib (2 - 1) + fib(2 - 2) + fib 1) + (1 + 0))
~> ((fib 1 + fib 0) + 1) + (1 + 0))
~> ((1 + 0) + 1) + (1 + 0))
~> (1 + 1) + (1 + 0))
~> 2 + 1
~> 3

1.6

The recursion formula for the following problem is:

1
2

(m, 0) = m
(m, n) = m + (m, n - 1)

The code for the solution:

1
2
3

let rec sum = function
  | (m, 0) -> m
  | (m, n) -> m + sum (m, n - 1)

1.7

The type for the expressions is: (System.Math.PI, fact -1) = (float * int) fact(fact 4) = int power(System.Math.PI, fact 2) = float (power, fact) = (float -> int -> float) * (int -> int))

Book by Michael R. Hansen and Hans Richel

Photo by Ilija Boshkov on Unsplash