When is a composition of catamorphisms a catamorphism?
From page 3 of http://research.microsoft.com/en-us/um/people/emeijer/Papers/meijer94more.pd... :
it is not true in general that catamorphisms are closed under composition When is this true?
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 < sebastien@chaoticresearch.com> wrote:
From page 3 of http://research.microsoft.com/en-us/um/people/emeijer/Papers/meijer94more.pd... :
it is not true in general that catamorphisms are closed under composition
When is this true?
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
Thanks Wren. That was my guess too, but it seems not necessary:
http://stackoverflow.com/questions/12103309/when-is-a-composition-of-catamor...
On Sat, Aug 25, 2012 at 10:33 PM, wren ng thornton
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
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-catamor...
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
participants (2)
-
Sebastien Zany -
wren ng thornton