无法为使用STUArray的函数找到适当的签名(GHC也不能)

Question

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

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

也就是说，包含包含元素的不可变未装箱数组的不可变数组。这将要求我将谓词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

很好，很好。但是看看它有多丑！当然，我不想泄露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中成功地使用它？！)

我不知道这里出了什么问题。我相信这与s中的“隐藏”ST状态有关，detST的s是与det中的s不同的一些s，但我不知道如何为此编写一个类型。

det 的正确定义是什么?为什么？！

没有det的程序只使用FlexibleContexts，不使用-Wall警告，可以很好地编译。完整的源代码可以找到作为这里的要旨。

Answer 1

我用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)

这个问题源于缺乏更高级别的约束-- runST有(forall s. ST s a) -> a类型，所以您需要像forall s . MArray (STUArray s) e (ST s)这样的约束，这是GHC不支持的。这个技巧使您能够使类型检查器确信约束实际有效。关于这个问题的更深入的讨论可以在上面链接的文章中找到.