Re: [Haskell-cafe] When is a composition of catamorphisms a catamorphism?
On 8/26/12 9:10 PM, Sebastien Zany wrote: Thanks Wren. That was my guess too, but it seems not necessary: http://stackoverflow.com/questions/12103309/when-is-a-composition-of-catamorphisms-a-catamorphism Well, sure. I was meaning in the general case. If you have the right kind of distributivity property (as colah suggests) then things will work out for the particular case. But, having the right kind of distributivity property typically amounts to being a natural transformation in some appropriately related category; so that just defers the question to whether an appropriately related category always exists, and whether we can formalize what appropriately related means. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] When is a composition of catamorphisms a catamorphism?
Thanks Wren. That was my guess too, but it seems not necessary: http://stackoverflow.com/questions/12103309/when-is-a-composition-of-catamorphisms-a-catamorphism On Sat, Aug 25, 2012 at 10:33 PM, wren ng thornton w...@freegeek.orgwrote: 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 :: (F1 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.htmlhttp://comonad.com/haskell/catamorphisms.html we have the law: Given 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, ~wren __**_ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] When is a composition of catamorphisms a catamorphism?
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 :: (F1 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 we have the law: Given 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, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] When is a composition of catamorphisms a catamorphism?
More specifically (assuming I understood the statement correctly): Suppose I have two base functors F1 and F2 and folds for each: fold1 :: (F1 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? On Thu, Aug 23, 2012 at 10:11 PM, Sebastien Zany sebast...@chaoticresearch.com wrote: From page 3 of http://research.microsoft.com/en-us/um/people/emeijer/Papers/meijer94more.pdf : it is not true in general that catamorphisms are closed under composition When is this true? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] When is a composition of catamorphisms a catamorphism?
From page 3 of http://research.microsoft.com/en-us/um/people/emeijer/Papers/meijer94more.pdf : it is not true in general that catamorphisms are closed under composition When is this true? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
