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

Question

Мы используем концепцию формирования таблицы CYK для получения этих результатов на Прологе. Вот некоторые примеры выходных данных для product_c(+Cell1, + ​​Cell2, -Product):

?- product_c(["A","B"],["C","D"],What).
What = ["AC", "AD", "BC", "BD"].
?- product_c(["A"],[],What).
What = [].

Я пытался использовать string_concat, но это дает мне такие результаты:

What = ["A", "B", "C", "D"].

Я не уверен, как решить эту проблему. Буду признателен за любую оказанную помощь.

Answer 1

Вы тут как бы перепутали. Самое быстрое решение - это взять декартово произведение отсюда, а затем конкатенировать список результатов.

list_List_CartProd(L1,L2,L3):- 
     cartProd(L1,L2,L3,L1).

cartProd(_, [], [], _).

cartProd([], [_|T2], L3, L4):-
    cartProd(L4, T2, L3, L4).

cartProd([H1|T1], [H2|T2], [[H1,H2]|T3], L4):-
    cartProd(T1, [H2|T2], T3, L4).

list_concatEl([],[]).
list_concatEl([X|Xs],[Y|Ys]) :-
    X=[X1,X2],
    string_concat(X1,X2,Y),
    list_concatEl(Xs,Ys).

product_c(L1,L2,L4) :-
    list_List_CartProd(L1,L2,L3),
    list_concatEl(L3,L4).

Если мы проверим это сейчас с вашими делами, мы получим:

?- product_c(["A","B"],["C","D"],What).
What = ["AC", "BC", "AD", "BD"] ;
false.

?- product_c(["A"],[],What). 
What = [] ;
false.

Answer 2

Таким образом, вы можете решить эту проблему следующим образом:

list_pairs(List1, List2,String) :-
    List1 = ["A","B"],
    List2 = ["C","D"],
    findall([X,Y], (member(X, List1), member(Y, List2)), Pairs),
    pairToString(Pairs,String).

pairToString([],[]).
pairToString([[X,Y]|T],[H1|T1]):-
    atomic_list_concat([X,Y], '', Atom),
    atom_string(Atom, H1),
    pairToString(T,T1).

Итак, с findall/3 вы получаете все комбинации из двух списков (Pairs = [["A", "C"], ["A", "D"], ["B", "C"], ["B", "D"]]). Чтобы преобразовать это в список строк, я написал pairToString/2,

?- list_pairs(List1, List2, Pairs).
List1 = ["A", "B"],
List2 = ["C", "D"],
Pairs = ["AC", "AD", "BC", "BD"]