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)) <There is no constant that goes here.> (\(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