如何在sml中部分实现功能

Question

我正在阅读“现代编译器在ML中的实现”一书，同时学习sml。

我被第一章中的一个练习(1.1.b)难住了。我们被要求实现一个二叉树，它维护键/值对，键是字符串，值是参数化类型。我的数据类型定义如下

type key = string
datatype 'a tree = LEAF | TREE of 'a tree * key * 'a * 'a tree

我们需要实现一个类型为'a tree * key -> 'a的lookup函数。我不知道如何实现这个函数，因为当树是LEAF时，我不知道返回什么。'a没有默认值。书中的说明没有说明如果找不到键该怎么做，但它坚持函数必须返回类型'a。

这只是书中的一个错误，还是在sml中有正确的方法来做到这一点？

在这种情况下，我尝试引发一个异常，但编译器显然不会让我在不捕获异常的情况下抛出它。

如果我在Scala中实现这一点，我会将返回类型更改为Option[A]，如果没有找到键就返回None；或者在Common Lisp中，我会传递一个change来使用找到的值进行调用，然后如果没有找到键就不调用change。

这是我的代码，它还不能工作。

(* page 12, exercise 1.1 b *)
type key = string
datatype 'a tree = LEAF | TREE of 'a tree * key * 'a * 'a tree

val empty = LEAF

fun insert(key,value,LEAF) = TREE(LEAF,key,value,LEAF)
  | insert(key,value,TREE(l,k,v,r)) =
    if key<k
    then TREE(insert(key,value,l),k,v,r)
    else if key>k
    then TREE(l,k,v,insert(key,value,r))
    else TREE(l,key,value,r)

fun lookup(LEAF,key) =  (* !!!HELP!!!  I don't know what to do in this case *)
  | lookup(TREE(l,k,v,r),key) = if k=key
                                then v
                                else if key<k
                                then lookup(l,key)
                                else lookup(r,key)

val t1 = insert("a",1,empty)
val t2 = insert("c",2,t1)
val t3 = insert("b",3,t2)
   ;

     lookup(t3,"a");
     lookup(t3,"b");
     lookup(t3,"c");
     lookup(t3,"d");

顺便说一句，我不明白为什么emacs sml-mode坚持缩进对lookup的调用。

Answer 1

您绝对可以将lookup更改为使用'a option。

这是一个基本的字典实现，它使用不透明的模块和类型参数，而不是模块参数。您从中派生的示例使用了一种混合，其中key是模块参数，'a是值仍然是多态的。这通常是一个好主意，因为您在实现方面具有更大的灵活性。但是，因为您只是使用列表作为字典，所以可以使用''key来表示等价性相当的类型参数。(如果您想要更有效的表示，如树或hashmap，则需要更大的接口。)

signature DICT = sig
  type (''key, 'value) dict
  val empty : (''key, 'value) dict
  val insert : ''key -> 'value -> (''key, 'value) dict -> (''key, 'value) dict
  val lookup : ''key -> (''key, 'value) dict -> 'value option
end

structure Dict :> DICT = struct
  type (''key, 'value) dict = (''key * 'value) list
  val empty = []
  fun insert k v [] = [(k, v)]
    | insert k v ((k2,v2)::dict) =
        if k = k2
        then (k,v)::dict
        else (k2,v2)::insert k v dict
  fun lookup k dict = Option.map #2 (List.find (fn (k2,v2) => k = k2) dict)
end

现在,

- val demo = Dict.lookup "foo" (Dict.insert "foo" 42 Dict.empty)
> val demo = SOME 42 : int option

val t1 = insert("a",1，empty) val t2 = insert("c",2，t1) val t3 = insert("b",3，t2)；X lookup(t3，"a")；lookup(t3，"b")；lookup(t3，"c")；lookup(t3，"d")；

顺便说一句，我不明白为什么emacs sml-mode坚持缩进查找的调用。

这是因为sml-mode认为;是表达式运算符，而不是声明分隔符。我放置了一个X，如果它是表达式运算符，那么在这里放置一个表达式是很自然的。进行换行符时，将后续表达式放在相同的缩进点上是很自然的。

Emacs sml-mode只使用前面的一行来确定缩进级别，这使得它有点简单。您可以通过在所有声明前加上val ... =前缀，或者以不那么随意的方式放置;来避免此处的缩进，例如

...
val t3 = insert ("b", 3, t2)
val L1 = lookup(t3,"a")
val L2 = ...

或

...
val t3 = insert ("b", 3, t2)
;lookup(t3,"a");
;lookup(t3,"b");

这里两边的;s背后的思想是，当我们讨论声明分隔符(而不是表达式运算符)时，允许您重复任意多个;s，因此，由于;s不需要终止val ...声明，因此这些行不容易受到前后上下文更改的影响，就像val x = ...一样。只有当您仅将SML代码作为脚本/在REPL中求值时，这种风格才有意义。否则，如果您只对副作用感兴趣，则可能希望命名绑定或使用val _ = ...。