在函数表示的环境中查找值
Finding a value in a function represented environment
当要在 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
因此,环境现在表示为一个函数,该函数接受一个名称,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
当要在 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
因此,环境现在表示为一个函数,该函数接受一个名称,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