9

我试图使用 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。

提前致谢。

4

1 回答 1

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仍然适用于链接列表，但请注意，您不是在自己的函数中手动解构列表。如果有一个allPfor 并行列表不是很好吗？会的，但没有。不过，写起来并不难：

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. 模块描述是这样说的：

    不应再在用户代码中显式导入此模块。用户代码应该只导入 Parallel 和，直到矢量化器支持类型类，类型特定的模块。

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

于 2012-12-29T22:48:25.900 回答