Thanks Stephen,

That looks like a nice set of slides.

You're right that what I call the mapFn and the reduceFn could be combined into one function. Logically, though, I think it's more intuitive if they are separated. In addition, it seems important to allow for the possibility of having a function at the terminal point. For example, here's how I would define merge.

merge xs ys =

recursionEngine

(\(xs, ys) -> null xs || null ys)

(\(xs, ys) -> xs ++ ys)

(:)

(\(x:xs, y:ys) -> min x y)

(\(x:xs, y:ys) -> if x <= y then (xs, y:ys) else (x:xs, ys))

(xs, ys)

I'm not sure how to translate that into the genPR formulation.

merge xs ys =

genPR

(\(xs, ys) -> null xs || null ys)

(\(x:xs, y:ys) -> if x <= y then (xs, y:ys) else (x:xs, ys))

(\(x:xs, y:ys) merged -> (min x y) : merged)

Besides the problem with the third argument, the fourth argument is awkward since it must take both heads, take their min, and then add them to the result of the recursive call. I'd prefer to take the heads and the min in a separate step as in the fourth argument to recursionEngine.

-- Russ

On Sat, Nov 6, 2010 at 2:10 AM, Stephen Tetley wrote:

Hello Russ

Richard Kieburtz has a slightly smaller formulation of primitive
recursion on page 13 of these slides - the fold-like argument 'h'
doesn't appear to need a change of type:

http://programatica.cs.pdx.edu/P/Programatica%20Logic1.pdf

genPR :: (a -> Bool) -> (a -> a) -> c -> (a -> c -> c) -> a -> c
genPR p b g h x = if p x then g else h x (genPR p b g h (b x))

-- factorial function:
fact :: Integer -> Integer
fact = genPR (==0) (subtract 1) 1 (*)

Ignoring changes in argument order, the type of your recursionEngine
is one term and one type variable larger:

recursionEngine :: (a -> Bool) -> (a -> c) -> (b -> c -> c) -> (a ->
b) -> (a -> a)-> a -> c

Best wishes

Stephen