Skip to content

Instantly share code, notes, and snippets.

@bos
Created April 13, 2011 03:27
Show Gist options
  • Save bos/916911 to your computer and use it in GitHub Desktop.
Save bos/916911 to your computer and use it in GitHub Desktop.
Sparse vector addition
-- 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)]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment