Monday, March 5, 2007

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)

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'

No comments: