STUArray с полиморфным типом

Question

Я хочу реализовать алгоритм, использующий ST монады и STUArray с, и я хочу, чтобы иметь возможность работать с обеими Float и Double данных.

Я продемонстрирую более простой пример проблемы: вычисление memoized 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 это невозможно ..

Answer 1

К сожалению, в настоящее время вы не можете создать контекст, который требует, чтобы массив unboxed был доступен для определенного типа. Определенные ограничения не допускаются. Тем не менее, вы все равно можете выполнить то, что вы пытаетесь сделать (с дополнительным преимуществом иметь версии кода для конкретных типов.) Для более длинных функций вы можете попытаться разделить общие выражения, чтобы повторный код был как можно меньше ,

{-# 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 #-} 

Типовая Unboxed версия (которая не работает) будет иметь ограничение типа, как следующее:

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 #-} 

Answer 2

Так вот обходной путь, который я собираюсь сделать сейчас - создание нового типа для типов, для которых (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 

Хотя я не совсем доволен этим, я предпочитаю его по правилам, потому что:

• правила зависят от оптимизации
• правила на самом деле не предполагается изменить алгоритм (?). где в этом случае они будут иметь так же, как в коробках массивов, очень различное поведение относительно ленивости и т. д.