1

私はhaskellを学習している最中で、この問題に遭遇しました:

使用するGlasgow Haskell Compiler, Version 6.10.4, for Haskell 98, stage 2 booted by GHC version 6.10.1

ファイルの共通先頭

{-# LANGUAGE FlexibleContexts #-}

module UPSO where

import Control.Monad(forM,forM_)
import Control.Monad.ST.Lazy (ST,runST)
import Data.Array.MArray (MArray, Ix, getBounds, newArray, readArray, writeArray)
import Data.Array.ST (STArray,STUArray)

minmax xs@(x:_) = foldr (\x (l,u) -> (min x l,max x u)) (x,x) xs

modify a i f = do
    x <- readArray a i
    writeArray a i (f x)

increment a i = modify a i (+1)
decrement a i = modify a i (\x -> x - 1)

uniquePermutationsM t 0 = return $! [[]]
uniquePermutationsM t pos = do
    (l,u) <- getBounds t
    perms <- forM [l..u] (\d -> do
         count <- readArray t d -- t[d]
        if count == 0
            then return $! []
            else do
                decrement t d
                pss <- uniquePermutationsM t (pos-1)
                increment t d
                return $! (map (d:) pss)
        )
    return $! (concat perms)

STArray の使用 (動作)

mkArray :: (Int,Int) -> (ST s) (STArray s Int Int)    
mkArray bounds = newArray bounds 0 

uniquePermutationsST ::  [Int] -> ST s [[Int]]
uniquePermutationsST xs = do
    let bounds@(l,u) = (minmax xs) 
    t <- mkArray  bounds
    forM_ xs (increment t)
    pos <- sum `fmap` mapM (readArray t) [l..u]
    uniquePermutationsM t pos

uniquePermutations xs = runST (uniquePermutationsST xs)

STUArray の使用 (機能しません)

しかし、ボックス化されていないアレイに切り替えようとすると、エラー メッセージが表示されます。

mkArray :: (Int,Int) -> (ST s) (STUArray s Int Int)    
mkArray bounds = newArray bounds 0 

uniquePermutationsST ::  [Int] -> ST s [[Int]]
uniquePermutationsST xs = do
    let bounds@(l,u) = (minmax xs) 
    t <- mkArray  bounds
    forM_ xs (increment t)
    pos <- sum `fmap` mapM (readArray t) [l..u]
    uniquePermutationsM t pos

uniquePermutations xs = runST (uniquePermutationsST xs)

エラーメッセージ

Could not deduce (MArray (STUArray s) Int (ST s))
  from the context ()
  arising from a use of 'newArray' at UPSO.hs:35:17-33
Possible fix:
  add (MArray (STUArray s) Int (ST s)) to the context of
    the type signature for 'mkArray'
  or add an instance declaration for (MArray (STUArray s) Int (ST s))
In the expression: newArray bounds 0
In the definition of 'mkArray': mkArray bounds = newArray bounds 0

また:

Could not deduce (MArray (STUArray s) Int (ST s))
  from the context ()
  arising from a use of 'increment' at UPSO.hs:41:14-24

型注釈をいじってからほぼ 2 時間後、誰かが私を正しい方向に向けてくれることを願っています。いったい何が間違っているのでしょうか？

お時間をいただきありがとうございます。

4

1 に答える 1

2

Haskellメーリングリストに同じ質問を投稿したところ、次の回答が得られました。

の代わりに[strict を使用]Control.Monad.STControl.Monad.ST.Lazyすると、これは機能します。

問題はMArray、厳密なSTモナドに対してインスタンスが宣言されていることです。ST遅延モナド に対応するインスタンスはないようです。
-- デイブ・メネンデス ( http://www.eyrie.org/~zednenem/ )

それは考えていませんでした。ただし、ボックス化されていない値の計算を遅らせることはできないため、これらのインスタンスを定義しないのは理にかなっています。

strictToLazySTPeter Gammie さんは、Control.Monad.ST.Lazyモジュールの関数を適用して、ボックス化されていない可変配列を遅延状態のスレッドで使用できることを指摘しました。ただし、配列の内容は依然として厳密であることに注意してください。

http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad-ST-Lazy.html#v%3AstrictToLazyST

于 2009-07-21T23:22:31.873 に答える