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:
map f (iterate f x) = iterate f (f x)
zipWith (⊗) as . map (⊗X) = map (⊗X) . zipWith (⊗) as
if⊗
associativesum . map (×X) = (×X) . sum
, a special case offoldr ⊕ e . map (⊗X) = (⊗X) . foldr ⊕ e
if(a ⊕ b) ⊗ X = (a ⊗ X) ⊕ (b ⊗ X)
ande ⊗ 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?
In
= { zipWith (⊗) as . map (⊗X) = map (⊗X) . zipWith (⊗) as
if ⊗ associative }
Did you perhaps mean to write “commutative”?
Hi, let’s see an example. Let
as := [a,b,c]
and let the input be[d,e,f]
.So what I need is indeed associativity. :)
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
Hmmm.. I’m not sure that’s right, dagit. Now that we have derived an inductive definition of
poly
:one can see that
poly
is in fact afoldr
: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 afoldr
(to do so you will need the law in the post aboutiterate
andmap
), and fusesum
into it. Then you get a definition ofpoly
as afoldr
. To be extreme, you can even doand perform a
foldr
-fusion. The derivation will be very similar to that in the post.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.
I didn’t know about SimpleReflect before. Looks like a very useful tool (and I’m curious how it works). Thanks!
I use it through lambdabot (the channel bot for #haskell on freenode). It’s also available as a standalone package on hackage:
http://hackage.haskell.org/package/simple-reflect
You can see most of the source code here:
http://hackage.haskell.org/packages/archive/simple-reflect/0.2/doc/html/src/Debug-SimpleReflect-Expr.html
It uses many of the standard type classes in clever ways to build up expressions and then pretty print them. Simple, but effective.
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)
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!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?
I really liked that second example because you managed to derive Horner’s rule (eg, from exercise 2.38 in SICP, http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html) without much trouble.
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
anditerate
is instead formulated using repeatedmap
,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.
Pingback: Tweets that mention Evaluating Simple Polynomials -- Topsy.com