EOPL - 2.3.2 - Procedural Representation

Section 2.3 is about strategies for representing data types. In section 2.3.1 an abstract interface for environments is presented, and then in section 2.3.2, Figure 2.3 shows a procedural implementation for the environment interface. Translated into F#, Figure 2.3 would be like the following:

let find_index a lst = 
    let rec loop l = 
        match l with
          [] -> raise Not_found
        | (x :: l') when x = a -> List.length l'
        | (x :: l') -> loop l' in
    loop (List.rev lst)
        
let list_find_position sym los = 
    if List.mem sym los then
        Some (find_index sym los)
    else
        None
        
let empty_env () = 
    fun sym -> failwith (sprintf "No binding for %s" sym)

let apply_env env sym = 
    env sym
    
let extend_env syms vals env = 
    fun sym -> match list_find_position sym syms with
                 None -> apply_env env sym
               | Some i -> List.nth vals i

In this case, function find_list_position is redundant, because find_index does not take a predicate, so it's less generic than the version in the book. It shouldn't be a problem at this point, though. Function find_index reverses the list, we can write a version that does without that:

let rec find_index2 a lst = 
    match lst with 
      [] -> raise Not_found
    | (x :: lst') when x = a -> 0
    | (x :: lst') -> 1 + find_index2 a lst'