haskell - Merge two association lists with running accumulator -

haskell - Merge two association lists with running accumulator -

basically, describe union/merge of [(,)] combined running accummulator on snd of pair... there elegant way implement this?

(please reference code in context of answering question. if want review code, great too, please on other site: http://codereview.stackexchange.com/questions/54993/merging-time-series)

a time series,

data model variant :: [(day, a)] -> model deriving (show)

... type a in [(day, a)] represents "total balance" e.g. bank account.

some illustration data,

day1 = fromgregorian 1987 10 17 day2 = fromgregorian 1987 10 18 day3 = fromgregorian 1987 10 19 day4 = fromgregorian 1987 10 20 day5 = fromgregorian 1987 10 21 day6 = fromgregorian 1987 10 22 m1 = variant [(day1, 1), (day3, 3), (day5, 5)] :: model integer m2 = variant [(day1, 1), (day2, 2), (day4, 4), (day6, 6)] :: model integer

now, merge 2 time series such "total balance" additive,

(&+) :: num => model -> model -> model (variant a) &+ (variant b) = variant $ reverse $ fst $ go b ([],0) go [] [] (xs, c) = (xs, c) go ((da,va):as) [] (xs, c) = go [] (((da,va+c):xs), va+c) go [] ((db,vb):bs) (xs, c) = go [] bs (((db,vb+c):xs), vb+c) go a@((da,va):as) b@((db,vb):bs) (xs, c) | da > db = go bs (((db,vb+c):xs), vb+c) | da < db = go b (((da,va+c):xs), va+c) | da == db = go bs (((da,va+vb+c):xs), va+vb+c)

so,

what = m1 &+ m2 variant [(1987-10-17,2),(1987-10-18,4),(1987-10-19,7),(1987-10-20,11),(1987-10-21,16),(1987-10-22,22)]

the moment saw reverse felt there might trouble. here's version lazier , works on infinite values. depend upon each of inputs beingness sorted day, however. first seek merge 2 streams

merge :: num => model -> model -> model merge (variant xs) (variant ys) = variant (go xs ys) go [] ys = ys go xs [] = xs go xx@((dx, vx):xs) yy@((dy, vy):ys) | dx < dy = (dx, vx) : go xs yy | dx > dy = (dy, vy) : go xx ys | otherwise = (dx, vx + vy) : go xs ys

it's core of had, much simpler. typically, if can create computation lazy in haskell it's worth effort may more efficient. after point, we'll accumulate

accum :: num => model -> model accum (variant xs) = variant (go xs 0) go [] _ = [] go ((d, v):xs) c = allow c' = v + c in (d, c') : go xs c'

and combining these 2 desired result

-- (&+) :: num => model -> model -> model -- &+ b = accum (merge b)

though, might improve leave merge , accum exposed api since can combined in many ways other (&+).

it may worth noting obvious way write accum function right fold

accum' :: num => model -> model accum' (variant xs) = variant (snd $ foldr go (0, []) xs) go (d, v) (c, res) = allow c' = v + c in (c', (d, c'):res)

doesn't work because accumulates parameter rear of list. trying left fold works have reverse list—a double sin against laziness.

accum'' :: num => model -> model accum'' (variant xs) = variant (reverse $ snd $ foldl go (0, []) xs) go (d, v) (c, res) = allow c' = v + c in (c', (d, c'):res)

which gives hint happening in original version. can write right fold, however, have little tricky in order pass accumulator in right direction

accum' :: num => model -> model accum' (variant xs) = variant (foldr go (const []) xs 0) go (d, v) rest c = allow c' = v + c in (d, c') : rest c'

note here result of foldr go (const []) xs value of type a -> [a].

haskell