Generating combinations and searching

Full relationality and space-searching

Even if we design a predicate with an implicit idea of input arguments and output arguments, a goal could use variables in any place. So in general we may expect that, by resolution, Prolog attempts to find all substitutions of variables satisfying the relation. This could be obtained automatically in simple cases, or must be explicitly programmed in others.

Either way, Prolog is a language with an inherent ability to capture well the algorithms that need to search solutions in tree-like spaces.

Searching solutions with join/3

File join-search.pl:

join(L1, L2, [a,b,c])
├── {L1/[], L2/[a,b,c]}
└── join(T', L2, [b,c]) : {L1/[a|T']}
    ├── {L1/[a], L2/[b,c]}
    └── join(T'', L2, [c]) : {L1/[a,b|T'']}
        ├── {L1/[a,b], L2/[c]}
        └── join(T''', L2, []) : {L1/[a,b,c|T'']}
            └── {L1/[a,b,c], L2/[]}

We know Prolog will "explore", since the goal matches multiple rules. And thanks to tail recursion, solutions are created while exploring.

Searching solutions: permutation/2

File permutation.pl:

The resolution tree of p([a,b,c], L) (with m2 for member2 and p for permutation):

p([a,b,c], L)
└── m2([a,b,c], X', Zs'), p(Zs', Ys') : {L/[X'|Ys']}
    ├── p([b,c], Ys')  : {L/[a|Ys']}
    │   ├── p([c], Ys'')  : {L/[a,b|Ys'']}  → p([], Ys''')  ...  {L/[a,b,c]}
    │   └── p([b], Ys'')  : {L/[a,c|Ys'']}  ...  [a,c,b]
    ├── p([a,c], Ys')  : {L/[b|Ys']}   ...  [b,a,c]; [b,c,a]
    └── p([a,b], Ys')  : {L/[c|Ys']}   ...  [c,a,b]; [c,b,a]

Full relationality pitfalls: permutation(L, [a,b])?

File perm-pitfall.pl. The same program, asked the other way round. The first answer is found, and then the search goes on forever:

p(L, [a,b])
└── m2(L, a, Zs'), p(Zs', [b])  : {L/...}
    ├── p(Zs', [b]) : {L/[a|Zs']}
    │   ├── m2(Zs', b, Zs''), p(Zs'', [])  ...
    │   │   ├── p(Zs'', []) : {L/[a,b|Zs'']}  →  {L/[a,b]}
    │   │   └── m2(Xs', b, Ys''), p([X'|Ys''], [])  : {L/[a,X',b|Ys'']}  ...
    │   │           └── ...  (to infinity)

Why? With L unbound, member2 can produce lists of any length (it inserts a in an open list), while permutation only stops on the empty list. The notebook stops the runaway search with a stack error.

Pitfalls in searching

• Sometimes building fully relational predicates is not very easy, especially with possibly infinite solutions: it is not generally easy to enumerate them all. This is typically the case when enumeration is not strictly directional.
• Example: checking if a list has the elements 10, 20 and 30 is much easier than enumerating all the lists having 10, 20 and 30.
• Possible solution in principle: in certain applications it would still be possible to iteratively extract what is needed. Essentially, the idea would be to navigate the resolution tree breadth-first instead of depth-first. All solutions would be eventually found, though at very high memory and time costs.

Exploiting exploration to generate combinations

File combinations.pl. A general pattern in Prolog: consider a resolvent G1, G2, ..., Gn. If Gi gives ki solutions, and they do not constrain the execution of the successive goals, then overall we get ∏ ki solutions, obtained by all combinations of the solutions of each Gi.

The composition of goals works as a sort of for-comprehension: it recalls very much what for-comprehension and flatMap are about, what is also called a monadic computation. So in a sense, Prolog computations are always potentially sorts of for-comprehensions. Here 3 × 2 = 6 solutions.

Generating combinations: links in a grid

File gridlink.pl:

gridlink(3, 3, L) gives, in order, link(0,0,0,1), link(0,0,1,0), ..., link(2,2,2,1), link(2,2,1,2): 24 links of the 3 × 3 grid. The generators interval produce all cells, neighbour produces the four candidate neighbours of a cell, and the tests discard those outside the grid.