[Haskell-cafe] When is a composition of catamorphisms a catamorphism?
sebastien at chaoticresearch.com
Mon Aug 27 03:10:05 CEST 2012
Thanks Wren. That was my guess too, but it seems not necessary:
On Sat, Aug 25, 2012 at 10:33 PM, wren ng thornton <wren at freegeek.org>wrote:
> On 8/24/12 3:44 AM, Sebastien Zany wrote:
>> More specifically (assuming I understood the statement correctly):
>> Suppose I have two base functors F1 and F2 and folds for each: fold1 ::
>> a -> a) -> (μF1 -> a) and fold2 :: (F2 a -> a) -> (μF2 -> a).
>> Now suppose I have two algebras f :: F1 μF2 -> μF2 and g :: F2 A -> A.
>> When is the composition (fold2 g) . (fold1 f) :: μF1 -> A a catamorphism?
> From <http://comonad.com/haskell/**catamorphisms.html<http://comonad.com/haskell/catamorphisms.html>>
> we have the law:
> F, a functor
> G, a functor
> e, a natural transformation from F to G
> (i.e., e :: forall a. F a -> G a)
> g, a G-algebra
> (i.e., f :: G X -> X, for some fixed X)
> it follows that
> cata g . cata (In . e) = cata (g . e)
> The proof of which is easy. So it's sufficient to be a catamorphism if
> your f = In . e for some e. I don't recall off-hand whether that's
> necessary, though it seems likely
> Live well,
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe