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
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