Generalizing recursion on integers
I thought I’d post a brief answer to the question I raised in my last post, which was “is there an analogous higher-order function [like foldr] for recursion on numbers?”
As I pointed out, you can define product using foldr, like this:
product = foldr (*) 1
What I wanted is another function, say foldrNum, that would allow me to define factorial using the same idea:
factorial = foldrNum (*) 1
As it turns out, all I need to do is make some slight modifications to the foldr definition, which looks like this:
foldr :: (a -> b -> b) -> b -> [a] -> b foldr op v [] = v foldr op v (x:xs) = op x (foldr op v xs)
I’ll keep foldrNum general enough so that, like foldr, it can return a value of any type (b), but unlike foldr, which can process a list of any type (a), I think it’s essential to the idea of foldrNum that it only operate on a non-negative integer, which is what the recursion is based on. First, I’ll show the definition of foldrNum I came up with. Then I’ll compare it line-by-line with foldr so that we can see exactly what’s the same and what’s different.
Here’s foldrNum:
foldrNum :: (Int -> b -> b) -> b -> Int -> b foldrNum op v 0 = v foldrNum op v (n+1) = op (n+1) (foldrNum op v n)
The similarities are obvious, but I like to make things as obvious as possible. First, the types of each function:
foldr :: (a -> b -> b) -> b -> [a] -> b foldrNum :: (Int -> b -> b) -> b -> Int -> b
Now, the base case:
foldr op v [] = v foldrNum op v 0 = v
Finally, the recursive case:
foldr op v (x:xs) = op x (foldr op v xs) foldrNum op v (n+1) = op (n+1) (foldrNum op v n)
The natural question arising from this is “How do I generalize foldr and foldrNum, since they’re so much alike?” Joshua Ball anticipated that question in his comment on my last post, although I confess I haven’t fully wrapped my head around his solution yet.
I think this is enough for today. So many possible directions to go in. I must content myself with one small piece at a time. 🙂
Dimitre Novatchev said,
June 14, 2007 @ 11:37 am
Hi Evan,
The function you are after is:
foldr op v (take n [1 .. ])
Or you could use the definition of the function
iter
as defined in FXSL.
Which is actually composing a function with itself N times
f.f.f….f initval
Cheers,
Dimitre Novatchev
John Prevost said,
June 14, 2007 @ 1:00 pm
I agree with Dimitre here, as far as “foldr op v (take n [1 .. ])” goes.
In a way, you’re trying too hard here. Remember that Haskell has non-strict evaluation—this means that there’s no real difference between the following:
1) a function that takes an integer and then tail calls itself with the next integer in some pre-determined sequence, and
2) a function that takes a sequence and then tail calls itself on the tail of the sequence, combined with a function that produces a pre-determined sequence.
In both cases, the next number in sequence will only be produced when it is needed—this isn’t an imperative language where returning a list means you will always be allocating and holding that list in memory. Instead, you might think of a function that returns a list as being exactly the same thing as a function that returns a description of the process of how to produce that list.
I hope that was at least a little clearer than it sounds to me right now. 🙂
Daryl said,
August 18, 2007 @ 5:14 pm
hi i enjoyed the read