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