如何在SML中的else if语句中解决“未解析的flex记录”？

Question

我想找到当前给定节点直接或间接连接的节点列表。例如，我有一个节点列表：

[1,2]

和元组列表，每个元组代表一个直接边缘：

[(1,5),(2,4),(4,6)]

所以，我正在寻找的节点是

[1,2,5,4,6]

因为，1连接到5,2连接到4.然后，4连接到6.为了实现这一点，我需要两个队列和一个列表。每次发现新节点时，我们都会将新节点附加到队列和列表中。然后，我们删除队列的第一个节点，然后转到下一个节点。如果新节点连接到队列的当前节点。然后，我们将新节点添加到队列和列表中。

我们一直这样做，直到队列为空，我们返回列表。

所以现在，我有一个追加函数，它将列表附加到另一个列表：

fun append(xs, ys) = 
   case ys of 
        [] => xs
    | (y::ys') => append(xs @ [y], ys')

然后，我有一个名为getIndirectNodes的函数，它打算返回给定节点间接连接的节点列表，但抛出“未解析的弹性记录”。据说List1和List2具有相同的项目。但是，List1服务队列，list2服务器作为要返回的列表。

  fun getIndirectNode(listRoleTuples, list1, list2) =
      if list1 = []
          then list2
     else if hd(list1) = #1(hd(listRoleTuples))
        then (
            append(list1,#2(hd(listRoleTuples)) :: []);
            append(list2,#2(hd(listRoleTuples)) :: []);
            getIndirectNode(listRoleTuples,tl(list1),list2)
            )
        else
           getIndirectNode(listRoleTuples,tl(list1),list2)

如果我删除else if语句，它完全正常。但是，这不是我打算做的。问题出在else if语句中。我该怎么办才能修复它？

Answer 1

SML需要确切地知道元组具有什么形状才能解构它。 您可以指定参数的类型 - listRoleTuples : (''a * ''a) list - 但使用模式匹配是一个更好的主意。

（该代码还有许多其他问题，但这是您问题的答案。）

Answer 2

似乎你的一个同学在very related task中有这个确切的元组问题。

确保在再次提出相同问题之前浏览StackOverflow问答。

至于获取间接节点，这可以通过定点迭代来解决。

首先，您获得所有直接节点，然后获得直接节点的直接节点。

并且您以递归方式执行此操作，直到不再以这种方式出现新节点。

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

fun toSet xs =
    ... sort and remove duplicates ...

fun getReachableNodes (startNodes, edges) =
    let
      fun f startNode = getDirectNodes (startNode, edges)
      val startNodes = toSet startNodes
      val endNodes = toSet (List.concat (List.map f startNodes))
    in
      if startNodes = endNodes
      then endNodes
      else getReachableNodes (startNodes @ endNodes, edges)
    end

这并不完全找到间接的终端节点;它找到startNodes可以直接或间接访问的所有节点，它包括startNodes本身，即使它们不能直接或间接地自己访问。

我试图通过使用sets作为数据类型来简化此练习;它甚至比实际的，有效的集合类型的实现更整洁，例如，使用平衡的二叉搜索树。通过向集合添加元素更容易看出是否没有新节点，因为如果集合已经包含元素，则在添加元素之前和之后它将等同于自身。

当有意义时，我尝试使用高阶函数。例如，给定一个我希望在每个元素上做同样事情的列表，List.map会生成一个结果列表。但是自从我想做的事情，getDirectNodes (startNode, edges)产生一个列表，然后List.map f产生一个列表列表。所以List.concat将其折叠成一个列表。

List.concat (List.map f xs)

这是很常见的事情。