[Haskell-cafe] Re: excercise - a completely lazy sorting algorithm

Heinrich Apfelmus apfelmus at quantentunnel.de
Sun Jul 12 11:26:55 EDT 2009


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?


Regards,
apfelmus

--
http://apfelmus.nfshost.com



More information about the Haskell-Cafe mailing list