Finding a value in a function represented environment

Question

When it came to finding a value in a bst env all I had to do was compare the value I was looking for with the root value at a node

type 'a tenv = (name * 'a) btree

exception NotFound of name
fun find compare name Leaf = raise NotFound name 
| find compare name (Node (lt, (key, value), rt)) = 
  case compare(name, key) of
    LESS => find compare name lt
  | GREATER => find compare name rt
  | EQUAL => value

But in a function represented env instead of a bst with nodes and leafs the find function is of type

name * 'a fenv -> 'a

and

type 'a fenv = name -> 'a

I get the general idea of the function but I'm confused as to how I would traverse the environment looking for the name. Bst has a node and a tree like structure. Can someone just give an explanation if possible?

EDITED IN

My working implementation is as such

exception NotFound of name
val Empty = fn name => raise NotFound name

fun Find(name, env) = env name

fun Bind(name, data, rho) = fn key => if key = name then data else rho 
key 

Answer 1

So an environment is now represented as a function that takes a name and either returns its value in the environment or raises an exception.
This function is going to be a composition of functions, and you "traverse" it by applying functions that represent older environments.
(This sounds more complicated than it is, but it can take a while to wrap your head around it.)

You can create the empty environment by writing a function that takes a name and raises an exception:

val empty = fn n => raise NotFound n

Finding things is much shorter than a tree lookup, since the environment already is that function:

fun find n env = env n

What remains is insertion:

fun insert (key, value) env = ... what?

It has to be a function that takes a name, since that's what an environment is

fun insert (key, value) env = fn n => ... what?

If n is the same as key, that function should return value:

fun insert (key, value) env = fn n => if n = key then value else ... what?

n might be found in the rest of the environment, so we apply that function in order to look for it there:

fun insert (key, value) env = fn n => if n = key then value else env n

And that's, as they say, it.

In a sense, the "traversal" code has moved from the lookup function to the insertion function.

Test:

- val env = insert ("hi", 23) empty;
val env = fn : string -> int
- find "hi" env;
val it = 23 : int
- find "hello" env;

uncaught exception NotFound
  raised at: ...
- val env2 = insert ("hello", 999) env;
val env2 = fn : string -> int
- find "hello" env2;
val it = 999 : int
- find "hi" env2;
val it = 23 : int

As you can see, representing things as functions can be extremely compact.

---

In order to see what's happening, let's expand the first example:

val env = insert ("hi", 23) empty

Which is the same as (expanding the definition of insert):

val env = fn n => if n = "hi" then 23 else empty n

Successful lookup:

find "hi" env

is

env "hi"

which is

(fn n => if n = "hi" then 23 else empty n) "hi"
->
if "hi" = "hi" then 23 else empty n
-> 
23

Failure:

find "hello" env
->
(fn n => if n = "hi" then 23 else empty n) "hello"
->
if "hello" = "hi" then 23 else empty "hello"
->
empty "hello"
->
raise NotFound "hello"

---

Exception-handling example:

If you don't handle the exception, you will get an "uncaught exception" error, as in the example above.

You need to handle the exception in the code that uses find.
A trivial example:

fun contains n env = let val _ = find n env
                     in true
                     end
                     handle NotFound nm => false


- contains "hello" env;
val it = false : bool
- contains "hi" env;
val it = true : bool