Unified interface to MArray and MVector

Question

How would you make a single interface to various implementations of mutable arrays and vectors, while keeping it pragmatic? I.e. with:

performance comparable to direct use of arrays/vectors (without abstraction)
minimum code duplication

Something like this:

-- (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 ()

The implementation for MArray can be something like this (seems working):

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

Here's a broken implementation for 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

Question:

how would you implement an instance for MVector or refactor this code to make it possible to have an abstraction for both, arrays and vectors?

Imports and extensions:

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

Runnable source code: https://gist.github.com/oshyshko/6fae4f859b8f8434af6d3f1eb3cad98e

user_745903 · Answer

The vector types aren't parametric on the index type, so you can't shoehorn them into quite the same interface as the array ones which are.

But first a more general issue: instances of the form

instance constraints => ClassName p q r

only really make sense for one thing: to define a class synonym, i.e. a class that is basically the same as its superclasses^†.

In all other situations, the instance should mention at least one concrete type constructor. In your case that should probably be the concrete array and vector types, respectively:

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
  ...

Yes, this means some code duplication, but it'll be basically just trivial “linking definitions”.

Now, to make it compatible with vectors, you need to avoid having s take an index-type parameter. That's possible because the array types always take the index as the first argument, i.e. you can use currying to hard-bake an extra variable into the instance declarations. Then you can retrieve that information again with in form of an associated type family:

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

^†This can, incidentally, also be done with

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

Unified interface to MArray and MVector

1 Answers