如何将Prolog的cut剪枝逻辑转换为Curry语言的惯用实现？

以下是最初的Curry实现的算法，输入参数n，可匹配编辑距离在n以内的两个字符串：

lev :: Eq a => Int -> [a] -> [a] -> ()
lev n (a : b) (a : c) =
  lev n b c
lev n (_ : b) (_ : c) | n > 0 =
  lev (n - 1) b c
lev n (_ : b) c | n > 0 =
  lev (n - 1) b c
lev n b (_ : c) | n > 0 =
  lev (n - 1) b c
lev n [] [] =
  ()

该算法修改了朴素递归逻辑，限制了允许尝试的编辑操作次数，一旦使用完n次编辑机会就会终止。

将上述逻辑翻译为Prolog代码如下：

p(_, [], []).
p(N, [A|B], [A|C]) :-
  p(N, B, C).
p(N, [_|B], C) :-
  N>0,
  p(N-1, B, C).
p(N, B, [_|C]) :-
  N>0,
  p(N-1, B, C).
p(N, [_|B], [_|C]) :-
  N>0,
  p(N-1, B, C).

上述两段代码虽然限制了编辑次数，但没有控制分支因子，因此时间复杂度随输入大小呈指数级增长。在Prolog中可以通过添加cut（!，剪枝操作符）解决该问题：

p(_, [], []).
p(N, [A|B], [A|C]) :-
  !, p(N, B, C).
p(N, [_|B], C) :-
  N>0,
  p(N-1, B, C).
p(N, B, [_|C]) :-
  N>0,
  p(N-1, B, C).
p(N, [_|B], [_|C]) :-
  N>0,
  p(N-1, B, C).

添加cut后分支因子被限制，算法时间复杂度降为线性。但Curry语言不支持cut操作，以下是Curry中两种惯用的等价剪枝实现方案： #

方案1：显式守卫消除重叠分支 #

Curry的模式匹配默认会回溯所有符合条件的分支，我们可以给编辑操作的分支添加额外守卫，保证只有当「当前两个字符不相等」时才会进入这些分支，从根源上消除分支重叠，避免不必要的回溯：

lev :: Eq a => Int -> [a] -> [a] -> ()
-- 字符相等时优先匹配，无编辑消耗
lev n (a : b) (a : c) = lev n b c
-- 替换操作：字符不等且有剩余编辑次数时触发
lev n (x : b) (y : c) | x /= y, n > 0 = lev (n - 1) b c
-- 删除操作：删除第一个字符串当前字符，仅当字符不等/第二个字符串已空且有剩余次数时触发
lev n (x : b) [] | n > 0 = lev (n - 1) b []
lev n (x : b) (y : c) | x /= y, n > 0 = lev (n - 1) b (y : c)
-- 插入操作：相当于删除第二个字符串当前字符，仅当字符不等/第一个字符串已空且有剩余次数时触发
lev n [] (y : c) | n > 0 = lev (n - 1) [] c
lev n (x : b) (y : c) | x /= y, n > 0 = lev (n - 1) (x : b) c
-- 匹配成功终止条件
lev _ [] [] = ()

这种方案是纯声明式的，不需要依赖任何搜索原语，是Curry社区比较推荐的写法。 #

方案2：用once组合子封装搜索 #

如果不想改动原有递归逻辑，可以直接使用Curry标准库提供的once搜索组合子，它只会取搜索空间的第一个成功结果，直接终止后续回溯，和Prolog中cut的效果完全等价：

import Control.Search (once)

lev :: Eq a => Int -> [a] -> [a] -> ()
lev n xs ys = once $ lev' n xs ys
  where
    lev' n (a : b) (a : c) = lev' n b c
    lev' n (_ : b) (_ : c) | n > 0 = lev' (n - 1) b c
    lev' n (_ : b) c | n > 0 = lev' (n - 1) b c
    lev' n b (_ : c) | n > 0 = lev' (n - 1) b c
    lev' _ [] [] = ()

这种方案改动量极小，只需要给原有递归逻辑套一层once封装即可，适合快速改造现有代码的场景。 #

内容的提问来源于stack exchange，提问作者Wheat Wizard