STUArray mit polymorphen Typ

Question

Ich möchte einen Algorithmus mit dem ST Monade und STUArray s implementieren, und ich will es in der Lage sein, mit beiden Float und Double Daten zu arbeiten.

Ich demonstriere auf ein einfacheres Beispiel Problem: Berechnung eines Memo scanl (+) 0 (ich weiß, dass es ohne STUArray gelöst werden kann, nur als Beispiel). Diese

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

nicht mit:

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

Ich kann die vorgeschlagene "Mögliche fix" nicht anwendbar. Weil ich etwas wie (forall s. MArray (STUArray s) a (ST s)) zum Kontext hinzufügen muss, aber afaik, das ist unmöglich.

Answer 1

Leider können Sie nicht einen Kontext verursachen, der erfordert, dass ein ungeboxtes Array für einen bestimmten Typ verfügbar ist. Quantifizierte Constraints sind nicht erlaubt. Sie können jedoch immer noch erreichen, was Sie versuchen zu tun (mit dem zusätzlichen Vorteil typspezifischer Codeversionen.) Bei längeren Funktionen könnten Sie versuchen, gängige Ausdrücke aufzuteilen, damit der wiederholte Code so klein wie möglich ist .

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

Der Generic Unboxed Version würde (was nicht funktioniert), um eine Typeinschränkung wie die haben folgende:

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

Sie vereinfachen könnte wie folgt aussehen: So, hier

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

ist der Umgehung Ich gehe jetzt mit - Erstellen einer neuen Klasse für Typen, für die (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 

Während ich damit nicht ganz zufrieden bin, ziehe ich es auf Regeln, weil:

• Regeln hängen von Optimierungen
• Regeln nicht wirklich angeblich um den Algorithmus zu ändern (?). In diesem Fall würden sie als Box-Arrays ein sehr unterschiedliches Verhalten hinsichtlich Faulheit usw. haben.