Как указать все пары в заданном списке на Прологе?

Использование select/3 дважды (или select/3 один раз и member/2 один раз) позволит вам достичь того, чего вы хотите. Я позволю вам разобраться в деталях и попрошу помощи, если это все еще проблематично.

Кстати, синтаксис Пролога для списка не (a, b, c), а [a, b, c] (ну, это синтаксический сахар, но я остановлюсь на этом).

редактировать: как указал @WillNess, вы не ищете какую-либо пару (X, Y), а только пары, где X находится перед Y в списке.

DCG действительно хорошо подходят: как описано @false, они могут создавать графически привлекательное решение:

... --> [] | [_], ... .

pair(L, X-Y) :-
    phrase((..., [X], ..., [Y], ...), L).

В качестве альтернативы, если вы используете SWI-Prolog, вызов append/2 тоже делает свое дело аналогичным образом, но менее эффективно, чем DCG:

pair2(L, X-Y) :-
    append([_, [X], _, [Y], _], L).

Вы можете сделать это с помощью базовой рекурсии, как предложил @WillNess в своем комментарии. Я оставлю эту часть для него, чтобы детализировать, если это необходимо!

Итак, чтобы перевести Haskell

pairs (x:xs) = [ (x,y) | y<-xs ]
                ++ pairs xs 
pairs []     = []

как предикат Пролога с возвратом, это простой и короткий,

pair([X|XS],X-Y):- member( ... ,XS).  %% fill in the '...' here
pair([_|XS],P) :- pair(XS, ... ).     %%
%% pair([],_) :- false. 

Чтобы получить все возможные пары, используйте findall:

pairs(L,PS):- findall(P, pair(L,P), PS).

Рассмотрите возможность использования bagof, если ваши списки могут содержать логические переменные. Однако управление возвратом bagof может быть сложной проблемой.

pairs также можно записать как детерминированное, рекурсивное определение без возврата, конструирующее свой выходной список с помощью параметра-аккумулятора — здесь в порядке сверху вниз, что делает его действительно списком различий:

pairs([X|T],PS):- T=[_|_], pairs(X,T,T,PS,[]) ; T=[], PS=[].
pairs([],[]).

pairs(_,[],[],Z,Z).
pairs(_,[],[X|T],PS,Z):- pairs(X,T,T,PS,Z).
pairs(X,[Y|T],R,[X-Y|PS],Z):- pairs(X,T,R,PS,Z).

Вот возможный способ решения этого.

Следующий предикат combine/3 истинен, если третий аргумент соответствует списку, содержащему пары, где первый элемент каждой пары равен первому аргументу combine/3. Второй элемент каждой пары будет соответствовать элементу списка во втором аргументе предиката combine/3. Несколько примеров того, как должен работать combine/3:

?- combine(a,[b],X).
X = [pair(a,b)]

?- combine(a,[b,c,d],X).
X = [pair(a,b), pair(a,c), pair(a,d)]

Возможный способ определения combine/3:

combine(A,[B],[pair(A,B)]) :- !.

combine(A,[B|T],C) :-
  combine(A,T,C2),          % Create pairs for remaining elements in T.
  append([pair(A,B)],C2,C). % Append current pair and remaining pairs C2.
                            % The result of append is C.

Теперь combine/3 можно использовать для определения pair/2:

pairs([],[]).      % Empty list will correspond to empty list of pairs.
pairs([H|T],P) :-  % In case there is at least one element.
  nonvar([H|T]),   % In this case it expected that [H|T] is instantiated.
  pairs(H,T,P).

pairs(A,[B],[pair(A,B)]) % If remaining list contains exactly one element,
  :- !.                  % then there will be only one pair(A,B).
pairs(A,[B|T],P) :-      % In case there are at least two elements.
  combine(A,[B|T],P2),   % For each element in [B|T] compute pairs
                         % where first element of each pair will be A.
  pairs(B,T,P3),         % Compute all pairs without A recursively.
  append(P2,P3,P).       % Append results P2 and P3 together.

Пример использования:

?- pairs([a,b,c],X).
X = [pair(a, b), pair(a, c), pair(b, c)].

?- pairs([a,b,c,d],X).
X = [pair(a, b), pair(a, c), pair(a, d), pair(b, c), pair(b, d), pair(c, d)].

Вы можете использовать append/ для перебора списка:

?- append(_,[X|R],[a,b,c,d]).
X = a,
R = [b, c, d] ;
X = b,
R = [c, d] ;
X = c,
R = [d] ;
X = d,
R = [] ;
false.

Затем используйте member/2, чтобы сформировать пару X-Y для каждого Y в R:

?- append(_,[X|R],[a,b,c,d]), member(Y,R), Pair=(X-Y).
X = a,
R = [b, c, d],
Y = b,
Pair = a-b ;
X = a,
R = [b, c, d],
Y = c,
Pair = a-c ;
X = a,
R = [b, c, d],
Y = d,
Pair = a-d ;
X = b,
R = [c, d],
Y = c,
Pair = b-c ;
X = b,
R = [c, d],
Y = d,
Pair = b-d ;
X = c,
R = [d],
Y = d,
Pair = c-d ;
false.

Затем используйте findall/3, чтобы собрать все пары в список:

?- findall(X-Y, (append(_,[X|R],[a,b,c,d]), member(Y,R)), Pairs).
Pairs = [a-b, a-c, a-d, b-c, b-d, c-d].

Таким образом, ваше окончательное решение может быть выражено как:

pairs(List, Pairs) :-
    findall(X-Y, (append(_,[X|R],List), member(Y,R)), Pairs).

Пример использования:

?- pairs([a,b,c,d], Pairs).
Pairs = [a-b, a-c, a-d, b-c, b-d, c-d].