2

当要在 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
4

1 回答 1

3

因此，现在将环境表示为一个函数，该函数采用名称并在环境中返回其值或引发异常。
该函数将是函数的组合，您可以通过应用代表旧环境的函数来“遍历”它。
（这听起来比实际上更复杂，但可能需要一段时间才能理解它。）

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

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"

异常处理示例：

如果您不处理异常，您将收到“未捕获的异常”错误，如上例所示。

您需要处理使用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
于 2018-03-09T05:39:17.057 回答