# ekmett/recursion-schemes

Closed
opened this Issue Dec 7, 2012 · 8 comments

Projects
None yet
6 participants
Collaborator

### ppetr commented Dec 7, 2012

 I don't know if it's a good idea and if it isn't actually contained in some other generalized functions you already have, but I feel such monadic functions could be often useful: ```-- | A monadic catamorphism. cataM :: (Foldable t, T.Traversable (Base t), Monad m) => (Base t a -> m a) -- ^ a monadic (Base t)-algebra -> t -- ^ fixed point -> m a -- ^ result cataM f = c where c = f <=< T.mapM c <=< (return . project) -- | A monadic anamorphism anaM :: (Unfoldable t, T.Traversable (Base t), Monad m) => (a -> m (Base t a)) -- ^ a monadic (Base t)-coalgebra -> a -- ^ seed -> m t anaM g = a where a = (return . embed) <=< T.mapM a <=< g -- etc``` If you like the idea, I can provide them.

### sboosali commented Nov 16, 2015

 this would be great, as well as examples of their use.

### ChristopherKing42 commented May 10, 2016

 Or at implementation in arbitrary categories (of which the Kelsi category in one).

### sboosali commented May 11, 2016 • edited

 I can't get it to work. There are at least two ways: (the below might not typecheck) generalize Foldable and Functor ``````cataC :: (Category.Foldable t, Category.Functor (~>), f ~ Base t) => (f a ~> a) -> (t ~> a) cataC u = c where c = project Category.>>> Category.fmap c Category.>>> u `````` ("Category.Foldable" and "Category.Functor" don't exist) use Arrow to inject functions (project and fmap) ``````cataC :: (Foldable t, Arrow (~>), f ~ Base t) => (f a -> a) -> (t ~> a) cataC u = c where c = arr (project Prelude.>>> fmap c) Category.>>> u `````` that's what the (. return) did in cataM. will they be easy to work with? On Wed, May 11, 2016 at 2:56 AM, Christopher King notifications@github.com wrote: Or at implementation in arbitrary categories (of which the Kelsi category in one). — You are receiving this because you commented. Reply to this email directly or view it on GitHub #3 (comment) (this message was composed with dictation: charitably interpret typos)Sam Boosalis
Collaborator

### phadej commented Jun 29, 2016

 You can implement `cataM` using `cata`: ```cataM :: ... => (Base t a -> m a) -> t -> m a cata :: ... => (Base t b -> b ) -> t -> b cata' :: ... => (Base t (m a) -> m a) -> t -> m a cata' = cata cataM f = (>>= f) . cata (traverse (>>= f))``` ```λ Prelude Data.Functor.Foldable > let cataM f = (>>= f) . cata (traverse (>>= f)) λ Prelude Data.Functor.Foldable > :t cataM cataM :: (Monad m, Traversable (Base t), Data.Functor.Foldable.Foldable t) => (Base t b -> m b) -> t -> m b``` IIRC, when I needed `cataM` I got away with `cata` by defining `f` to have `traverse` and `>>=` built-in. The problem is e.g. `Prim [a]` is not `Traversable` atm, but you can do, yet it's easy to forget to `>>` previous actions: ```> flip runState (0 :: Int) \$ cata (\case { Nil -> return (); Cons _ x -> x >> modify' succ }) "foobar" ((),6)```
Collaborator

### phadej commented Jul 5, 2016

 Added `Traversable` to `Prim [a]` in ca17aa9

Collaborator

### phadej commented Jul 6, 2016

 FWIW: https://hackage.haskell.org/package/unification-fd-0.10.0.1/docs/Data-Functor-Fixedpoint.html defines `cataM`, `anaM` and `hyloM`, yet I'm not sure if we want to made arbitrary choice in which order to sequence the effects,. Manual definition with non-monadic version is more powerful.

### kozross commented Mar 26, 2018

 @phadej Could you elaborate on 'manual definition with non-monadic version' a bit? I understand why giving users control over sequencing is a good thing, but I'm having a bit of trouble thinking of how you'd write something like this for, say, an anamorphism with monadic effects (such as randomness via `MonadRandom`).
Owner

### ekmett commented Apr 2, 2018

 `ana` with monadic effects is sort of the 'default' direction. It follows just from having a distributive law for "pushing" the effects down into the seed over the functor, so that you never have to deal with it! For your monadic randomness example, you'd ideally use an RNG that supports some form of `split` and push down into each branch a different seed, enabling computation down each branch to proceed independently rather than sequencing them all together. Mind you, this "seed" is the same general idea as an anamorphism to begin with. =) This is fundamentally different than running the anamorphism and trying to sequence some state through all the parts of a functor. As for ```cataM :: (Traversable (Base t), Monad m, Recursive t) => (Base t c -> m c) -> t -> m c cataM = cata . (sequence >=>)``` it can be defined using `cata` as @phadej noted, the problem is that it bakes in a bunch of assumptions about "how" we distribute our monad/applicative over the base functor. I've left off `cataM` primarily because it isn't nicely canonical, and because you tend to get a huge pile of nested effects with bottoms lurking all over the place for infinite examples. `sequence` and `distribute` are both valid choices of distributive law. It is somewhat illustrative to play with `gcata` and `gana` with those as the distributive laws at play, and compare them to the various `distFoo`s offered by this library. I also just checked and found it interesting that when you go to do the opposite construction using `Distributive` to make "comonadic anamorphisms" you get something totally boring! ```anaW :: (Distributive (Base t), Comonad f, Corecursive t) => (f a -> Base t a) -> f a -> t anaW = ana . (=>= distribute) ``` A distributive functor has a fixed shape. `Nu f` for a distributive functor is an infinite tree of that shape, unfolding it level by level by stepping the anamorphism just gives you more copies of the same shape. This effectively models an infinitely deep function that only ever consumes arguments. The seed is useless. Once you properly account for laziness you might be able to sprinkle some bottoms throughout that shape like landmines -- I'm not sure, I haven't checked, but that's it. I had some hope when I first thought about it because `Cofree f` for a distributive `f` is a form of (possibly-infinite-state) Moore machine and the type of seed represents the state space, but `Nu f` leaves you no labels for the leaves. That said, if you can sprinkle bottoms through the tree maybe you can get some kind of halting test by using `seq` to check for bottoms but only in a semi-algorithm sense, but that's about all I can come up with for the sort of shapes that'd admit a "comonadic anamorphism".

Merged