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

Question

我使用ST-Monad和未装箱的STArrays(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

我还需要添加Predicate,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中成功使用它？!).

我不确定这里有什么问题.我认为它与"隐藏的"ST状态有关s,并且s detST是s除了sin 之外的其他部分det,但我不知道如何为此编写类型.

什么是正确的定义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具有 type (forall s. ST s a) -> a，因此您需要像 之类的约束forall s . MArray (STUArray s) e (ST s)，而 GHC 不支持这些约束。这个技巧可以让你让类型检查器相信约束确实成立。我上面链接的文章中提供了有关此问题的更深入的讨论。