[Haskell-beginners] General primitive recursion

[Russ Abbott]

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
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20101106/b793fb8d/attachment.html