STUArray avec le type polymorphes

Question

Je veux mettre en œuvre un algorithme utilisant la ST monade et STUArray s, et je veux qu'il soit en mesure de travailler avec les deux Float et Double données.

Je vais démontrer sur un exemple simple problème: calcul d'un scanl (+) 0 memoized (je sais qu'il peut être résolu sans STUArray, en utilisant comme exemple).

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

Cela échoue avec:

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)) 

Je ne peux pas appliquer le suggéré "solution possible". Parce que j'ai besoin d'ajouter quelque chose comme (forall s. MArray (STUArray s) a (ST s)) au contexte, mais c'est impossible.

Answer 1

Malheureusement, vous ne pouvez actuellement créer un contexte qui nécessite qu'un tableau non-box soit disponible pour un type spécifique. Les contraintes quantifiées ne sont pas autorisées. Cependant, vous pouvez toujours accomplir ce que vous essayez de faire, (avec l'avantage supplémentaire d'avoir des versions de code spécifique de type.) Pour les fonctions plus longues, vous pouvez essayer de diviser des expressions communes afin que le code répété est aussi faible que possible .

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

La version Unboxed générique serait (ce qui ne fonctionne pas) une contrainte de type comme ce qui suit:

accumSTU :: forall a. (IArray UArray a, Num a, 
    forall s. MArray (STUArray s) a (ST s)) => [a] -> Int -> a 

Vous pouvez simplifier la façon suivante:

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

Alors, voici la solution de contournement que je vais avec pour l'instant - la création d'une nouvelle classe de types pour les types pour lesquels (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 

Bien que je ne suis pas tout à fait satisfait, je le préfère sur des règles parce que:

• règles dépendent des optimisations
• règles ne sont pas vraiment censés changer l'algorithme (?). où dans ce cas ils seraient comme des tableaux en boîte ont un comportement très différent concernant la paresse, etc