[Haskell-cafe] Generalised merge

[Henning Thielemann]

On Thu, 15 Mar 2007, Paul Johnson wrote:

> 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.

It may help if you temporarily reorganize the TimeFunc to a list of
intervals [(Node,Node)] with Node=(Value, Time), thus duplicating the node
values. (I would also prefer Node=(Time, Value), because Value depends
functionally on Time, that is Nodes represent a function of type Time ->
Value.) This helps accessing the necessary data for linear interpolation.
Then you might first interpolate intervals from list 'a' at the times of
TimeFunc 'b', calling the new TimeFunc 'ba', then vice versa for 'b' and
'a' leads to 'ab', then merge 'a' with 'ab' and 'b' with 'ba'.

I have also coded some interpolation of piecewise linear functions:
  http://darcs.haskell.org/htam/src/Numerics/Interpolation/Linear.hs