[Haskell-beginners] Decomposing recursion

[Russ Abbott]

As someone who comes into contact with Haskell only once a year when I teach
an introductory Haskell course, I'm not familiar with whether the following
is of any general interest.

It struck me that one can decompose recursive functions into their pieces
which can then be plugged into a recursion engine. Define a recursion engine
as follows.

recursionEngine termCond termFn reduceFn mapFn wayAheadFn =
    recursiveFn
    *where *recursiveFn y
            | termCond y = termFn y
            | *otherwise  *= reduceFn (mapFn y) (recursiveFn (wayAheadFn y))

Then one can define, for example, factorial as follows.

factorial =
  recursionEngine
    (==0)     -- *termCond*. Stop when we reach 0
    (\_ -> 1) -- *termFn*. At 0, return 1.
    (*)       -- *reduceFn*. After the recursive call multiply n * factorial
(n-1).
    id        -- *mapFn*. This is what's saved for the reduce function.
    (+ (-1))  -- *wayAheadFn*.  The recursive call is made on n-1.

What I like about this is that it abstracts out the recursive process and
allows one to plug functions into it to achieve what one wants.  This is
similar in spirit to map, foldr, and similar higher order functions.

I'm writing because I like this and wanted to share it. Also, the standard
higher order functions are, or course, widely used. My question is whether
this has been pushed further to generate widely used libraries of other
higher order functions and if so whether there is a discussion of them
somewhere. In other words, what other algorithmic frameworks have been
abstracted in this way?  (I wouldn't count, for example, sort and zip since
only one function is plugged into their abstract versions; changing that
function doesn't significantly change the *kind *of computation being
done.) Although it's hard to tell, I didn't see anything that looked similar
in either the libraries that come with the standard Haskell download or on
hackage <http://hackage.haskell.org/packages/archive/pkg-list.html>.

This wiki page<http://cs.calstatela.edu/wiki/index.php/Courses/CS_332F/Recursion_engines>is
my presentation of this. Besides a recursionEngine it also includes a
tailRecursionEngine (for tail recursion, naturally) and an
extendedRecursionEngine. The extendedRecursionEngine supports functions that
require multiple recursive calls in the body such as mergesort or quicksort.

Thanks.
*
-- Russ Abbott
_____________________________________________*
*  Professor, Computer Science
  California State University, Los Angeles

  Google voice: 424-235-5752 (424-cell-rja)
  blog: http://russabbott.blogspot.com/
  vita:  http://sites.google.com/site/russabbott/
_____________________________________________*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20101105/c59a53a9/attachment.html