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

[Heinrich Apfelmus]

Brent Yorgey wrote:
> Raynor Vliegendhart wrote:
>
>> 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
> 
> [] is a strange functor to use with hylo, since it is already
> recursive and its only base case (the empty list) doesn't contain any
> a's.  Think about the intermediate structure that
> 
>   hylo (unfoldr (\a -> Just (a,a))) head
> 
> is building up: it is a list of lists of lists of lists of lists of
> lists of.... no wonder it doesn't terminate! =)

Yep, not terminating is the correct behavior here.


In particular, we have

    example = hylo repeat head
            = cata head . ana repeat

and the intermediate data structure is

    Fix []

which is an infinite nested tower of infinite lists.


Regards,
apfelmus

--
http://apfelmus.nfshost.com