Hylomorphisms (was: [Haskell-cafe] excercise - a completely lazy sorting algorithm)

On 7/12/09, Heinrich Apfelmus wrote:

Raynor Vliegendhart wrote:

...

On 7/9/09, Heinrich Apfelmus wrote:

...

Of course, some part of algorithm has to be recursive, but this can be outsourced to a general recursion scheme, like the hylomorphism

hylo :: Functor f => (a -> f a) -> (f b -> b) -> (a -> b) hylo f g = g . fmap (hylo f g) . f

Is that definition of hylo actually usable? A few on IRC tried to use that definition for a few examples, but the examples failed to terminate or blew up the stack.

The implementation of quicksort with hylo works fine for me, given medium sized inputs like for example quicksort (reverse [1..1000]) .

What were the examples you tried?

One of the examples I tried was: hylo (unfoldr (\a -> Just (a,a))) head $ 42 This expression fails to determinate. Here are two examples copumpkin tried on IRC: <copumpkin> > let hylo f g = g . fmap (hylo f g) . f in hylo (flip replicate 2) length 5 <lambdabot> 5 <copumpkin> > let hylo f g = g . fmap (hylo f g) . f in hylo (flip replicate 2) sum 5 <lambdabot> * Exception: stack overflow