SML - 创建将键映射到值的字典

Question

我需要在SML中创建一个字典，但是我在插入函数方面遇到了极大的困难。

    type dict = string -> int option

作为一个例子，这里是一个空字典：

    val empty : dict = fn key => NONE

这是我的插入函数实现：

    fun insert (key,value) d = fn d => fn key => value

但这个类型是错误的，我需要的是insert: (string*int) -> dict -> dict。我已经搜索了从惰性函数到实现字典的所有内容。任何帮助或指导都将不胜感激！

如果您仍然对我试图实现的内容感到困惑，我起草了一个简单的查找函数调用时应该得到的结果。

    fun lookup k d = d k

    - val d = insert ("foo",2) (insert ("bar",3) empty);
    val d = fn : string -> int option
    - lookup2 "foo" d;
    val it = SOME 2 : int option
    - lookup2 "bar" d;
    val it = SOME 3 : int option
    - lookup2 "baz" d;
    val it = NONE : int option

- user44438

Answer 1

你可以对函数的签名进行推理：

val insert = fn: (string * int) -> dict -> dict

当您提供key、value 和一个字典d时，您希望得到一个新的字典d'。因为dict是string->int option，所以d'是一个函数，它接受一个string并返回一个int option。

假设你向该函数提供一个字符串s。有两种情况可能发生：当s与key相同时，返回相关联的值；否则，通过查找具有键s的d来返回一个值。

这是直译的结果。

fun insert (key, value) d = fn s => if s = key then SOME value
                                    else d s

- pad