STUArray with polymorphic type

Question

我想实现一个算法，使用ST monad和STUArray s，我希望它能够同时使用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))的内容，但这不可能是不可能的。

Answer 1

不幸的是，您目前无法创建上下文，该上下文要求对于特定类型可以使用取消装箱的数组。量化约束是不允许的。然而，你仍然可以完成你想要做的事情（具有类型特定的代码版本的附加优点）。对于更长的函数，你可以尝试分离出通用表达式，以便重复代码尽可能小。

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

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 

虽然我并不完全满意，我喜欢它的规则，因为：

• 规则取决于优化
• 规则是不是真的应该改变算法（？）。在这种情况下，它们将作为盒装阵列在懒惰等方面具有非常不同的行为。