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.

This wiki page 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/
_____________________________________________