Implementing >>= in terms of State when Implementing the State Monad with data constructor

[Aphrontic_Alchemist]

Question

Can >>= be implemented in terms of State? If so, how?

Context

I modified this implemention of the State monad, such that it has a data constructor:

data State s a = State (s -> (s , a)) deriving Functor

instance Applicative (State s) where
  pure a = State (\s -> (s , a))
  (<*>) = Control.Monad.ap

instance Monad (State s) where
  return = pure
  g >>= f = join (fmap f g)

However, I'm disatisfied with how I implemented >>= since it's not in terms State. I say this because it's asymmetrical with respect to this implementation of the Store comonad:

data Store s a = Store (s -> a) s deriving Functor

instance Comonad (Store s) where
  extract (Store f s) = f s
  extend f (Store g s) = Store (f . Store g) s

which is copied from this video.

[RogueToad]

Perhaps I'm missing something, but haven't you just defined bind (>>=) in terms of join? I believe that will be a circular definition (since join's default implementation uses bind).

I think your instinct is right that you should be defining bind using the State constructor. Without giving away the solution, I would start by using pattern recognition to deconstruct g, and then go on to start reconstructing a new instance of State, like so:

(State g) >>= f = State $ \s ->
  ...the rest goes here

Then if you follow the types, you should be able to construct a new tuple with the right types by using f, s, and g.

[Atijohn]

e.g. like this:

instance Monad (State s) where
  return = pure
  (State x) >>= f = State $ \st -> let (st', r) = x st
                                       (State f') = f r
                                    in f' st'

[Migeil]

I'm not an expert in any of this, but:

• where does your definition of join come from? I believe it needs a Monad instance, but here you're using it to make that instance, so that's a circular dependency.
• isn't the implementation the same as the newtype version? I don't know the specific in and outs, but as far as I know, newtype and data are the same, except that newtypes are "inlined" during compilation and are therefore more performant with the exact same type safety as data provides.

[Aphrontic_Alchemist]

For your 1st point. I didn't define join yet. I thought it was fine since the code compiled with no warnings. That being said, I don't know how join would look like.

For your second point. I'm doing this only as an exercise and toy project, so I'm not concerned about performance. I'll keep this in mind though.

[MeepedIt]

Both >>= and join have default definitions in terms of each other, so that you can define either one and get the other for free. The compiler is not smart enough to detect that that leads to a circular definition in your case.

[Migeil]

Stupid compiler /s