5

我使用 ST-Monad 和未装箱的 STArrays (STUArray) 构建了一个用于查找矩阵行列式的函数。矩阵的类型如下：

newtype Matrix e = Matrix (Array Int (UArray Int e))

也就是说，一个不可变数组，其中包含包含元素的不可变未装箱数组。这将要求我将 Predicate 添加IArray UArray e到处理 的函数中Matrix，而这又需要FlexibleContexts. 好的，完成。

用于计算行列式的函数具有以下签名：

detST :: (IArray UArray e, MArray (STUArray s) e (ST s),
          Num e, Eq e, Division e)
   => Array Int (UArray Int e) -> ST s e

我还需要添加谓词MArray (STUArray s) e (ST s)，因为在内部数组被转换为可变数组（外部装箱，内部未装箱）。

这个函数可以这样使用：

main = do
    let m@(Matrix x) = matrix [ [1,-2,3,234]
                              , [5,2,3,-3]
                              , [7,18,3,40]
                              , [2,9,71,0] ]
        d = runST (detST x) :: Int -- needed for type check, ambiguous otherwise

print d

工作正常。但是看看它有多丑！当然，我不想放弃 of 的内部结构Matrix（至少不会超出附加到我的函数的谓词已经让我这样做）。我想定义以下函数：

det :: Matrix e -> e

而我不能。

我试过没有正确的签名：

det (Matrix arr) = runST (detST arr)

失败。公平地说，我会让我的大脑工作：detST需要IArray UArray e, MArray (STUArray s) e (ST s), Num e, Eq e, Division e，所以需要，det不是吗？

det :: (IArray UArray e, MArray (STUArray s) e (ST s),
          Num e, Eq e, Division e) => Matrix e -> e

失败。但我不明白怎么做。GHC ( 7.4.2 ) 给我的信息是：

Could not deduce (MArray (STUArray s) t (ST s))
  arising from a use of `detST'

但是那个确切的术语在谓词中！

GHC 建议：

add (MArray (STUArray s) t (ST s)) to the context of
  a type expected by the context: ST s t
  or the inferred type of
     det :: (Eq t, Num t, IArray UArray t, Division t) => Matrix t -> t
or add an instance declaration for (MArray (STUArray s) t (ST s))

好的。至于我的理解，我已经做了第一件事。也确实存在一个实例(MArray ...)（否则，我怎么能在 main 中成功使用它？！）。

我不确定这里有什么问题。我相信它与 in 中的“隐藏”ST 状态有关s，并且 s与indetST不同，但我不知道如何为此编写类型。ssdet

什么是正确的定义det- 为什么？

没有det编译的程序只使用FlexibleContexts，没有警告-Wall。完整的源代码可以在这里找到。

4

1 回答 1

4

我设法使用 Keegan McAllister在本文中描述的技巧使其工作：

{-# LANGUAGE FlexibleContexts, ScopedTypeVariables, RankNTypes, GADTs #-}

data Evidence s e where
  Evidence :: (MArray (STUArray s) e (ST s)) => Evidence s e

data ElemType e = ElemType (forall s. Evidence s e)

det :: forall e . (IArray UArray e, Num e, Eq e, Division e)
       => ElemType e -> Matrix e -> e
det (ElemType e) mat = runST (f e mat)
  where
    f :: Evidence s e -> Matrix e -> ST s e
    f Evidence (Matrix arr) = detST arr

用法：

main :: IO ()
main = do
    let m = matrix [ [1,-2,3,234]
                   , [5,2,3,-3]
                   , [7,18,3,40]
                   , [2,9,71,0] ]
    print $ det (ElemType Evidence) (m :: Matrix Int)

问题源于缺少更高级别的约束 - runSThas type (forall s. ST s a) -> a，因此您需要像forall s . MArray (STUArray s) e (ST s)GHC 不支持的约束。这个技巧可以让你让类型检查器相信这个约束实际上是成立的。我在上面链接的文章中可以更深入地讨论这个问题。

于 2013-04-05T09:45:01.343 回答