Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Suggestion: Add monadic variants of various ...morphism functions. #3

Closed
ppetr opened this issue Dec 7, 2012 · 8 comments
Closed

Suggestion: Add monadic variants of various ...morphism functions. #3

ppetr opened this issue Dec 7, 2012 · 8 comments

Comments

@ppetr
Copy link
Collaborator

@ppetr 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
Copy link

@sboosali sboosali commented Nov 16, 2015

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

@ChristopherKing42
Copy link

@ChristopherKing42 ChristopherKing42 commented May 10, 2016

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

@sboosali
Copy link

@sboosali sboosali commented May 11, 2016

I can't get it to work. There are at least two ways:

(the below might not typecheck)

  1. 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)

  1. 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

@phadej
Copy link
Contributor

@phadej 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)
@phadej
Copy link
Contributor

@phadej phadej commented Jul 5, 2016

Added Traversable to Prim [a] in ca17aa9

@phadej phadej closed this Jul 5, 2016
@phadej
Copy link
Contributor

@phadej 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
Copy link

@kozross 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).

@ekmett
Copy link
Collaborator

@ekmett 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 distFoos 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".

phadej added a commit that referenced this issue Jun 5, 2020
- `fix` is at https://github.com/phadej/fix. I'll give Samuel and Ryan
  commit access to it, if this patch is accepted.

- There are two bits to this:
  - `Fix`, `Mu` and `Nu` are not essential to the use of `recursion-schemes`,
    in fact: nothing broke. (Not that we have too many examples).

  - **If** someone wants to add Fix to `base`, we'd be closer to that.
   `fix` is essentially "done" package.

  - There's https://hackage.haskell.org/package/data-fix package,
    and the *right* way forward would be to use it.
    I'm in contact with the author to make `data-fix`. There are
    differences:
    - has a `(~>)` alias for hylo
    - `unfix` vs. `unFix`
    - `data-fix` uses `Eq (f (Fix f))` like instances
    - provides cataM, anaM, hyloM.
      We (with edward saying final words) decided not to add them.
      #3

    The list in increasing amount of how hard the topics
    are to settle on :)
phadej added a commit that referenced this issue Jun 5, 2020
- `fix` is at https://github.com/phadej/fix. I'll give Samuel and Ryan
  commit access to it, if this patch is accepted.

- There are two bits to this:
  - `Fix`, `Mu` and `Nu` are not essential to the use of `recursion-schemes`,
    in fact: nothing broke. (Not that we have too many examples).

  - **If** someone wants to add Fix to `base`, we'd be closer to that.
   `fix` is essentially "done" package.

  - There's https://hackage.haskell.org/package/data-fix package,
    and the *right* way forward would be to use it.
    I'm in contact with the author to make `data-fix`. There are
    differences:
    - has a `(~>)` alias for hylo
    - `unfix` vs. `unFix`
    - `data-fix` uses `Eq (f (Fix f))` like instances
    - provides cataM, anaM, hyloM.
      We (with edward saying final words) decided not to add them.
      #3

    The list in increasing amount of how hard the topics
    are to settle on :)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants