在函数表示的环境中查找值

Question

当要在 bst 环境中查找值时，我所要做的就是将我要查找的值与节点处的根值进行比较

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

因此，环境现在表示为一个函数，该函数接受一个名称，return它在环境中的值或引发异常。
此函数将是函数的组合，您 "traverse" 通过应用代表旧环境的函数来实现它。
（这听起来比实际更复杂，但您可能需要一段时间才能理解它。）

您可以通过编写一个带有名称并引发异常的函数来创建空环境：

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 相同，则该函数应 return 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

正如他们所说，就是这样。

从某种意义上说，"traversal"代码已经从查找函数转移到了插入函数。

测试：

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

Exception-handling 示例：

如果不处理异常，将出现 "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

在函数表示的环境中查找值

Finding a value in a function represented environment

ml

sml

mosml