Блог

Я работаю над книгой «Современная реализация компилятора в ML» и одновременно изучаю sml.

Я озадачен одним из упражнений (1.1.b) в первой главе. Нас просят реализовать двоичное дерево, которое поддерживает пары ключ / значение, при этом ключи являются строками, а значения являются параметризованным типом. Мой тип данных определяется следующим образом

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

Нас просят реализовать lookup функцию, тип которой 'a tree * key -> 'a .
Я не знаю, как реализовать эту функцию, потому что я не знаю, что возвращать, когда дерево является LEAF . Значение по умолчанию отсутствует 'a . В инструкциях в книге не указано, что делать, если ключ не найден, но он настаивает на том, что функция ДОЛЖНА возвращать тип 'a .

Это просто ошибка в книге, или есть правильный способ сделать это в sml?

Я пытался создать исключение в этом случае, но компилятор, по-видимому, не позволит мне создать исключение, не поймав его.

Если бы я реализовывал это в Scala, я бы изменил возвращаемый тип на Option[A] и возвращал None , если ключ не найден; или в Common Lisp я бы передал продолжение для вызова с найденным значением, а затем просто не вызывал продолжение, если ключ не найден.

Вот мой код, который еще не работает.

 (* 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 .

Вы определенно можете перейти lookup на использование 'a option .

Вот базовая реализация словаря, которая использует непрозрачный модуль и параметры типа, а не параметры модуля. В примере, который вы получили, используется смесь, где key является параметром модуля, а 'a значение по-прежнему полиморфно. Как правило, это хорошая идея, потому что у вас больше гибкости в отношении реализации. Но поскольку вы просто используете список как словарь, вы можете использовать ''key для обозначения параметра типа, который сопоставим по равенству. (Если вам нужно более эффективное представление, такое как дерево или хэш-карта, вам понадобится интерфейс большего размера.)

 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 _ = ... , если вас интересует только побочный эффект.