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

[Raynor Vliegendhart]

On 7/12/09, Heinrich Apfelmus <apfelmus at quantentunnel.de> wrote:
> Raynor Vliegendhart wrote:
> > On 7/9/09, Heinrich Apfelmus <apfelmus at quantentunnel.de> 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