[Haskell-cafe] Scrap your rolls/unrolls

[Sjoerd Visscher]

A little prettier (the cata detour wasn't needed after all):

   data IdThunk a
   type instance Force (IdThunk a) = a
   type Alg f a = f (IdThunk a) -> a

   fold :: CFunctor f ForceCat (->) => Alg f a -> Fix f -> a
   fold alg = alg . cmap (ForceCat $ fold alg)

   sumAlg :: Alg (ListF Int) Int
   sumAlg Nil = 0
   sumAlg (Cons a r) = a + r

   sumList :: List Int -> Int
   sumList = fold sumAlg

It all works out very well, so this trick seems to be really useful!

Sjoerd

On Oct 23, 2010, at 4:05 PM, Sjoerd Visscher wrote:

> 
> On Oct 23, 2010, at 1:27 PM, Sebastian Fischer wrote:
>> 
>> I think `Control.Functor.Categorical.CFunctor` is a more natural replacement for functor here. One can define
>> 
>>   instance CFunctor (ListF a) ForceCat Hask
>> 
>> and I was hoping that I could define `fold` based on CFunctor but I did not succeed. The usual definition of `fold` is
>> 
>>   fold :: Functor f => (f a -> a) -> Fix f -> a
>>   fold f = f . fmap (fold f)
>> 
>> and I tried to replace this with
>> 
>>   fold :: CFunctor f ForceCat Hask => ...
>> 
>> but did not find a combination of type signature and definition that compiled.
> 
> The catamorphism lies in the ForceCat category. Also, you can't just pass "a" to "f" because Force a is undefined.
> 
>   data IdThunk a
>   type instance Force (IdThunk a) = a
> 
>   cata :: CFunctor f ForceCat (->) => (f (IdThunk a) -> a) -> ForceCat (FixThunk f) (IdThunk a)
>   cata alg = ForceCat $ alg . cmap (cata alg)
> 
> Then you can define fold as follows:
> 
>   fold :: CFunctor f ForceCat (->) => (f (IdThunk a) -> a) -> Fix f -> a
>   fold = unForceCat . cata
> 
> Fortunately the IdThunk does not get in the way when defining algebras:
> 
>   sumAlg :: ListF Int (IdThunk Int) -> Int
>   sumAlg Nil = 0
>   sumAlg (Cons a r) = a + r
> 
> greetings,
> Sjoerd Visscher
> 
> 
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 

--
Sjoerd Visscher
http://w3future.com