[Haskell-cafe] Wildly off-topic: de Boor's algorithm

[Andrew Coppin]

Given a suitable definition for Vector2 (i.e., a 2D vector with the 
appropriate classes), it is delightfully trivial to implement de 
Casteljau's algorithm:

de_Casteljau :: Scalar -> [Vector2] -> [[Vector2]]
de_Casteljau t [p] = [[p]]
de_Casteljau t ps = ps : de_Casteljau t (zipWith (line t) ps (tail ps))

line :: Scalar -> Vector2 -> Vector2 -> Vector2
line t a b = (1-t) *| a + t *| b

Now if you want to compute a given point along a Bezier spline, you can do

bezier :: Scalar -> [Vector2] -> Vector2
bezier t ps = head $ last $ de_Casteljau t ps

You can chop one in half with

split :: Scalar -> [Vector2] -> ([Vector2], [Vector2])
split t ps =
  let pss = de_Casteljau t ps
  in (map head pss, map last pss)

And any other beautiful incantations.


Now, de Boor's algorithm is a generalisation of de Casteljau's 
algorithm. It draws B-splines instead of Bezier-splines (since B-splines 
generalise Bezier-splines). But I think I may have ACTUALLY MELTED MY 
BRAIN attempting to comprehend it. Can anybody supply a straightforward 
Haskell implementation?