Prolog pivot/2谓词奇偶分支共存时运行异常问题排查

需求说明 #

实现pivot(Before, After)谓词，满足以下规则：

• 若列表元素数为偶数：Before的前后两半长度相同，After是Before的后半部分拼接前半部分
• 若列表元素数为奇数：Before的前后两半长度相同，中间元素保持不变，After是Before的后半部分+中间元素+前半部分
• 核心逻辑：Before的前半部分等于After的后半部分，Before的后半部分等于After的前半部分

问题现状 #

现有实现无法处理pivot(A, [1,2,3,4,5])这类反向查询（已知After求Before），无输出结果，预期结果应为A = [4,5,3,1,2]。

原错误代码 #

pivot(Before,After) :-
    append(A,B,Before),
    length(A,N),
    length(B,N),
    append(B,A,After).
pivot(Before,After) :-
    append(A,B,Before),
    length(A,N),
    N1 is N + 1,
    length(B,N1),
    append(C,Tail,B),
    length(C,1),
    append(Tail,C,F),
    append(F,A,After).

问题分析 #

1. 偶数长度子句：仅支持正向查询（已知Before求After），反向查询时append(A,B,Before)会产生无限多拆分可能，无法收敛到正确长度
2. 奇数长度子句：逻辑方向错误，假设Before拆分为短前半+长后半，但反向查询时After的结构是长前半+短后半，原逻辑无法匹配这种结构，导致无结果

修复方案 #

先明确列表长度，再按长度奇偶性进行固定长度的拆分，确保双向查询都能正常工作：

修复后的代码 #

pivot(Before, After) :-
    % 优先获取已知列表的长度，避免无限回溯
    (length(Before, Len) ; length(After, Len)),
    (   % 偶数长度处理
        Len mod 2 =:= 0,
        N is Len // 2,
        length(A, N),
        length(B, N),
        append(A, B, Before),
        append(B, A, After)
    ;   % 奇数长度处理
        Len mod 2 =:= 1,
        N is (Len - 1) // 2,
        length(A, N),
        length(B, N),
        append(A, [C| B], Before),
        append(B, [C| A], After)
    ).

测试验证 #

• 执行查询pivot(A, [1,2,3,4,5])，返回正确结果：

  A = [4,5,3,1,2]
  

• 执行正向查询pivot([4,5,3,1,2], After)，返回：

  After = [1,2,3,4,5]
  

• 偶数长度测试pivot([1,2,3,4], After)，返回：

  After = [3,4,1,2]
  

内容的提问来源于stack exchange，提问作者Silver-Bullet03