对列表进行递归时出现 SML [循环] 错误

Question

我正在尝试构建一个压缩 2 个给定函数的函数，忽略较长列表的长度。

fun zipTail L1 L2 = 
    let 
      fun helper buf L1 L2 = buf
        | helper buf [x::rest1] [y::rest2] = helper ((x,y)::buf) rest1 rest2
    in
      reverse (helper [] L1 L2)
    end

当我这样做时，我收到了错误消息：

Error: right-hand-side of clause doesn't agree with function result type [circularity]

我很好奇圆度错误是什么，我应该如何解决这个问题。

Answer 1

出现循环问题 many 。

您想要 (x::rest1) 而不是 [x::rest1]。

问题是语法错误。

模式 [foo] 将匹配其中只有一个元素的列表，foo。
模式 x::rest1 将匹配其中至少包含一个元素 x 及其（可能为空）尾部 rest1 的列表。 这是您想要的模式。但是该模式包含一个中缀运算符，因此您需要在它周围添加一个括号。
组合模式 [x::rest1] 将匹配一个列表恰好一个元素本身是一个列表至少一个元素。此模式有效，但过于具体，并且本身不会引发类型错误。

出现循环错误的原因是编译器无法推断出 rest1 的类型。由于它出现在 :: 模式构造函数的右侧，因此它必须是 'a list，并且由于它单独出现，因此它必须是 'a。尝试 unify 'a = 'a list 就像找到方程 x = x + 1 的解.

您可能会说 "well, as long as 'a = 'a list list list list list ... infinitely, like ∞ = ∞ + 1, that's a solution." 但是 Damas-Hindley-Milner type system 并没有将这种无限构造视为定义明确的类型。并且创建单例列表 [[[...x...]]] 将需要无限数量的括号，因此无论如何它都不完全实用。

一些更简单的循环示例：

fun derp [x] = derp x：这是对您的情况的简化，其中 derp 的第一个参数中的模式表示一个列表，而 x 表示此列表中的元素类型必须与列表本身的类型相同。
fun wat x = wat [x]：这是一个非常相似的情况，其中 wat 接受类型为 'a 的参数并使用'列表 类型的参数。当然，'a 可以是一个 'a list，但是 'a list 也必须是一个'a list列表,等等

正如我所说，由于句法错误概念，您正在循环。列出模式。但循环性并不局限于列表。它们是组合类型和自引用的产物。这是一个没有列表的示例 Function which applies its argument to itself?:

fun erg x = x x：在这里，x 可以被认为是具有 'a 类型的开头，但将其视为应用于自身的函数，它还必须具有类型 'a -> 'b。但是如果 'a = 'a -> 'b，那么 'a -> b = ('a -> 'b) -> 'b，以及 ('a -> 'b) -> b = (('a -> 'b) -> b) -> b，等等。 SML 编译器很快确定这里没有解决方案。

这并不是说具有循环类型的函数总是无用的。作为 newacct points out, turning purely anonymous functions into recursive ones actually requires this, like in the Y-combinator.

内置ListPair.zip 是usually tail-recursive，顺便说一下。

Answer 2

这里有很多问题

1) 在 helper buf L1 L2 = buf 中，模式 buf L1 L2 将匹配所有可能的输入，使您的下一个子句（一旦调试）变得多余。在上下文中，我认为您的意思是 helper buf [] [] = buf，但是在列表大小不等的情况下，您会运行陷入 non-exhaustive 匹配的问题。最简单的解决方法是将第二个子句（带有 x::rest1 的子句）移到顶行，然后使用第二个模式来捕获至少一个列表为空的情况。

2) [xs::rest] 是一个模式，它匹配一个包含 1 个项目的列表，其中该项目是一个非空列表。那不是你的注意力。您需要使用 (,) 而不是 [,].

3) reverse 应该是 rev.

进行这些更改后，您的定义将变为：

fun zipTail L1 L2 = 
let 
    fun helper buf (x::rest1) (y::rest2) = helper ((x,y)::buf) rest1 rest2
      | helper buf rest1 rest2 = buf

in
    rev (helper [] L1 L2)
end;

按预期工作。

错误信息本身有点难以理解，但你可以这样想。在

helper buf [x::rest1] [y::rest2] = helper ((x,y)::buf) rest1 rest2

左边括号里的东西是列表的列表。所以它们的类型是 'a list list，其中 'a 是 x 的类型。在 x::rest1 中 rest1 的类型必须是 'a list 因为 rest1 也出现在等号的另一边与 [x::rest1] 相同的位置然后rest1 的类型必须与 [x::rest1] 的类型相同，即 'a list list。因此 rest1 必须同时是 'a list 和 'a list list，这是不可能的。

如果你试图理解 'a list list = 'a list，那么循环就来自于你需要一个 'a 和 'a = 'a list 的类型。这将是一个类型，其值由相同类型的值列表组成，并且该列表中的项目的值本身必须是相同类型的元素列表......这是一个永无止境的粘性循环.

对列表进行递归时出现 SML [循环] 错误

SML [circularity] error when doing recursion on lists

type-inference

sml

smlnj