Merging Two Battery Relationship Lists

Question

Basically, I would describe it as a union / merge [(,)] combined with a working accummulator on snd pairs ... Is there an elegant way to implement this?

(Please indicate my code only in the context of answering the question. If you want to view my code, this is also great, but please do it on this other site: https://codereview.stackexchange.com/questions/54993/merging -time-series )

Time series

 data Model a where Variant :: [(Day, a)] -> Model a deriving (Show) 

... where the type a in [(Day, a)] is basically a “common balance," for example. Bank account.

Some example 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 combine the two time series so that the "overall balance" is additive,

 (&+) :: Num a => Model a -> Model a -> Model a (Variant a) &+ (Variant b) = Variant $ reverse $ fst $ go ab ([],0) where go [] [] (xs, c) = (xs, c) go ((da,va):as) [] (xs, c) = go as [] (((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 a bs (((db,vb+c):xs), vb+c) | da < db = go as b (((da,va+c):xs), va+c) | da == db = go as 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)] 

Answer 1

The moment I saw reverse , I felt that there could be problems. Here's a version that is more lazy and runs on infinite values. However, it depends on each of its inputs, as sorted on Day . First we aim for merge two threads

 merge :: Num a => Model a -> Model a -> Model a merge (Variant xs) (Variant ys) = Variant (go xs ys) where 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 

This is basically the essence of what you had, but much easier. Generally, if you can make computing lazy in Haskell, then it's worth the effort, as it can be more efficient. After that we accumulate

 accum :: Num a => Model a -> Model a accum (Variant xs) = Variant (go xs 0) where go [] _ = [] go ((d, v):xs) c = let c' = v + c in (d, c') : go xs c' 

And then, combining these two, we get the desired result

 -- (&+) :: Num a => Model a -> Model a -> Model a -- a &+ b = accum (merge ab) 

Although, it may be better to leave merge and accum as an open API, since they can be combined in different ways, except as soon as (&+) .

---

It may be worth noting that the obvious way to write the accum function as a right fold

 accum' :: Num a => Model a -> Model a accum' (Variant xs) = Variant (snd $ foldr go (0, []) xs) where go (d, v) (c, res) = let c' = v + c in (c', (d, c'):res) 

doesn't work because it accumulates a parameter from the back of the list. The left addition attempt works, but we have to reverse the list - a double sin against laziness.

 accum'' :: Num a => Model a -> Model a accum'' (Variant xs) = Variant (reverse $ snd $ foldl go (0, []) xs) where go (d, v) (c, res) = let c' = v + c in (c', (d, c'):res) 

which gives a hint as to what happened in the original version. However, we can write it as a right fold, but we need to be a little complicated to transfer the battery in the right direction

 accum' :: Num a => Model a -> Model a accum' (Variant xs) = Variant (foldr go (const []) xs 0) where go (d, v) rest c = let c' = v + c in (d, c') : rest c' 

Note that the result of foldr go (const []) xs is a value of type a -> [a] .

Answer 2

The list of associations here is actually a "red herring." This is really a more general question on how to perform a merge using a function to combine terms with equal keys. The version of the list of unions is the same question, but with a preliminary application of the Schwartz transform .

In this case, we need a function with this type:

 mergeCombineWith :: (a -> a -> Ordering) -> (a -> a -> a) -> [a] -> [a] -> [a] 

where the first parameter determines the order, and the second parameter is the union function applied to elements with equal keys. Suppose the input lists are pre-sorted. If we also assume that none of the input lists have duplicate keys, or that we also want to combine duplicates in the same input list, then the solution will be simple. For a traditional type merge function:

 mergeWith :: (a -> a -> Ordering) -> [a] -> [a] -> [a] 

then our desired function is obtained by grouping the results of a traditional merge:

 mergeCombineWith cmp comb xs ys = map combs . groupBy eq $ mergeWith cmp xs ys where combs = foldr1 comb eq xy = isEQ $ cmp xy isEQ EQ = True isEQ _ = False 

More generally, it would be interesting to consider the merger of many lists, not just two. This can be done in a simple way using a fold:

 multiMergeCombineWith :: (a -> a -> Ordering) -> (a -> a -> a) -> [[a]] -> [a] multiMergeCombineWith cmp comb = foldr1 $ mergeCombineWith cmp comb 

But this solution would be ineffective if there were many lists to merge. It is best to prioritize lists and always check the lists first whose first items are the smallest in that order. There are several good priority queue implementations in Hackage.

However, once again, if you have a solution to the multiple-list problem for a traditional merge, you don’t need to reinvent the wheel. Do a traditional merge first, then group and merge as above.

Thanks to Daniel Wagner for pointing me out that versions of two traditional merge functions can be found in the data-ordlist package in Hackage, called mergeBy and mergeAllBy .

EDIT: A new version of the queue has recently been published to Hackage . Discuss it in this reddit thread .