Sparse vector addition

SparseZip.hs

-- Assumption: indices are sorted in ascending order.

type Sparse a = [(Int,a)]

zipWithS :: (Num a) => (a -> a -> a) -> Sparse a -> Sparse a -> Sparse a
zipWithS f as0 bs0 = filter ((/=0) . snd) $ go as0 bs0
  where go ias@(ia@(i,a):as) jbs@(jb@(j,b):bs) =
            case compare i j of
              LT -> ia : go as jbs
              EQ -> (i,f a b) : go as bs
              GT -> jb : go ias bs
        go as [] = as
        go _  bs = bs

-- *Main> zipWithV (+) [(0,2.2),(3,3),(4,3.3)] [(1,1.1),(3,-3),(4,3.6),(5,9)]
-- [(0,2.2),(1,1.1),(4,6.9),(5,9.0)]