5

ST-Monad とボックス化されていない STArray (STUArray) を使用して、行列の行列式を見つける関数を作成しました。マトリックスの型は次のとおりです。

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

つまり、要素を含む不変のボックス化されていない配列を含む不変の配列です。IArray UArray eこれには、を扱う関数に Predicate を追加する必要があり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)内部で配列が可変配列 (外側はボックス化され、内側はボックス化されていない) に変換されるため、Predicate も追加する必要があります。

この関数は次のように使用できます。

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 edet

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 ...)(そうでなければ、どうすればそれをメインでうまく使用できたでしょうか?!)。

ここで何が悪いのかわかりません。の「隠された」ST状態と関係sがあり、 のはindetST以外sのものであると思いますが、これの型を書く方法がわかりません。sdet

の適切な定義は何ですか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 ) がないことに起因するため、 GHC ではサポートされていない(forall s. ST s a) -> aのような制約が必要です。forall s . MArray (STUArray s) e (ST s)このトリックにより、制約が実際に保持されていることを型チェッカーに納得させることができます。この問題の詳細については、上記のリンク先の記事を参照してください。

于 2013-04-05T09:45:01.343 に答える