Translate list comprehension to Prolog

Question

I have a list comprehension in Haskell that I want to translate to Prolog.

The point of the list comprehension is rotating a 4 by 4 grid:

rotate :: [Int] -> [Int]
rotate grid = [ grid !! (a + 4 * b) | a <- [0..3], b <- [0..3] ]

Now in Prolog, I translated it like this:

rotateGrid([T0,T1,T2,T3,T4,T5,T6,T7,T8,T9,T10,T11,T12,T13,T14,T15],
       [T0,T4,T8,T12,T1,T5,T9,T13,T2,T6,T10,T14,T3,T7,T11,T15]).

Can we do better?

Answer 1

We can use findall/3 for list comprehensions (Cf. the SWI-Prolog Documentation). E.g.,

?- findall(X, between(1,10,X), Xs).
Xs = [1,2,3,4,5,6,7,8,9,10]

Xs is a list holding all values that can unify with X when X is a number between 1 and 10. This is roughly equivalent to the Haskell expression let Xs = [x | x <- [1..10]](1). You can read a findall/3 statement thus: "find all values of [First Argument] such that [Conditions in Second Argument] hold, and put those values in the list, [Third Argument]".

I've used findall/3 to write a predicate rotate_grid(+Grid, ?RotatedGrid). Here is a list of the approximate Haskell-Prolog equivalences I used in the predicate; each line shows the relation between the value that the Haskell expression will evaluate to and the Prolog variable with the same value:

• a <- [0..3] = A in between(0, 3, A)
• b <- [0..3] = B in between(0, 3, B)
• (a + 4 * d) = X in X is A + 4 * D
• <Grid> !! <Index> = Element in nth0(Index, Grid, Element)

Then we simply need to find all the values of Element:

rotate_grid(Grid, RotatedGrid) :-
    findall( Element,

            ( between(0,3,A),
              between(0,3,B),
              Index is A + 4 * B,
              nth0(Index, Grid, Element) ),

             RotatedGrid
           ).

To verify that this produces the right transformation, I down-cased the Prolog code from the question and posed the following query:

?- rotate_grid([t0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12,t13,t14,t15],
       [t0,t4,t8,t12,t1,t5,t9,t13,t2,t6,t10,t14,t3,t7,t11,t15]).
|    true.

---

Footnotes:

(1): between/3 isn't actually the analogue of [m..n], since the latter returns a list of values from m to n where between(M,N,X) will instantiate X with each value between M and N (inclusive) on backtracking. To get a list of numbers in SWI-Prolog, we can use numlist(M,N,Ns). So a stricter analogue for x <- [1.10] would be the conjunction member(X, Ns), numlist(1, 10, Ns).

Answer 2

You want a permutation of a list. The concrete elements are not considered. Therefore, you can generalize your Haskell signature to

rotate :: [x] -> [x]

This is already a very valuable hint for Prolog: the list's elements will not be considered - elements will not even be compared. So a Prolog solution should be able to handle variables directly, like so:

?- rotateGrid(L,R).
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P],
   R = [_A,_E,_I,_M,_B,_F,_J,_N,_C,_G,_K,_O,_D,_H,_L,_P].

And your original definition handles this perfectly.

Your version using list comprehensions suggests itself to be realized via backtracking, certain precautions have to be taken. Using findall/3, as suggested by @aBathologist will rename variables:

?- length(L,16),rotate_grid(L,R).
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P],
   R = [_Q,_R,_S,_T,_U,_V,_W,_X,_Y,_Z,_A1,_B1,_C1,_D1,_E1,_F1].

The built-in predicate bagof/3 addresses this problem. Note that we have to declare all local, existential variables explicitly:

rotate_grid2(Grid, RotatedGrid) :-
   bagof(
     Element,
     A^B^Index^    % declaration of existential variables
       (  between(0,3,A),
          between(0,3,B),
          Index is A + 4 * B,
          nth0(Index, Grid, Element)
       ),
     RotatedGrid).

For lists that are shorter than 16 elements, the Haskell version produces a clean error, but here we get pretty random results:

?- L=[1,2,3,4],rotate_grid(L,R).
   L = [1,2,3,4], R = [1,2,3,4].
?- L=[1,2,3,4,5],rotate_grid(L,R).
   L = [1,2,3,4,5], R = [1,5,2,3,4].

This is due to the unclear separation between the part that enumerates and "generates" a concrete element. The cleanest way is to add length(Grid, 16) prior to the goal bagof/3.

List comprehensions in Prolog

Currently, only B-Prolog offers a form of list comprehensions:

R@=[E: A in 0..3,B in 0..3,[E,I],(I is A+4*B,nth0(I,L,E))].

However, it does not address the second problem:

| ?- L = [1,2,3], R@=[E: A in 0..3,B in 0..3,[E,I],(I is A+4*B,nth0(I,L,E))].
L = [1,2,3]
R = [1,2,3]
yes