How to produce products on the CYK table in prolog?

Question

We are using the concept of CYK table formation to produce these results on Prolog. Here are some sample outputs for product_c(+Cell1, +Cell2, -Product):

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

I've tried using string_concat, but that gives me results like:

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

I'm not sure how to go about this problem. Any help is much appreciated.

Answer 1

You got here kind of type mix up. The quickest fix would be like taking the cartesian product from here Cartesian prod and then concatenating the result list.

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).

If we test it now with your cases we get:

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

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

Answer 2

So you can solve this problem in this way:

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).

So, with findall/3 you get all the combinations of the two list (Pairs = [["A", "C"], ["A", "D"], ["B", "C"], ["B", "D"]]). To convert this in a list of string, i've written pairToString/2.

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