haskell - 将列表理解翻译为Prolog

我想将Haskell的列表理解功能翻译成Prolog。

列表理解的重点是旋转4 x 4网格:

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

现在在Prolog中，我将其翻译为:

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

我们可以做得更好吗？

最佳答案

我们可以使用findall/3进行列表推导(参见SWI-Prolog Documentation)。例如。，

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

Xs是一个列表，其中包含当X是1到10之间的数字时可以与X统一的所有值。这大致相当于Haskell表达式let Xs = [x | x <- [1..10]](1)。您可以这样阅读findall/3语句:“找到[First Argument]的所有值，使[Secondary in the Second Argument]成立，然后将这些值放在[Third Argument]列表中。”

我已经使用findall/3编写了谓词rotate_grid(+Grid, ?RotatedGrid)。这是我在谓词中使用的近似Haskell-Prolog等价列表。每行显示Haskell表达式将求值的值与具有相同值的Prolog变量之间的关系:

a <- [0..3] = A中的between(0, 3, A)

b <- [0..3] = B中的between(0, 3, B)

(a + 4 * d) = X中的X is A + 4 * D

<Grid> !! <Index> = Element中的nth0(Index, Grid, Element)

然后，我们只需要查找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
           ).

为了验证此转换是否正确，我从问题中简化了Prolog代码，并提出了以下查询:

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

脚注:

(1):between/3实际上不是[m..n]的类似物，因为后者将m到n的值列表返回，其中between(M,N,X)将实例化X，且每个值在M和N之间(包括N和N)(在回溯时)。要获取SWI-Prolog中的数字列表，我们可以使用numlist(M,N,Ns)。因此，更严格的x <- [1.10]类似物将是合取member(X, Ns), numlist(1, 10, Ns)。