Cartesian

Description

This concept takes two input lists L and K and creates a list of pairs Res, in which each combination of elements of the first and the second list occurs exactly once.

The result is a list of terms pair(X, Y), where X is an element of list L and Y is an element of list K.

The implementation uses nested foreach do loops to create each combination of elements once. The fromto accumulators are used to collect the result list.

Parameters

L

a list

K

a list

Res

a free variable, will be bound to a list

Schema

:-mode cartesian(+,+,-).
cartesian(L,K,Res):-
        (foreach(X,L),
         fromto([],In,Out,Res),
         param(K) do
            (foreach(Y,K),
             fromto(In,In1,[pair(X,Y)|In1],Out),
             param(X) do
                true
            )
        ).

Comments

Note the use of an empty body (true) in the innermost loop. All calculations are done by parameter passing alone.

If we want to create the elements in the same order as the elements in the input list, we have to exchange input and output arguments of the fromto statements, like so:

:-mode cartesian(+,+,-).
cartesian(L,K,Res):-
        (foreach(X,L),
         fromto(Res,In,Out,[]),
         param(K) do
            (foreach(Y,K),
             fromto(In,[pair(X,Y)|In1],In1,Out),
             param(X) do
                true
            )
        ).

Example

The example builds all pairs of sources and sink nodes for flows and creates contribution structures from them. An additional accumulator NoPath is used to collect cases where there is no route between the nodes.

:-mode create_contribution(+,+,+,-,-).
create_contribution(FromList,ToList,
                    PMatrix,Contribution,NoPath):-
        (foreach(From,FromList),
         fromto([],In1,Out1,Contribution),
         fromto([],NP1,NP2,NoPath),
         param(ToList,PMatrix) do
            (foreach(To,ToList),
             fromto(In1,In,Out,Out1),
             fromto(NP1,NoPath1,NoPath2,NP2),
             param(From,PMatrix) do
                contribution(From,To,From,To,1,PMatrix,
                             In,Out,NoPath1,NoPath2)
            )
        ).