Improvement on this function

[Jon Fairbairn]

On 2003-09-17 at 10:31EDT Gordon James Miller wrote:

Something I think is more café than language:

> Hello all.
> 
> I'd be interested in getting some feedback on how to do this linear
> interpolation function a little more cleanly.  The normal way that this
> is taught is to find the set of indices in the x list that bracket the
> input value, then use the slope between these points to calculate the y
> value for the input value.
> 
> I had a version working at one point using !! to access particular
> elements but I wasn't sure which one was the better solution.

!! can be expensive.

> linterp :: [Double] -> [Double] -> Double -> Double
> linterp (x1:x2:xs) (y1:y2:ys) x  
>     | x <= x2 || xs == []   = linterpPair x1 x2 y1 y2 x
>     | otherwise = linterp (x2:xs) (y2:ys) x
>     where linterpPair x1 x2 y1 y2 x = x1 + (x - x1) * (y2 - y1) / (x2 -
> x1)

It seems to me that you have too much going on in one
function. It would be better to break it into the part that
finds the point where the interpolation is supposed to
happen and the function that does the interpolation. You
sort-of do this, but don't go far enough for my taste.

You don't say whether the xs are supposed to be in
increasing order.  Also it's not obvious that your version
does the right thing in the case where x < head xs, and
linterpPair doesn't look right to me.

Something like:

linterp :: [Double] -> [Double] -> Double -> Double
linterp xs ys x = linterpPair (neighbours (zip xs ys))
  where linterpPair ((x1,y1),(x2,y2)) = y1 + (x - x1) * (y2 - y1) / (x2 - x1)
        neighbours all@(p@(x1,y1):rest) 
                   | x >= x1
                   = head (dropWhile ((<x). fst . snd) (all `zip` rest))

would be more to my taste, though it would be better to
handle the errors rather than leave them to the runtime
system. I think I would also define the function as 

linterp :: [(Double, Double)] -> Double -> Double

since that seems more natural as the data are connected that
way, and it would eliminate a zip.

-- 
Jón Fairbairn                                 Jon.Fairbairn at cl.cam.ac.uk