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

[mokus at deepbondi.net]

mokus at deepbondi.net wrote:
> It took me a while to get the intuition right on those, but here's a quick
> sketch.  Let n = number of control points, m = number of knots, and p =
> degree.  For p = 0 (constant segments), each control point corresponds to
> one span of the knot vector, so n = m - 1.  Each time you move up a
> degree, the basis functions span one more segment of the knot vector.
> Thus, to keep the same number of control points you have to add a knot
> when you add a degree, so n = m - 1 + p.  Equivalently, n - p = m - 1,
> which incidentally makes an appearance in the deBoor function below when
> we zip "spans p us" with "spans 1 ds".  This is just the property that
> ensures that  the length of these lists is equal.

How embarrassing, I managed to get this simple math wrong.  That's what I
get for trying to think in the morning without either my notes or my
coffee, I suppose.  At least, I have that standard excuse to fall back on,
so I'll take advantage of it.  "n = m - 1 + p" should read "n + p = m - 1"
- I added "p" to the wrong side.

It is indeed the property that makes the zip line up, but not by the math
I gave.  Instantiating n and m as the respective "length" expressions
makes the equation:

> length ds + p = length us - 1

With subsequent derivation in light of the fact that the 1st control point
is being ignored (which introduces a "- 1" on the RHS, if I'm not mistaken
again), as mentioned earlier, and the fact that the expression in question
is supposed to return a list one shorter than ds:

> length ds + p - 1 = length us - 1 = length (tail us)
> length ds - 1 = length (tail us) - p
> length (spans 1 ds) = length (spans p (tail us))

(Under the assumption that all the lists involved are long enough for the
tail and drop operations)
And all is (hopefully) right again.

-- James