Patterns for "Symmetric" Functions

Question

Try this new stackoverflow thing as suggested :) This is not a very specific haskell, but it is clear in haskell.

Here is a pattern that appears every time and time: the function takes two arguments, which it processes symmetrically. this property often happens. Example:

-- | Merge sorted lists of ranges. merge :: (Ord n) => [(n, n)] -> [(n, n)] -> [(n, n)] merge [] r2 = r2 merge r1 [] = r1 merge r1@((s1, e1) : rest1) r2@((s2, e2) : rest2) | e1 < s2 = (s1, e1) : merge rest1 r2 | e2 < s1 = (s2, e2) : merge r1 rest2 | s1 >= s2 && e1 <= e2 = merge rest1 r2 -- 1 within 2 | s2 >= s1 && e2 <= e1 = merge r1 rest2 -- 2 within 1 | e1 > e2 = merge (merged : rest1) rest2 | otherwise = merge rest1 (merged : rest2) where merged = (min s1 s2, max e1 e2) 

Note that the processing of "r1" and "r2" is symmetric. In fact, there are only 4 cases: combining with a zero value results in a non-empty, not a coincidence, gives the range unchanged, one of which contains the other range, and the overlap creates a combined range and tries to combine it with the rest.

However, each case has a mirror version, so it ends with 8, although mirror 4 can be obtained mechanically. Not only is there twice as much room for errors, due to symmetry errors will not be caught by the typechecker director. Is there a name for this template? Ways to cancel a repeat? I suppose I can try to define it for a list and then write "mappend ab = mconcat [a, b]", but the problem is that it’s more difficult for me to think in a general way (for example, it hurts me to remember which list to include again combined interval). It is much easier to define mappend and then get mconcat from this. Maybe there is a better way to think about a list version to avoid headaches?

What I think I want to do is “focus” on one case, so I can write in terms of “this” and “that”. Not only is it easier to think than two equally privileged “r1” and “r2”, that-> this case should be implicit from this-> this.

Answer 1

The trick is that you are fusing two separate steps. The first step is simply combining the lists. The second is the merging of intervals so that they do not overlap. The factor of two steps and everything is simplified.

 mergeList (x@(s1,_):xs) (y@(s2,_):ys) = case compare s1 s2 of LT -> x : merge xs (y:ys) GT -> y : merge (x:xs) ys EQ -> x : y : merge xs ys mergeList xs ys = xs ++ ys mergeRuns (x@(s1,e1):x'@(s2,e2):xs) | e1 < s2 = x : mergeRuns (x':xs) -- x is less than and nonoverlapping | otherwise = mergeRuns ((s1, max e1 e2) : xs) -- there is overlap mergeRuns x = x merge xs ys = mergeRuns $ mergeList xs ys 

(unverified)

If you add some built-in pragmas, ghc should take care of creating smoother code for you. Otherwise, you could flatten them manually to get a more voluminous, but more efficient implementation. Ours, you could just leave it, because it should be quite effective, as in any case.

Another approach would be to write the function mergeCons :: (n,n) -> [(n,n)] -> [(n,n)] (which is actually just a variation of mergeRuns ), and then replace it with standard minuses in the function mergeList . This would make the argument about investments a little easier. Here is some code demonstrating this solution (again untested):

 mergeCons x@(s1,e1) (x'@(s2,e2):xs) | e1 < s2 = x : (x':xs) -- x is less than and nonoverlapping | otherwise = (s1, max e1 e2) `mergeCons` xs -- there is overlap mergeCons x [] = [x] merge' (x@(s1,_):xs) (y@(s2,_):ys) = case compare s1 s2 of LT -> x `mergeCons` merge xs (y:ys) GT -> y `mergeCons` merge (x:xs) ys EQ -> x `mergeCons` y `mergeCons` merge xs ys merge' xs ys = xs ++ ys 

Answer 2

Not a solution for your specific case, but, as a rule, for a commutative function, you can define an arbitrary order of arguments, and then call the function with inverted arguments if they are in the "wrong" order.