SML 中未解析的弹性记录的错误是什么？

Question

我是 SML 的新手，并向人们询问了我遇到的错误。但是，我找不到问题所在。

收到的错误信息是：

stdIn:10.1-16.48 Error: unresolved flex record (need to know the names       
of ALL  the fields in this context)
type: {1:''Y, 2:''X; ''Z}

我有两个功能。第一个函数是reverse，就是把一个list和return倒过来。例如，将 [1,2,3,4] 反转为 [4,3,2,1]。这个功能绝对没有问题。

fun reverse(L) =
   if L = nil then nil
   else reverse(tl(L)) @ [hd(L)];

下一个函数是 getDirectNode，它有 3 个参数，起始节点、包含边的元组列表和一个空列表。例如，我有一个节点 1 作为第一个参数。我有一个包含所有边的元组列表。 [(1,2),(1,3),(2,3),(2,4)]，用于第二个参数。最后，第三个参数将是一个空列表。

在 getDirectNodes 函数中，它会找到第一个数字为 1 的元组。在这种情况下，它将得到 (1,2) 和 (1,3)。然后，它会将 2 和 3 放入空列表中并 return 它。因此，该函数将 return [2,3].

这是我的函数：

  fun getDirectNodes(startNode,Tuples,list) =
     if Tuples = [] 
        then list
     else if #1(hd(Tuples)) = startNode
        then getDirectNodes(startNode,tl(Tuples),reverse(#2(hd(Tuples)) :: list))
     else
        getDirectNodes(startNode, tl(Tuples),list)

可能导致错误的原因是什么？

Answer 1

您收到的错误是由于 SML 编译器无法推断您拥有的元组类型。 #1 和 #2 不是函数，而是适用于任意类型元组的宏，只要它们有两个元素即可。所以克服这个问题的一个快速方法是添加类型注释，

fun getDirectNodes(startNode, Tuples : (int * int) list, list) = ...

但是既然你发布了这么多你的解决方案，我想就此给出一些一般性的反馈：

反转

您对 reverse 的实施有一些错误：

当你写 if L = [] ... 时，你强制 L 成为 equality type, ''a。这可能看起来很奇怪，因为您只是在测试 L 是否为空，但在 L = [] 可以成为有效表达式之前，其元素也必须具有可比较性。您可以通过模式匹配或使用函数 List.null（使用模式匹配）来避免相等类型限制来解决此问题。
它使用hd和tl代替模式匹配；这些函数是 partial，这意味着如果使用不当，它们可能会在运行时崩溃。您可以通过在空列表和非空列表上使用模式匹配来避免它们。

它递归地使用 @，非常低效：你的算法是 O(n²)因为 @ 的左侧需要线性时间来解决每个递归调用，即几何复杂度：

   reverse [1,2,3,4]
~> reverse [2,3,4] @ [1]
~> reverse [3,4] @ [2] @ [1]
~> reverse [4] @ [3] @ [2] @ [1]
~> reverse [] @ [4] @ [3] @ [2] @ [1]

此时reverse已经使用了O(n)栈space.

~> [] @ [4] @ [3] @ [2] @ [1]
~> [4] @ [3] @ [2] @ [1]       (* 1 recursive call in @ *)
~> [4,3] @ [2] @ [1]           (* 2 recursive calls in @ *)
~> [4,3,2] @ [1]               (* 3 recursive calls in @ *)
~> [4,3,2,1]                   (* 4 recursive calls in @ *)

此时 reverse 已经使用了 O(n + (n-1) + ... + 1) = O(n²) 次递归调用。

实际上有一个内置函数叫做rev。

是这样实现的：

fun rev xs =
  let fun rev_helper []      xs_bw = xs_bw
        | rev_helper (x::xs) xs_bw = rev_helper xs (x::xs_bw)
  in rev_helper xs [] end

并称它为：

   rev [1,2,3,4]
~> rev_helper [1,2,3,4] []
~> rev_helper [2,3,4] [1]   (* 1 recursive call *)
~> rev_helper [3,4] [2,1]   (* 1 recursive call *)
~> rev_helper [4] [3,2,1]   (* 1 recursive call *)
~> rev_helper [] [4,3,2,1]  (* 1 recursive call *)
~> [4,3,2,1]

使用heap内存而不是stack内存，并且O(n)递归调用。

getDirectNodes

以下是评论的非详尽列表：

同样的事情。平等类型在这里适用。 Tuples = [].
有list作为累加结果很爽！我可能会称它为更具描述性的东西，就像我称呼 Tuples 类似 edges 来描述它的 content 而不是它的 type.
虽然使用像 list 这样的累积结果很简洁，但这意味着您的函数将一个空列表作为输入。如果调用者向它提供一个非空列表怎么办？公开这个额外的参数会留下错误的空间，所以将它隐藏在一个内部函数中，就像我对 rev_helper.
使用模式匹配代替hd和tl。
您对 reverse 的使用似乎很有意义：您已经体验过 list 以相反的方式结束。但是，与其在每次递归调用时在 list 上调用 reverse，不如在最后（当 Tuples 为空时）执行一次一次。

鉴于此建议，这里是您的代码的变体：

fun getDirectNodes (startNode, []) = []
  | getDirectNodes (startNode, (x, endNode) :: edges) =
    if x = startNode
    then endNode :: getDirectNodes (startNode, edges)
    else getDirectNodes (startNode, edges)

以及使用内部尾递归函数和末尾单个 rev 的变体：

fun getDirectNodes (startNode, edges) =
    let fun helper ([], endNodes) = endNodes
          | helper ((x, endNode) :: edges, endNodes) =
            if x = startNode
            then helper (edges, endNode :: endNodes)
            else helper (edges, endNodes)
    in rev (helper (edges, [])) end

下面是我如何使用高阶函数实现它：

fun getDirectNodes (startNode, edges) =
    List.map #2 (List.filter (fn (x, _) => x = startNode) edges)

我没有收到警告的原因。尽管没有任何类型注释，我在这里使用 #2 是因为我在代码 fn (x, _) => ... 中对 edges 的元素进行模式匹配。这将 edges 限制为 2 元组列表。

运行这个：

- getDirectNodes (1, [(1,2),(1,3),(2,3),(2,4)]);
> val it = [2, 3] : int list

SML 中未解析的弹性记录的错误是什么？

What is error of unresolved flex record in SML?

sml

smlnj

反转

getDirectNodes