Sunday, December 31, 2006

EOPL - 1.2.1 - Deriving Programs from BNF Data Specifications

It's not necessary to have functions like list-of-numbers? in F#, because types are checked statically. An int list will always be a list of integers if the code compiles. The type checker takes care of that. So here are versions of nth-elt and list-length:

let rec nth_elt l n =
match (l, n) with
([], _) -> failwith ("List too short by " +
string_of_int (n + 1) + " elements")
| (x :: rl, 0) -> x
| (_ :: rl, _) -> nth_elt rl (n - 1)

let rec list_length l =
match l with
[] -> 0
| (_ :: rl) -> 1 + list_length rl

Just for fun, here is a non-recursive version of list-length, using a fold:

let list_length l = List.fold_left (fun n _ -> n + 1) 0 l

Unfortunately the F# compiler doesn't let us write this version in point-free style because of some trouble with the value restriction.

Exercises 1.5 and 1.6 make no sense in F#, once again because of the static type checker. Exercise 1.7 is quite easy, thanks to any_to_string:

let nth_elt l n =
let rec loop l' n' =
match (l', n') with
([], _) -> failwith ((any_to_string l) +
" does not have an element " +
string_of_int n)
| (x :: rl, 0) -> x
| (_ :: rl, _) -> loop rl (n' - 1) in
loop l n

No comments: