7

我想使用STmonad 和STUArrays 实现一个算法，并且我希望它能够同时处理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))在上下文中添加类似的东西，但是这是不可能的..

4

2 回答 2

4

所以这是我现在要使用的解决方法 - 为以下类型创建一个新的类型类(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

虽然我对此并不完全满意，但我更喜欢规则，因为：

  • 规则取决于优化
  • 规则并不真的应该改变算法（？）。在这种情况下，它们将作为盒装数组在惰性等方面具有非常不同的行为。
于 2010-02-11T12:12:01.067 回答
4

不幸的是，您目前无法创建要求未装箱数组可用于特定类型的上下文。不允许使用量化约束。但是，您仍然可以完成您正在尝试做的事情，（具有特定于类型的代码版本的额外优势。）对于更长的函数，您可以尝试拆分常用表达式，以便重复代码尽可能小.

{-# 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 #-}
于 2010-02-08T19:59:11.783 回答