Рекурсивные определения в прологе

Question

Как написать рекурсивное определение в Прологе, чтобы создать чередующийся список следующим образом:

alternate(K, L, M) выполняется, если список M получен путем элементы поочередно из списков K и L, например ::

?- alternate([1,2,3,4,5,6],[a,b,c],Zs).

Zs = [1, a, 2, b, 3, c, 4, 5, 6]

Кроме того, если один список длиннее другого, то остальные элементы более длинного списка появляются в конце результата, M.

Моя попытка решить эту проблему следующая, но она не работает:

alternate([],L,L).
alternate(K, [], K).
alternate([Firstk|Restk], [Firstl|Restl], M):-
   K is [Firstk|Restk], L is [Firstl|Restl],
   M is [M|[Firstk]], K is Restk,
   M is [M|[Firstl]], L is Restl,
   alternate(K, L, M).

Любые советы или пожелания приветствуются

Answer 1

Вы могли бы описать это отношение, переключив первые два аргумента в рекурсивном вызове, как предложено @WillNess в комментариях. А поскольку два списка могут различаться по длине, было бы полезно иметь предикат, который описывает списки в целом, чтобы избежать совпадения произвольных терминов в нерекурсивном правиле. Также было бы неплохо иметь несколько более описательное имя, которое отражает реляционную природу предиката. Учитывая все это, предикат может выглядеть примерно так:

islist([]).
islist([_|T]) :-
   islist(T).

list_list_interlocked([],L,L) :-
   islist(L).
list_list_interlocked([X|Xs],Ys,[X|Zs]) :-
   list_list_interlocked(Ys,Xs,Zs).

Ваш пример запроса работает как ожидалось:

?- list_list_interlocked([1,2,3,4,5,6],[a,b,c],Zs).
Zs = [1, a, 2, b, 3, c, 4, 5, 6].

Предикат также работает, если второй список длиннее:

?- list_list_interlocked([1,2,3],[a,b,c,d,e,f],Zs).
Zs = [1, a, 2, b, 3, c, d, e, f].

И это работает только со списками:

?- list_list_interlocked(definitelynolist,[],Zs).
false.

?- list_list_interlocked([],definitelynolist,Zs).
false.

Последняя причина, по которой вам нужно islist/1. Если вы определите нерекурсивное правило следующим образом: list_list_interlocked([],L,L)., то Prolog может объединить произвольные термины с L, и запрос выдаст неверный результат:

?- list_list_interlocked([],definitelynolist,Zs).
Zs = definitelynolist.

Предикат также можно использовать в другом направлении, например, Какие списки дают [1,a,2,b,3,c] при блокировке? :

?- list_list_interlocked(X,Y,[1,a,2,b,3,c]).
X = [],
Y = [1, a, 2, b, 3, c] ;
X = [1, a, 2, b, 3, c],
Y = [] ;
X = [1],
Y = [a, 2, b, 3, c] ;
X = [1, 2, b, 3, c],
Y = [a] ;
X = [1, 2],
Y = [a, b, 3, c] ;
X = [1, 2, 3, c],
Y = [a, b] ;
X = [1, 2, 3],
Y = [a, b, c] ;
false.

Answer 2

Мне нравятся другие ответы, особенно один от @tas. Но все же, этот подход чувствует себя слишком ... "маленький шаг". Если вы обрабатываете два списка и должны выбирать элементы из каждого, почему бы не выбрать эти два элемента одновременно вместо того, чтобы выбирать только из одного и менять списки? Это похоже на «алгоритм», а не на логическое декларативное описание отношения.

Поэтому я предлагаю следующее:

alternate([], Ys, Ys).
alternate([X|Xs], [], [X|Xs]).
alternate([A | As], [B | Bs], [A, B | ABs]) :-
    alternate(As, Bs, ABs).

Общий случай, чередующий два непустых списка, охватывается третьим пунктом: первые два элемента чередующегося списка являются первыми элементами двух списков, которые должны чередоваться. Первые два предложения касаются только случая, когда один или другой из списков пуст. (Вы можете добавить к ним islist целей @ tas, чтобы убедиться, что другой аргумент действительно является правильным списком.)

Вот тесты:

?- alternate([1,2,3,4,5,6],[a,b,c],Zs).
Zs = [1, a, 2, b, 3, c, 4, 5, 6] ;
false.

?- alternate([1,2,3],[a,b,c,d,e,f],Zs).
Zs = [1, a, 2, b, 3, c, d, e, f].

?- alternate(Xs, Ys, [1,a,2,b,3,c]).
Xs = [],
Ys = [1, a, 2, b, 3, c] ;
Xs = [1, a, 2, b, 3, c],
Ys = [] ;
Xs = [1],
Ys = [a, 2, b, 3, c] ;
Xs = [1, 2, b, 3, c],
Ys = [a] ;
Xs = [1, 2],
Ys = [a, b, 3, c] ;
Xs = [1, 2, 3, c],
Ys = [a, b] ;
Xs = [1, 2, 3],
Ys = [a, b, c] ;
false.

(В SWI-Prolog, который индексирует только первый аргумент, это оставляет немного больше точек выбора, чем некоторые альтернативы.)

Answer 3

Просто напишите два предиката, где один вызывает другой, и наоборот, например:

alternate1([],[],[]).
alternate1([],L,L).
alternate1([H|T],L,[H|T1]):-
    alternate2(T,L,T1).
alternate2([],[],[]).
alternate2(L,[],L).
alternate2(L,[H|T],[H|T1]):-
    alternate1(L,T,T1).

?- alternate1([1,2,3,4,5,6],[a,b,c],Zs).
Zs = [1, a, 2, b, 3, c, 4, 5, 6]
false