Evaluating Simple Polynomials

In the end of FLOLAC ’10 I had a chance to show the students, in 25 minutes, what functional program calculation is about. The student have just been exposed to functional programming a week ago in a three-hour course, after which they have written some simple programs handling concrete data but may have problem grasping those more abstract concepts like folds. I have talked to them about maximum segment sum way too many times (in the context of imperative program derivation, though), and it is perhaps too complex to cover in 25 minutes. The steep list problem, on the other hand, can be dealt with in 5 minutes. Thus I need another example.

This is what I eventually came up with: given a list of numbers a₀, a₁, a₂ ... an and a constant X, compute a₀ + a₁X, + a₂X² + ... + anXn. In Haskell it can be specified as a one-liner:

  poly as = sum (zipWith (×) as (iterate (×X) 1))

One problem of this example is that the specification is already good enough: it is a nice linear time algorithm. To save some multiplications, perhaps, we may try to further simplify it.

It is immediate that poly [] = 0. For the non-empty case, we reason:

   poly (a : as)
 =   { definition of poly }
   sum (zipWith (×) (a:as) (iterate (×X) 1))
 =   { definition of iterate }
   sum (zipWith (×) (a:as) (1 : iterate (×X) X))
 =   { definition of zipWith } 
   sum (a : zipWith (×) as (iterate (×X) X))
 =   { definition of sum }
   a + sum (zipWith (×) as (iterate (×X) X))

The expression to the right of a + is unfortunately not poly as — the last argument to iterate is X rather than 1. One possibility is to generalise poly to take another argument. For this problem, however, we can do slightly better:

   a + sum (zipWith (×) as (iterate (×X) X))
 =   { since iterate f (f b) = map f (iterate f b) }
   a + sum (zipWith (×) as (map (×X) (iterate (×X) 1)))
 =   { zipWith (⊗) as . map (⊗X) = map (⊗X) . zipWith (⊗) as 
          if ⊗ associative }
   a + sum (map (×X) (zipWith (×) as (iterate (×X) 1)))
 =   { sum . map (×X) = (×X) . sum }
   a + (sum (zipWith (×) as (iterate (×X) 1))) × X
 =   { definition of poly }
   a + (poly as) × X

We have thus come up with the program

  poly [] = 0
  poly (a : as) = a + (poly as) × X

Besides the definitions of sum, zipWith, iterate, etc, the rules used include:

  1. map f (iterate f x) = iterate f (f x)
  2. zipWith (⊗) as . map (⊗X) = map (⊗X) . zipWith (⊗) as if associative
  3. sum . map (×X) = (×X) . sum, a special case of foldr ⊕ e . map (⊗X) = (⊗X) . foldr ⊕ e if (a ⊕ b) ⊗ X = (a ⊗ X) ⊕ (b ⊗ X) and e ⊗ X = e.

Well, this is not a very convincing example. Ideally I’d like to have a derivation, like the steep list, where we gain some improvement in complexity by calculation.

What is your favourite example for functional program calculation?

13 thoughts on “Evaluating Simple Polynomials”

  1. In
    = { zipWith (⊗) as . map (⊗X) = map (⊗X) . zipWith (⊗) as
    if ⊗ associative }
    Did you perhaps mean to write “commutative”?

    1. Hi, let’s see an example. Let as := [a,b,c] and let the input be [d,e,f].

        zipwith (⊗) [a,b,c] (map (⊗X) [d,e,f])
      = zipwith (⊗) [a,b,c] [d⊗X,e⊗X,f⊗X]
      = [a⊗(d⊗X), b⊗(e⊗X), c⊗(f⊗X)]
      =   { (⊗) associative } 
        [(a⊗d)⊗X, (b⊗e)⊗X, (c⊗f)⊗X]
      = map (⊗X) [a⊗d, b⊗e, c⊗f]
      = map (⊗X) (zipWith (⊗) [a,b,c] [d,e,f])

      So what I need is indeed associativity. :)

  2. Thanks for the reply. I have another question.

    Could you derive this form from your original?

    poly as = foldl (\acc a -> a + acc * X) 0 as

    The reason I ask is because I’m often told that using higher-order recursive functions is better than coding the recursion directly. Here I feel like it’s actually harder to see what’s going on when I express it as a fold than the explicitly recursive version. For example, I had to play with the Expr type and SimpleReflect to convince myself that I wanted foldl instead of foldr.

    Doing a point free transformation we can get the even more obscure:

    poly = foldl ((+) . (X *)) 0

    1. Hmmm.. I’m not sure that’s right, dagit. Now that we have derived an inductive definition of poly:

        poly [] = 0
        poly (a : as) = a + (poly as) × X

      one can see that poly is in fact a foldr:

        poly = foldr (λa b → a + b × X) 0

      which does not seem to be the same function as foldl (λacc a → a + acc × X) 0.

      It is true for many people that definitions in terms of those structured recursion combinators tend to be more abstract and harder to understand. The advantage, on the other hand, is that once a program is expressed this way, we know more about its structure and properties. If a program turns out to be a fold, for example, we know that all laws about folds are applicable to the program.

      The manipulation in the program is in fact an instance of foldr-fusion. You may try to express (λas → zipWith (×) as (iterate (×X) X)) as a foldr (to do so you will need the law in the post about iterate and map), and fuse sum into it. Then you get a definition of poly as a foldr. To be extreme, you can even do

       = poly . id
       =  { id = foldr (:) [] }
         poly . foldr (:) []

      and perform a foldr-fusion. The derivation will be very similar to that in the post.

      1. You’re right. I misinterpreted the output from lambdabot. I was thinking that the coefficient next to (0 * x) was the lowest degree, but due to the nesting of the parens, if I actually multiply things out I see that it has the highest degree. My intuition had been foldr, but I did too many steps in my head and tricked myself :)

        I can even use lambdabot to see this expanded out for some examples:

        > foldl (\acc a -> a + acc * x) 0 [1..4] :: Expr
        4 + (3 + (2 + (1 + 0 * x) * x) * x) * x
        > let { poly [] = 0; poly (a : as) = a + poly as * x } in poly [1..4] :: Expr
        1 + (2 + (3 + (4 + 0 * x) * x) * x) * x
        > foldr (\a acc -> a + acc * x) 0 [1..4] :: Expr
        1 + (2 + (3 + (4 + 0 * x) * x) * x) * x

        I use lower case x here as that is already in scope with type Expr. I see that indeed, poly matches the foldr version. Thanks again! I’ll check out some of your other posts that you point out.

  3. I think I see why I was confused. You’re using x instead of * for multiplication. So the second equation has this precedence:

    poly (a : as) = a + ((poly as) * X)

    1. Sorry for the confusion. In fact it is not the letter x, but ×, a unicode character for multiplication. I’ve made it worse by using a typewriter font in which they look similar, and having capital X as the constant. I should perhaps have added the brackets to avoid confusion!

  4. I think I’m missing something. Doesn’t this program have a type error?

    poly [] = 0
    poly (a : as) = a + poly as × X

    The first equation gives poly 1 parameter on the LHS and the RHS is a value (instead of a function of one or more parameters). The second equation also gives poly one parameter on the LHS, but it then it calls poly with 3 parameters. Am I missing something obvious here?

    1. Thanks for the comment. Yes, it’s all about Horner’s rule!

      In Algebra of Programming Bird and de Moor generalised Horner’s rule:
      1. the part using zipWith and iterate is instead formulated using repeated map,
      2. sum is generalised to a fold,
      3. and the whole thing is generalised to structures other than lists.
      They then proved the rule using fold-fusion. It was in fact the first Horner’s rule I learned about. Here I specialised Horner’s rule back to lists and try to prove it without fold-fusion.

  5. Pingback: Tweets that mention Evaluating Simple Polynomials -- Topsy.com

Leave a Comment

Your email address will not be published. Required fields are marked *