Dynamic typing over containers of finite domain of basic types

Question

I have a problem with writing a simple function without too much repeating myself, below is a simplified example. The real program I am trying to write is a port of an in-memory database for a BI server from python. In reality there are more different types (around 8) and much more logic, that is mostly expressible as functions operating on polymorphic types, like Vector a, but still some logic must deal with different types of values.

Wrapping each value separatly (using [(Int, WrappedValue)] type) is not an option due to efficiency reasons - in real code I am using unboxed vectors.

type Vector a = [(Int, a)] -- always sorted by fst

data WrappedVector = -- in fact there are 8 of them
      FloatVector (Vector Float)
    | IntVector (Vector Int)
    deriving (Eq, Show)

query :: [WrappedVector] -> [WrappedVector] -- equal length
query vectors = map (filterIndexW commonIndices) vectors
    where
        commonIndices = intersection [mapFstW vector | vector <- vectors]

intersection :: [[Int]] -> [Int]
intersection = head -- dummy impl. (intersection of sorted vectors)

filterIndex :: Eq a => [Int] -> Vector a -> Vector a
filterIndex indices vector = -- sample inefficient implementation
    filter (\(idx, _) -> idx `elem` indices) vector

mapFst :: Vector a -> [Int]
mapFst = map fst

-- idealy I whould stop here, but I must write repeat for all possible types
-- and kinds of wrapped containers and function this:

filterIndexW :: [Int] -> WrappedVector -> WrappedVector
filterIndexW indices vw = case vw of
    FloatVector v -> FloatVector $ filterIndex indices v
    IntVector   v -> IntVector $ filterIndex indices v

mapFstW :: WrappedVector -> [Int]
mapFstW vw = case vw of
    FloatVector v -> map fst v
    IntVector   v -> map fst v

-- sample usage of query
main = putStrLn $ show $ query [FloatVector [(1, 12), (2, -2)],
                                IntVector   [(2, 17), (3, -10)]]

How can I express such code without wrapping and unwrapping like in mapFstW and filterIndexW functions?

Answer 1

If you're willing to work with a few compiler extensions, ExistentialQuantification solves your problem nicely.

{-# LANGUAGE ExistentialQuantification #-}
{-# LANGUAGE StandaloneDeriving #-}
module VectorTest where

type PrimVector a = [(Int, a)]

data Vector = forall a . Show a => Vector (PrimVector a)

deriving instance Show Vector

query :: [Vector] -> [Vector] -- equal length
query vectors = map (filterIndex commonIndices) vectors
    where
        commonIndices = intersection [mapFst vector | vector <- vectors]

intersection :: [[Int]] -> [Int]
intersection = head -- dummy impl. (intersection of sorted vectors)

filterIndex :: [Int] -> Vector -> Vector
filterIndex indices (Vector vector) = -- sample inefficient implementation
    Vector $ filter (\(idx, _) -> idx `elem` indices) vector

mapFst :: Vector -> [Int]
mapFst (Vector l) = map fst l

-- sample usage of query
main = putStrLn $ show $ query [Vector [(1, 12), (2, -2)],
                                Vector [(2, 17), (3, -10)]]

The StandaloneDeriving requirement can be removed if you write a manual Show instance for Vector, e.g.

instance Show Vector where
    show (Vector v) = show v