"Не удалось вывести (MArray (STUArray s) Int (ST s)) из context ()" при применении runST

Question

Я в процессе изучения 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

Я надеюсь, что после почти двух часов работы с аннотациями шрифтов кто-нибудь может указать мне правильное направление. Что на земле идет не так?

Спасибо за ваше время.

Answer 1

Я разместил тот же вопрос в списке рассылки haskell и получил ответ:

Это работает, если я [использую строгий] Control.Monad.ST вместо Control.Monad.ST.Lazy,

Проблема в том, что MArray случаи объявлены для строгого ST монады; похоже, что для ленивых нет соответствующих случаев ST монада.
- Дейв Менендес ( http://www.eyrie.org/~zednenem/)

Не думал об этом. Но имеет смысл не определять эти экземпляры, так как для неупакованных значений их вычисление не может быть отложено.

Питер Гэмми отметил, что можно применить функцию strictToLazyST из Control.Monad.ST.Lazy модуль для использования распакованных изменяемых массивов в потоке отложенного состояния. Имейте в виду, что массив по-прежнему строг в своем содержании.

http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad-ST-Lazy.html