STUArray с полиморфным типом

Question

Я хочу реализовать алгоритм, используя ST монада и STUArrays, и я хочу, чтобы он мог работать с обоими 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 #-}

Версия Generic Unboxed (которая не работает) будет иметь ограничение типа, подобное следующему:

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

Хотя меня это не совсем устраивает, я предпочитаю это по правилам, потому что:

• правила зависят от оптимизации
• правила на самом деле не должны менять алгоритм (?).где в этом случае они, как коробочные массивы, будут иметь совсем другое поведение в отношении лени и т. д.