在 Curry 中，如何让 inverse reverse 函数终止？

Question

我正在使用 PAKCS Curry 编译器，版本 3.3.0。

这是 Curry 中的简单列表反转函数（它在 Haskell 中也有效）：

rev :: [a] -> [a]
rev [] = []
rev (x : xs) = (rev xs) ++ [x]

让我们尝试反转函数，即找到一个列表 l 其反转是 [1..5]:

> rev l =:= [1 .. 5] where l free
{l=[5,4,3,2,1]} True
...hang...

库里能解方程真好。然而，它进入了一个寻找更多解决方案的无限循环。

这是 Prolog 中的等效谓词：

rev([], []).
rev([X | L], M) :- rev(L, LR), append(LR, [X], M).

Prolog 谓词也无法在相反方向终止：

?- rev(L, [1, 2, 3, 4, 5]).
L = [5, 4, 3, 2, 1] ;
...hang...

在 Prolog 中，我可以通过添加 L 及其逆具有相同长度的约束来帮助终止：

rev([], []).
rev([X | L], M) :- same_length([X | L], M), rev(L, LR), append(LR, [X], M).

有了这个额外的约束，谓词在两个方向上都终止了。

在 Curry 中，是否可以添加类似的约束，或者以其他方式帮助查询终止？

我尝试定义一个具有类似 same_length 约束的反函数：

same_length :: [a] -> [b] -> Bool
same_length [] [] = True
same_length (_ : _) [] = False
same_length [] (_ : _) = False
same_length (_ : xs) (_ : ys) = same_length xs ys

rev :: [a] -> [a]
rev [] = []
rev (x : xs) = (rev xs) ++ [x]

rev2 :: Data a => [a] -> [a]
rev2 b@(rev a) | same_length a b = a

然而它没有帮助：'rev2 [1 .. 5]' 也找到了一个解决方案，然后未能终止。

Answer 1

您考虑列表长度的想法非常好。但是，在您对 rev2 的定义中，函数模式 b@(rev a) 仍然在检查守卫 same_length a b 之前进行评估，因此，您的评估不会在找到第一个解决方案后终止。

我能想到的最简单的解决方案是在守卫的开头移动 same_length 约束，而在末尾有统一约束 - 使用 (&&).[=20 组合=]

revInv xs | same_length xs ys && rev ys =:= xs = ys where ys free

进一步完善逆定义w.r.t。关于列表元素的非严格性（例如，如果其中一个元素失败，则上面的定义失败），您甚至可以使用非严格统一运算符 =:<= 而不是严格统一运算符 =:=.

revInv' xs | same_length xs ys && rev ys =:<= xs = ys where ys free

为了比较，请考虑以下两个表达式。

> head (revInv [1, failed, 2])
*** No value found!
> head (revInv' [1, failed, 2])
2

在 Curry 中，如何让 inverse reverse 函数终止？

In Curry, how to get inverse reverse function to terminate?

curry