Reader monad - how does it conform to Monad interface?

Question

I'm learning category theory. I understand the concept of reader monad, it's even pretty easy to implement:

case class Reader[DEP, A](g: DEP => A) {
  def apply(dep: DEP): A = g(dep)

  def map[B](f: A => B): Reader[DEP, B] = Reader(dep => f(apply(dep)))

  def flatMap[B](f: A => Reader[DEP, B]): Reader[DEP, B] = Reader(dep => f(apply(dep)) apply dep)
}

However, I have problems implementing it with constraint to some generic Monad interface, i.e

trait Monad[A] {
  def pure(a: A): Monad[A]

  def map[B](f: A => B): Monad[B]

  def flatMap[B](f: A => Monad[B]): Monad[B]
}

let's forgot for a second that there's an applicative or functor and let's just put these 3 methods here.

Now, having this interface I have problems implementing ReaderMonad. map method is pretty straighforward, but what about pure and flatMap? What does it even mean to have pure on Reader? To implement flatMap, I need to have a function from A to Reader[DEP, B], but I have A => Monad[B], thus I'm not possible to access apply.

case class Reader[DEP, A](g: DEP => A) extends Monad[A] {
  def apply(dep: DEP): A = g(dep)

  override def pure(a: A): Reader[DEP, A] = Reader(_ => a) // what does it even mean in case of Reader

  override def map[B](f: (A) => B): Reader[DEP, B] = Reader(dep => f(apply(dep)))

  override def flatMap[B](f: (A) => Monad[B]): Reader[DEP, B] = ??? // to implement it, I need f to be (A) => Reader[DEP, B], not (A) => Monad[B]
}

Is it possible to implement it this way in scala? I tried to play around with self bound types, but it didn't work either. I know libraries like scalaz or cats uses typeclasses to implement these types, but this is just for educational purpose.

Answer 1

As you've discovered when trying to implement flatMap, the problem with declaring the Monad trait as you have is you lose the particular monad type you're defining when chaining operations. The usual way of defining the Monad trait is to parameterise it by the type constructor the monad instance is being defined for e.g.

trait Monad[M[_]] {
    def pure[A](a: A): M[A]
    def map[A, B](f: A => B, m: M[A]): M[B]
    def flatMap[A, B](f: A => M[B], m : M[A]): M[B]
}

So M is a unary type constructor such as List or Option. You can think of a Reader[DEP, A] as being a computation which depends on some environment type DEP which returns a value of type A. Since this has two type parameters you need to fix the environment parameter type when defining the monad instance:

case class Reader[DEP, A](g: DEP => A)

class ReaderMonad[DEP]() extends Monad[({type t[X] = Reader[DEP, X]})#t] {
    def pure[A](a: A) = Reader[DEP, A](_ => a)
    def map[A, B](f: A => B,m: Reader[DEP,A]): Reader[DEP,B] = Reader(env => f(m.g(env)))
    def flatMap[A, B](f: A => Reader[DEP,B],m: Reader[DEP,A]): Reader[DEP,B] = Reader(env => f(m.g(env)).g(env))
}

({type t[X] = Reader[DEP, X]})#t is a type lambda used to partially apply one of the two parameters for Reader[DEP, A].

Now pure returns a Reader which ignores the environment and returns the given value directly.

flatMap constructs a Reader which when run will run the inner computation, use the result to construct the next computation and run it with the same environment.