带有多态类型的STUArray

问题描述

我想用 ST monad和 STUArray s来实现算法，我希望它能够使用 Float 和 Double 数据。

I want to implement an algorithm using the ST monad and STUArrays, and I want it to be able to work with both Float and Double data.

我将演示一个更简单的示例问题：计算一个记忆 scanl（+）0 （我知道它可以在没有 STUArray $ b

I'll demonstrate on a simpler example problem: calculating a memoized scanl (+) 0 (I know it can be solved without STUArray, just using as example).

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

这会失败：



This fails with:

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不可能。

I can't apply the suggested "Possible fix". Because I need to add something like (forall s. MArray (STUArray s) a (ST s)) to the context, but afaik that's impossible..

推荐答案

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



Unforunately, you can't currently create a context that requires that an unboxed array be available for a specific type. Quantified Constraints aren't allowed. However, you can still accomplish what you're trying to do, (with the added advantage of having type-specific code versions.) For Longer functions, you could try to split out common expressions so that the repeated code is as small as 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 #-}

通用Unboxed版本（不起作用）将具有类型约束，如下所示：

The Generic Unboxed version (which doesn't work) would have a type constraint like the following:

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

您可以简化如下：



You could simplify as follows:

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

这篇关于带有多态类型的STUArray的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！