EOPL - Section 2.3.3

The abstract syntax tree representation for environments is quite straightforward in F#; it is shown below.

type Value = Integer of int | String of string
type Environment = EmptyEnv 
                 | ExtendedEnv of string list * 
                                  Value list * 
                                  Environment

// helper function
let list_find_position a lst = 
    let rec loop l = 
        match l with
          [] -> None
        | (x :: l') when x = a -> Some (List.length l')
        | (x :: l') -> loop l' in
    loop (List.rev lst)

let empty_env () = 
    EmptyEnv
    
let extend_env syms vals env = 
    ExtendedEnv (syms, vals, env)
    
let rec apply_env env sym = 
    match env with
      EmptyEnv -> failwith (sprintf "No binding for %s" sym)
    | ExtendedEnv (syms, vals, env') -> 
        match list_find_position sym syms with
          None -> apply_env env' sym
        | Some i -> List.nth vals i