arrays - MArray 和 MVector 的统一接口(interface)

Question

你将如何为可变数组和向量的各种实现创建一个单一接口(interface)，同时保持它的实用性？ IE。和:

性能与直接使用数组/向量(无抽象)相当

最少重复代码

像这样的东西:

-- (s)torage (k)ey (v)alue (m)onad
class (Monad m) => Storage s k v m where 
    empty :: k -> v -> m (s k v)
    alter :: (v -> v) -> k -> s k v -> m ()
    fold  :: (a -> v -> a) -> a -> s k v -> m a

main :: IO ()
main = do
    _a <-    empty 100 False :: IO   (IOUArray Int Bool)
    _b <-    empty 100 42    :: IO   (VUM.MVector RealWorld Int)
    let _c = empty 100 False :: ST s (STUArray   s Int Bool)
    let _d = empty 100 42    :: ST s (VUM.MVector s Int)
    return ()

MArray 的实现可以是这样的(似乎有效):

instance (Monad m, MArray s v m, Ix k, Num k) => Storage s k v m where
    empty   k v = A.newArray (0, k - 1) v
    alter f k s = A.readArray s k >>= A.writeArray s k . f
    fold  f a s = foldl' f a <$> A.getElems s

这是 MVectors 的一个损坏的实现:

-- doesn't work
instance (PrimMonad m, MVector s v, Unbox v) => Storage s k v m where
    empty   k v = VUM.replicate k v
    alter f k s = VUM.modify s f k
    fold  f a s = VU.foldl' f a <$> VU.freeze s

问题:

您将如何实现 MVector 的实例或重构此代码以使其能够对数组和向量进行抽象？

导入和扩展:

{-# LANGUAGE FlexibleContexts, FlexibleInstances, MultiParamTypeClasses,
             RankNTypes #-}
module UnifiedArray where

import           Control.Monad.Primitive     (PrimMonad, PrimState)
import           Control.Monad.ST            (RealWorld, ST, runST)
import           Data.Array.IO               (IOUArray)
import           Data.Array.MArray           (Ix, MArray)
import qualified Data.Array.MArray           as A
import           Data.Array.ST               (STUArray)
import           Data.Foldable               (foldl')
import           Data.Vector.Generic.Mutable (MVector)
import qualified Data.Vector.Unboxed         as VU
import           Data.Vector.Unboxed.Mutable (Unbox)
import qualified Data.Vector.Unboxed.Mutable as VUM

可运行源代码:
https://gist.github.com/oshyshko/6fae4f859b8f8434af6d3f1eb3cad98e

Answer 1

vector类型不是索引类型的参数，因此您不能将它们硬塞到与 array 完全相同的界面中。是的。
但首先是一个更普遍的问题:

instance constraints => ClassName p q r

形式的实例只有一件事才真正有意义:定义一个类同义词，即一个与其父类(super class)基本相同的类†。
在所有其他情况下，实例应至少提及一个具体的类型构造函数。在您的情况下，这可能应该分别是具体的数组和向量类型:

instance (m ~ IO, MArray IOArray e m, Ix k, Num k) => Storage IOArray k e m where
  ...
instance (m ~ IO, MArray IOUArray e m, Ix k, Num k) => Storage IOUArray k e m where
  ...
instance (m ~ ST, MArray STArray e m, Ix k, Num k) => Storage STArray k e m where
  ...

是的，这意味着一些代码重复，但它基本上只是微不足道的“链接定义”。
现在，为了使其与向量兼容，您需要避免使用 s采用索引类型参数。这是可能的，因为 array类型总是将索引作为第一个参数，即您可以使用 currying 将额外的变量硬烘焙到实例声明中。然后，您可以以关联类型族的形式再次检索该信息:

{-# LANGUAGE FlexibleInstances, FlexibleContexts, MultiParamTypeClasses, TypeFamilies #-}

module Asd where

import           Control.Monad.Primitive     (PrimMonad)
import           Data.Array.IO               (IOUArray)
import           Data.Array.MArray           (MArray)
import qualified Data.Array.MArray           as A
import           Data.Foldable               (foldl')
import           Data.Kind                   (Type)
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic.Mutable as G
import qualified Data.Vector.Mutable         as M

class (Monad m) => Storage s v m where
    type IndexingKey s :: Type
    empty :: IndexingKey s -> v -> m (s v)
    alter :: (v -> v) -> IndexingKey s -> s v -> m ()
    fold  :: (a -> v -> a) -> a -> s v -> m a

instance (m ~ IO, MArray IOUArray v m, A.Ix k, Num k)
                  => Storage (IOUArray k) v m where
    type IndexingKey (IOUArray k) = k
    empty   k v = A.newArray (0, k - 1) v
    alter f k s = A.readArray s k >>= A.writeArray s k . f
    fold  f a s = foldl' f a <$> A.getElems s

instance (PrimMonad m, s~M.PrimState m, G.MVector M.MVector v)
             => Storage (M.MVector s) v m where
    type IndexingKey (V.MVector s) = Int
    empty   k v = M.replicate k v
    alter f k s = M.modify s f k
    fold  f a s = V.foldl' f a <$> V.freeze s

†顺便说一句，这也可以通过

{-# LANGUAGE ConstraintKinds #-}
    
type ClassName p q r = constraints