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

molbdnilo · Accepted Answer · 2018-03-09T18:07:51.917

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

molbdnilo thank you so much after 4 hours of trying different methods and reading different explanations yours made much more sense. — BearsBeetBattlestar, Mar 09 '18 at 05:56
Sorry but im getting errors when find cant find a name in a given env so i rewrote mine to be as the following (edited in my original post) and yet I still error can you possibly tell me if I am checking the error case wrong — BearsBeetBattlestar, Mar 09 '18 at 06:59
@laughingllama42 You shouldn't do any pattern matching on anything. — molbdnilo, Mar 09 '18 at 07:05
but then how would I check for if name is not found in an env in the find function? — BearsBeetBattlestar, Mar 09 '18 at 07:06
You don't need to check – the exception will be thrown when the chain of function calls reaches the `empty` function. The three lines of code in this answer is a complete implementation. — molbdnilo, Mar 09 '18 at 07:08
Oh I see but I get an error when running on this test case find("c", Bind ("b", 2, Bind ("a", 1, Empty))), FR_NotFound "c") my current implementation is edited in — BearsBeetBattlestar, Mar 09 '18 at 07:15
@laughingllama42 You'll need to be more specific than "I get an error". — molbdnilo, Mar 09 '18 at 07:19
Sorry but say also in this test case find("b", Bind ("a", 1, Empty)) the result is supposed to be notfound b but instead my code doesnt raise an error and outputs an uncaught exception error — BearsBeetBattlestar, Mar 09 '18 at 07:29
If you don't catch (I think ML calls it "handle") the exception, you will get an uncaught exception error. (Just like in my test session above.) You need to handle the exception where you're using `find`. — molbdnilo, Mar 09 '18 at 07:43
@nolbdnilo thanks again for your help after taking a break from my code I found the error I was calling an exception twice which was causing issues. — BearsBeetBattlestar, Mar 09 '18 at 20:15

Finding a value in a function represented environment

1 Answers1