Geek asks and answers

Unable to find the correct signature for a function using STUArray (nor GHC)

I built a function to search for a matrix determinant using ST-Monad and unboxed STArrays (STUArray). The type for the matrix is ​​as follows:

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

that is, an immutable array containing immutable unpacked arrays containing elements. This will require me to add the Predicate IArray UArray eto the functions related to Matrix, which in turn requires FlexibleContexts. Well done.

The function used to calculate the determinant has the following signature:

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

I also need to add Predicate MArray (STUArray s) e (ST s), since internally arrays are converted to mutable arrays (outer box, inner unboxed).

This function can be used as follows:

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, s in det, , .

det - ?!

det FlexibleContexts, -Wall. .

+5
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. , . I, .

+4

More articles:


All Articles