Prolog统一和优化

Question

我想编写合并两个列表的合并函数,我可以通过编写两个(合并)谓词来做到这一点,其中一个是元素H1 = <H2,另一个是H1> H2但是我想写if-the-else条件但是然后统一失败,我不知道该怎么做.这是我的代码:

merge([H1|T1],[H2|T2],List):-
  (
   H1 =< H2 ->
        NewList = [H1|List],
        merge(T1,[H2|T2],NewList)
  ;
        NewList = [H2|List],
        merge([H1|T1],T2,NewList)
  ).

merge([],L,L).
merge(L,[],L).

我知道问题是什么,如果我写两个合并谓词,我可以避免它,但我不知道如何在这里做,我被困:(

模式匹配在这里失败:

Answer 1

你其实非常接近.看看这个痕迹:

?- trace, merge([1,3,5,6], [2,4,7,8], X).
   Call: (9) merge([1, 3, 5, 6], [2, 4, 7, 8], _6684) ? creep
   Call: (10) 1=<2 ? creep
   Exit: (10) 1=<2 ? creep
   Call: (10) _7050=[1|_6684] ? creep
   Exit: (10) [1|_6684]=[1|_6684] ? creep
   Call: (10) merge([3, 5, 6], [2, 4, 7, 8], [1|_6684]) ? creep
   Call: (11) 3=<2 ? creep
   Fail: (11) 3=<2 ? creep
   Redo: (10) merge([3, 5, 6], [2, 4, 7, 8], [1|_6684]) ? creep
   Call: (11) _7062=[2, 1|_6684] ? creep
   Exit: (11) [2, 1|_6684]=[2, 1|_6684] ? creep
   Call: (11) merge([3, 5, 6], [4, 7, 8], [2, 1|_6684]) ? creep
   Call: (12) 3=<4 ? creep
   Exit: (12) 3=<4 ? creep
   Call: (12) _7074=[3, 2, 1|_6684] ? creep
   Exit: (12) [3, 2, 1|_6684]=[3, 2, 1|_6684] ? creep
   Call: (12) merge([5, 6], [4, 7, 8], [3, 2, 1|_6684]) ? creep
   Call: (13) 5=<4 ? creep
   Fail: (13) 5=<4 ? creep
   Redo: (12) merge([5, 6], [4, 7, 8], [3, 2, 1|_6684]) ? creep
   Call: (13) _7086=[4, 3, 2, 1|_6684] ? creep
   Exit: (13) [4, 3, 2, 1|_6684]=[4, 3, 2, 1|_6684] ? creep
   Call: (13) merge([5, 6], [7, 8], [4, 3, 2, 1|_6684]) ? creep
   Call: (14) 5=<7 ? creep
   Exit: (14) 5=<7 ? creep
   Call: (14) _7098=[5, 4, 3, 2, 1|_6684] ? creep
   Exit: (14) [5, 4, 3, 2, 1|_6684]=[5, 4, 3, 2, 1|_6684] ? creep
   Call: (14) merge([6], [7, 8], [5, 4, 3, 2, 1|_6684]) ? creep
   Call: (15) 6=<7 ? creep
   Exit: (15) 6=<7 ? creep
   Call: (15) _7110=[6, 5, 4, 3, 2, 1|_6684] ? creep
   Exit: (15) [6, 5, 4, 3, 2, 1|_6684]=[6, 5, 4, 3, 2, 1|_6684] ? creep

在这个递归深度的时刻,你几乎有了解决方案.然后它开始出错了:

   Call: (15) merge([], [7, 8], [6, 5, 4, 3, 2, 1|_6684]) ? creep
   Fail: (15) merge([], [7, 8], [6, 5, 4, 3, 2, 1|_6684]) ? creep
   Redo: (14) merge([6], [7, 8], [5, 4, 3, 2, 1|_6684]) ? creep
   Fail: (14) merge([6], [7, 8], [5, 4, 3, 2, 1|_6684]) ? creep
   Redo: (13) merge([5, 6], [7, 8], [4, 3, 2, 1|_6684]) ? creep
   Fail: (13) merge([5, 6], [7, 8], [4, 3, 2, 1|_6684]) ? creep
   Redo: (12) merge([5, 6], [4, 7, 8], [3, 2, 1|_6684]) ? creep
   Fail: (12) merge([5, 6], [4, 7, 8], [3, 2, 1|_6684]) ? creep
   Redo: (11) merge([3, 5, 6], [4, 7, 8], [2, 1|_6684]) ? creep
   Fail: (11) merge([3, 5, 6], [4, 7, 8], [2, 1|_6684]) ? creep
   Redo: (10) merge([3, 5, 6], [2, 4, 7, 8], [1|_6684]) ? creep
   Fail: (10) merge([3, 5, 6], [2, 4, 7, 8], [1|_6684]) ? creep
   Redo: (9) merge([1, 3, 5, 6], [2, 4, 7, 8], _6684) ? creep
   Fail: (9) merge([1, 3, 5, 6], [2, 4, 7, 8], _6684) ? creep

那你的代码有什么问题？主要有两件事:你正在构建反转的结果(并非罕见)并且你没有一个好的方法来传回它.安排结果变量肯定是解决这些问题的一种方法,类似于Luai所说的:

merge(X,Y,Z) :- merge(X, Y, [], Z).

merge([H1|T1],[H2|T2],List,NewList):-
  (
   H1 =< H2 ->
        merge(T1,[H2|T2],[H1|List],NewList)
  ;
        merge([H1|T1],T2,[H2|List],NewList)
  ).

merge([],R,LRev,Res) :- reverse(LRev, L), append(L,R,Res).
merge(R,[],LRev,Res) :- reverse(LRev, L), append(L,R,Res).

或者你必须找出另一种方法,例如通过传递列表的尾部,如下所示:

merge2([H1|T1], [H2|T2], MT) :-
    (H1 =< H2 ->
        MT=[H1|MT2],
        merge2(T1, [H2|T2], MT2)
    ;
        MT=[H2|MT2],
        merge2([H1|T1], T2, MT2)
    ).
merge2([], T2, T2).
merge2(T2, [], T2).

我个人赞成这种做法.

Answer 2

你认为递归是错误的方式.第三个参数是合并的结果.

在这里你使用:

merge([H1|T1],[H2|T2],List):-
  (
   H1 =< H2 ->
        NewList = [H1|List],
        merge(T1,[H2|T2],NewList)
  ;
        NewList = [H2|List],
        merge([H1|T1],T2,NewList)
  ).

merge([],L,L).
merge(L,[],L).

换句话说,你是不是在前面加上递归调用的输出,你其实希望递归输出开始与H1和/或H2然后弹出从结果元素,并通过其余(的尾巴名单)的结果.

因此,快速解决方法是扭转:

merge([H1|T1],[H2|T2],List):-
  (
   H1 =< H2 ->
        List = [H1|NewList],
        merge(T1,[H2|T2],NewList)
  ;
        List = [H2|NewList],
        merge([H1|T1],T2,NewList)
  ).

merge([],L,L).
merge(L,[],L).

现在我们注意到有一些重复的代码,所以我们可以将其重写为:

merge([H1|T1],[H2|T2],[Min|NewList]):-
  (
   H1 =< H2 ->
        Min = H1,
        merge(T1,[H2|T2],NewList)
  ;
        Min = H2,
        merge([H1|T1],T2,NewList)
  ).

merge([],L,L).
merge(L,[],L).

但就个人而言,我发现两个子句的解决方案更优雅:

merge([H1|T1],[H2|T2],[H1|T3]) :-
   H1 =< H2,
   merge(T1,[H2|T2],T3).

merge([H1|T1],[H2|T2],[H2|T3]) :-
   H1 > H2,
   merge([H1|T1],T2,T3).

merge([],L,L).
merge(L,[],L).