unboxing, (sparse) matrices, and haskell vector library

Question

I would like to manipulate matrices (full or sparse) efficiently with haskell's vector library.

Here is a matrix type

import qualified Data.Vector.Unboxed as U
import qualified Data.Vector as V

data Link a = Full (V.Vector (U.Vector a))
    | Sparse (V.Vector (U.Vector (Int,a)))

type Vector a = U.Vector a

As you can see, the matrix is a vector of unboxed vectors. Now, I would like to do a dot product between a vector and a matrix. It is fairly simple to do by combining a sum, zip and map.

But if I do that, because I'm mapping through the rows of the matrix, the result is a boxed vector, even though it could be unboxed.

propagateS output (Field src) (Full weights) = V.map (sum out) weights
    where out     = U.map output src
          sum s w = U.sum $ zipWithFull (*) w s

propagateS output (Field src) (Sparse weights) = V.map (sum out) weights
    where out     = U.map output src
          sum s w = U.sum $ zipWithSparse (*) w s

zipWithFull = U.zipWith

zipWithSparse f x y = U.map f' x
    where f' (i,v) = f v (y U.! i)

How can I get an unboxed vector as a result efficiently ?

Subterrane

Answer 1

I don't know what your Field type is, so I don't quite understand the second snippet.

But if you represent your matrix as a boxed vector, your intermediate results will be boxed vectors. If you want to have an unboxed result, you need to convert types explicitly with U.fromList . V.toList. This an example for your dense matrix type (I omitted the sparse case for brevity):

import qualified Data.Vector.Unboxed as U
import qualified Data.Vector as V

-- assuming row-major order
data Matrix a = Full (V.Vector (U.Vector a))

type Vector a = U.Vector a

-- matrix to vector dot product
dot :: (U.Unbox a, Num a) => (Matrix a) -> (Vector a) -> (Vector a)
(Full rows) `dot` x =
  let mx = V.map (vdot x) rows
  in U.fromList . V.toList $ mx  -- unboxing, O(n)

-- vector to vector dot product
vdot :: (U.Unbox a, Num a) => Vector a -> Vector a -> a
vdot x y = U.sum $ U.zipWith (*) x y

instance (Show a, U.Unbox a) => Show (Matrix a) where
  show (Full rows) = show $ V.toList $ V.map U.toList rows

showV = show . U.toList

main =
  let m = Full $ V.fromList $ map U.fromList ([[1,2],[3,4]] :: [[Int]])
      x = U.fromList ([5,6] :: [Int])
      mx = m `dot` x
  in putStrLn $ (show m) ++ " × " ++ (showV x) ++ " = " ++ (showV mx)

Output:

 [[1,2],[3,4]] × [5,6] = [17,39]

I am not sure about performance of this approach. Probably it is much better to store the whole matrix as a single unboxed vector and access elements by index according to storage model. This way you don't need boxed vectors.

Take a look also at new repa library and its index operation.

Eaton