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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Sjoerd Visscher http://w3future.com