Нахождение значения в представленной функции среде

Question

Когда дело дошло до нахождения значения в bst env, все, что мне нужно было сделать, это сравнить искомое значение с корневым значением в узле.

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

Но в функции, представленной env вместо bst с узлами и листьями, функция find имеет тип

name * 'a fenv -> 'a

а также

type 'a fenv = name -> 'a

Я получил общее представление о функции, но меня смущает то, как я буду обходить окружение в поисках названия. Bst имеет узел и древовидную структуру. Может кто-то просто дать объяснение, если это возможно?

ИЗДАНО В

Моя рабочая реализация как таковая

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

Таким образом, среда теперь представляется как функция, которая принимает имя и либо возвращает его значение в среде, либо вызывает исключение.
Эта функция будет составной частью функций, и вы "пройдете" ее, применяя функции, представляющие более старые среды.
(Это звучит сложнее, чем на самом деле, но это может занять некоторое время, чтобы обернуть голову вокруг него.)

Вы можете создать пустую среду, написав функцию, которая принимает имя и вызывает исключение:

val empty = fn n => raise NotFound n

Поиск вещей намного короче, чем поиск по дереву, так как среда уже является этой функцией:

fun find n env = env n

Осталось вставить:

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

Это должна быть функция, которая принимает имя, так как это то, что окружение

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

Если n такой же как keyэта функция должна вернуть value:

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

n может быть найден в остальной среде, поэтому мы применяем эту функцию, чтобы найти ее там:

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

И это, как говорится, это.

В некотором смысле код "обхода" переместился из функции поиска в функцию вставки.

Тестовое задание:

- 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

Как видите, представление вещей в виде функций может быть чрезвычайно компактным.

---

Чтобы увидеть, что происходит, давайте расширим первый пример:

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

Что так же, как (расширение определения insert):

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

Успешный поиск:

find "hi" env

является

env "hi"

который

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

Неудача:

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"

---

Пример обработки исключений:

Если вы не обработаете исключение, вы получите ошибку "uncaught exception", как в примере выше.

Вы должны обработать исключение в коде, который использует find,
Тривиальный пример:

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