The most common kind of primitive recursive function I find myself
writing these days is a variation on the theme of merging two sorted lists.
You can see some examples in my Ranged Sets library at
http://ranged-sets.sourceforge.net/. For instance:
-- | Set union for ranged sets. Infix precedence is left 6.
rSetUnion, (-\/-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
-- Implementation note: rSetUnion merges the two lists into a single
-- sorted list and then calls normalise to combine overlapping ranges.
rSetUnion (RSet ls1) (RSet ls2) = RSet $ normalise $ merge ls1 ls2
where
merge ls1 [] = ls1
merge [] ls2 = ls2
merge ls1@(h1:t1) ls2@(h2:t2) =
if h1 < h2
then h1 : merge t1 ls2
else h2 : merge ls1 t2
-- | Set intersection for ranged sets. Infix precedence is left 7.
rSetIntersection, (-/\-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetIntersection (RSet ls1) (RSet ls2) =
RSet $ filter (not . rangeIsEmpty) $ merge ls1 ls2
where
merge ls1@(h1:t1) ls2@(h2:t2) =
rangeIntersection h1 h2
: if rangeUpper h1 < rangeUpper h2
then merge t1 ls2
else merge ls1 t2
merge _ _ = []
Union also has its own merge function.
The worst case I've come across was at work. I can't talk about the
details, but it involved manipulating two functions of time represented
by lists of samples. So I had a type TimeFunc = [(Value, Time)], and
the job was to compare two TimeFuncs with samples at different times.
Step 1 was to interpolate each TimeFunc with the values for the times in
the other TimeFunc, giving a result of type [(Value, Value, Time)] for
the union of all the times in both original TimeFuncs. I wrote a truly
hairy zipTimeFunc function with guards to match each possible case. It
worked, but it must have been 100 lines if you include the comments to
explain each case and demonstrate totality.
So I'm wondering if anyone has a more general pattern. Unfold? Some
variation on a theme of zip? I once tried writing a generalised merge,
but it needed half a dozen functions as arguments to handle all the
various cases. It was kludgier than just rolling a new merge routine
every time. And I don't think it would have handled the TimeFunc case.
Paul.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
