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