haskell - 为什么湿在 DPH 程序中得到 "Can' t vectorise expression GHC.Prim.Int#"错误？

Question

我试图使用 DPH 实现 nqueens 问题，但最终出现 Can't vectorise GHC.Prim.Int# 错误。当我搜索错误时，我发现了一个 GHC 错误，它讨论了用于模式匹配的矢量化文字 (http://haskell.1045720.n5.nabble.com/GHC-5702-Can-t-vectorise-pattern-matching-on -numeric-literals-td5076659.html)。我不确定这是否是同一个错误。
我的代码如下，

{-# LANGUAGE ParallelArrays #-}
{-# OPTIONS_GHC -fvectorise #-}
module NQueensP (nqueens_wrapper) 
where

import qualified Prelude
import Data.Array.Parallel
import Data.Array.Parallel.Prelude
import Data.Array.Parallel.Prelude.Int as I
import qualified Data.Array.Parallel.PArray as P


isSafe i q n  = isSafeHelper i (Prelude.zip (P.toList (toPArrayP q)) [n, n I.- 1..1]) 
            where isSafeHelper i []  = True
                  isSafeHelper i (x:xs) = (i I.== Prelude.fst x) && I.abs(i I.-   
                                  (Prelude.fst x)) I./= I.abs(n I.- (Prelude.snd x)) && 
                                       isSafeHelper i xs

nqueens_wrapper::Int -> PArray (PArray Int)
nqueens_wrapper n = toPArrayP (mapP toPArrayP (nqueens n 0))

nqueens::Int -> Int -> [:[:Int:]:]
nqueens n 1 = [:[:i:] | i <- (enumFromToP 1 n) :]
nqueens n k = [: [:i:] +:+ q | i <- oneton, q <- boards, isSafe i q k:]
           where boards = nqueens n (k I.- 1)
                 oneton = (enumFromToP 1 n) 

如果我做错了什么，请告诉我。我正在使用 GHC 7.4.1。

提前致谢。

Answer 1

是的，这似乎与您提到的错误有关。您得到的错误源于这一行:

nqueens n 1 = [:[:i:] | i <- (enumFromToP 1 n) :]

显然，您不能在 -fvectorise 中使用 n 模式。启用。让我们手动对这一行进行脱糖以删除 n 模式:

nqueens n w | w I.== 1 = [:[:i:] | i <- (enumFromToP 1 n) :]

我们现在已经处理了一个神秘的错误信息。这并不意味着我们已经完成了，因为下一条错误消息似乎同样神秘:

*** Vectorisation error ***
    Tycon not vectorised:  []

isSafe 的问题(我认为)是您使用了许多未使用 -fvectorise 编译的数据类型和变量。 .这意味着你不能只使用链表( Tycon not vectorised: [] )， Prelude.fst , Prelude.snd , 或 Prelude.zip ，除非您在模块中重新定义这些结构。 (很烦人，我什至不能使用 (.) 而不重新定义它。)

我们将不得不重写 isSafe .让我们看一下它的第一行:

isSafe i q n  = isSafeHelper i (Prelude.zip (P.toList (toPArrayP q)) [n, n I.- 1..1]) 

我们不能使用 Prelude.zip , 但我们可以使用 zipP相反，这意味着我们不必转换 q了。但是，我们的递减列表应该使用 DPH 组合器重写。够愚蠢的， enumFromThenToP不存在，所以我们会说 mapP (n I.-) (enumFromToP 0 (n I.- 1))获得 [n, n I.- 1..1] 的并行等效项.所以这条线变成:

isSafe i q n  = isSafeHelper i (zipP q (mapP (n I.-) (enumFromToP 0 (n I.- 1))))

现在为 isSafeHelper :

isSafeHelper i [] = True
isSafeHelper i (x:xs)
    = (i I.== Prelude.fst x)
    && I.abs(i I.- (Prelude.fst x)) I./= I.abs(n I.- (Prelude.snd x))
    && isSafeHelper i xs

因为 Prelude.fst和 Prelude.snd不可用，您可以通过在模式本身中提取元组的这些部分来解决此问题:

isSafeHelper i [] = True
isSafeHelper i ((x1,x2):xs)
    = (i I.== x1)
    && I.abs(i I.- x) I./= I.abs(n I.- x2)
    && isSafeHelper i xs

但是，当然，它仍然无法编译:您的参数将是一个并行列表，而不是 Prelude 风格的链表。为了解决这个问题，我们将使用函数 all 以更实用的方式重写它。 :

isSafeHelper i xs = all (isSafePredicate i) xs

isSafePredicate i (x1,x2)
    = (i I.== x1)
    && I.abs(i I.- x) I./= I.abs(n I.- x2)

all仍然适用于链接列表，但请注意，您不是在自己的函数中手动解构列表。如果有一个 allP 不是很好吗？对于并行列表？会的，但没有。不过，写起来并不难:

allP :: (a -> Bool) -> [: a :] -> Bool
allP p arr = andP (mapP p arr)

把它们放在一起，你可以写 isSafe如下:

isSafe i q n = allP (isSafePredicate i n) (zipP q ntoone) 
  where
    isSafePredicate i n (x1, x2)
        = (i I.== x1)
        && I.abs(i I.- x1) I./= I.abs(n I.- x2)
    ntoone = mapP (n I.-) (enumFromToP 0 (n I.- 1))

nqueens_wrapper看起来还不错。您的代码现在应该可以编译了。

几点注意事项:

我不知道它是否有效(我得到 *** Exception: crossMapP: not implemented ，并且不知道如何修复它)，但它看起来应该。

重写 isSafe反过来是行不通的。如果您尝试使用 Prelude Prelude 中的数字列表，您最终会收到关于 Int# 的投诉。再次。我想这是因为 isSafe被至少一个向量化函数 nqueens 使用.

不包括 Data.Array.Parallel.Prelude . module description这么说:

This module should not be explicitly imported in user code anymore. User code should only import Parallel and, until the vectoriser supports type classes, the type-specific modules.

不要对本地定义发疯。 isSafeHelper缺少它的n你的版本中的论点。