STUArray с полиморфным типом
Я хочу реализовать алгоритм с помощью ST монада и STUArrays, и я хочу, чтобы это смогло работать с обоими Float и Double данные.
Я продемонстрирую на более простой проблеме в качестве примера: вычисление мемоизованного scanl (+) 0 (Я знаю, что это может быть решено без STUArray, просто с помощью в качестве примера).
{-# LANGUAGE FlexibleContexts, ScopedTypeVariables #-}
import Control.Monad
import Control.Monad.ST
import Data.Array.Unboxed
import Data.Array.ST
accumST :: forall a. (IArray UArray a, Num a) => [a] -> Int -> a
accumST vals = (!) . runSTUArray $ do
arr <- newArray (0, length vals) 0 :: ST s (STUArray s Int a)
forM_ (zip vals [1 .. length vals]) $ \(val, i) ->
readArray arr (i - 1)
>>= writeArray arr i . (+ val)
return arr
Это перестало работать с:
Could not deduce (MArray (STUArray s) a (ST s)) from the context ()
arising from a use of 'newArray'
Possible fix:
add (MArray (STUArray s) a (ST s)) to the context of
an expression type signature
or add an instance declaration for (MArray (STUArray s) a (ST s))
Я не могу применить предложенную "Возможную фиксацию". Поскольку я должен добавить что-то как (forall s. MArray (STUArray s) a (ST s)) к контексту, но afaik это невозможно..
2 ответа
К сожалению, в настоящее время вы не можете создать контекст, который требует, чтобы неупакованный массив был доступен для определенного типа. Количественные ограничения не допускаются. Однако вы все равно можете выполнить то, что пытаетесь сделать (с дополнительным преимуществом наличия версий кода для конкретных типов). Для более длинных функций вы можете попытаться разделить общие выражения, чтобы повторяемый код был как можно меньше .
{-# LANGUAGE FlexibleContexts, ScopedTypeVariables #-}
module AccumST where
import Control.Monad
import Control.Monad.ST
import Data.Array.Unboxed
import Data.Array.ST
import Data.Array.IArray
-- General one valid for all instances of Num.
-- accumST :: forall a. (IArray UArray a, Num a) => [a] -> Int -> a
accumST :: forall a. (IArray UArray a, Num a) => [a] -> Int -> a
accumST vals = (!) . runSTArray $ do
arr <- newArray (0, length vals) 0 :: (Num a) => ST s (STArray s Int a)
forM_ (zip vals [1 .. length vals]) $ \(val, i) ->
readArray arr (i - 1)
>>= writeArray arr i . (+ val)
return arr
accumSTFloat vals = (!) . runSTUArray $ do
arr <- newArray (0, length vals) 0 :: ST s (STUArray s Int Float)
forM_ (zip vals [1 .. length vals]) $ \(val, i) ->
readArray arr (i - 1)
>>= writeArray arr i . (+ val)
return arr
accumSTDouble vals = (!) . runSTUArray $ do
arr <- newArray (0, length vals) 0 :: ST s (STUArray s Int Double)
forM_ (zip vals [1 .. length vals]) $ \(val, i) ->
readArray arr (i - 1)
>>= writeArray arr i . (+ val)
return arr
{-# RULES "accumST/Float" accumST = accumSTFloat #-}
{-# RULES "accumST/Double" accumST = accumSTDouble #-}
Общая версия без упаковки (которая не работает) будет иметь ограничение типа, подобное следующему:
accumSTU :: forall a. (IArray UArray a, Num a,
forall s. MArray (STUArray s) a (ST s)) => [a] -> Int -> a
Вы можете упростить следующим образом:
-- accumST :: forall a. (IArray UArray a, Num a) => [a] -> Int -> a
accumST :: forall a. (IArray UArray a, Num a) => [a] -> Int -> a
accumST vals = (!) . runSTArray $ do
arr <- newArray (0, length vals) 0 :: (Num a) => ST s (STArray s Int a)
accumST_inner vals arr
accumST_inner vals arr = do
forM_ (zip vals [1 .. length vals]) $ \(val, i) ->
readArray arr (i - 1)
>>= writeArray arr i . (+ val)
return arr
accumSTFloat vals = (!) . runSTUArray $ do
arr <- newArray (0, length vals) 0 :: ST s (STUArray s Int Float)
accumST_inner vals arr
accumSTDouble vals = (!) . runSTUArray $ do
arr <- newArray (0, length vals) 0 :: ST s (STUArray s Int Double)
accumST_inner vals arr
{-# RULES "accumST/Float" accumST = accumSTFloat #-}
{-# RULES "accumST/Double" accumST = accumSTDouble #-}
Итак, вот обходной путь, которым я сейчас пользуюсь - создание нового класса типов для типов, для которых (forall s. MArray (STUArray s) a (ST s)) :
class IArray UArray a => Unboxed a where
newSTUArray :: Ix i => (i, i) -> a -> ST s (STUArray s i a)
readSTUArray :: Ix i => STUArray s i a -> i -> ST s a
writeSTUArray :: Ix i => STUArray s i a -> i -> a -> ST s ()
instance Unboxed Float where
newSTUArray = newArray
readSTUArray = readArray
writeSTUArray = writeArray
instance Unboxed Double where
newSTUArray = newArray
readSTUArray = readArray
writeSTUArray = writeArray
Пока я Меня это не совсем устраивает, я предпочитаю это на правилах, потому что:
- правила зависят от оптимизаций
- правила на самом деле не должны изменять алгоритм (?). где в этом случае они, как упакованные массивы, будут иметь совсем другое поведение в отношении лени и т. д.