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. 🙂

3 Comments »

  1. 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

  2. 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. 🙂

  3. Daryl said,

    August 18, 2007 @ 5:14 pm

    hi i enjoyed the read

RSS feed for comments on this post · TrackBack URI

Leave a Comment