How to implement the `List` monad transformer in Scala?

Question

I have a monad that is very similar to a collection monad. I'm currently trying to implement a monad transformer for it, but I'm failing.

I've looked at the ListT implementation in Scalaz 6 and 7, but I cannot understand how it works. It uses some additional type Step, whose purpose is unclear to me.

So can someone please explain to me how to implement a list monad transformer, either by explaining the Scalaz approach or using a different implementation?

Answer 1

I am not quite sure, what the Step means in scalaz, but implementing a ListT is pretty straight forward. Depending on how many operations you want to put on it, it can be a little work, but the basic monad operations can be implemented as follows.

First we need typeclasses for monad and functor (we could also add applicative, but that is not necessary for this example):

trait Functor[F[_]] {
  def map[A,B](fa: F[A])(f: A => B): F[B]
}

trait Monad[F[_]] extends Functor[F] {
  def flatMap[A,B](fa: F[A])(f: A => F[B]): F[B]
  def pure[A](x: A): F[A]
}

object Monad {

  implicit object ListMonad extends Monad[List] {
    def map[A,B](fa: List[A])(f: A => B) = fa map f
    def flatMap[A,B](fa: List[A])(f: A => List[B]) = fa flatMap f
    def pure[A](x: A) = x :: Nil
  }

  implicit object OptionMonad extends Monad[Option] {
    def map[A,B](fa: Option[A])(f: A => B) = fa map f
    def flatMap[A,B](fa: Option[A])(f: A => Option[B]) = fa flatMap f
    def pure[A](x: A) = Some(x)
  }

  def apply[F[_] : Monad]: Monad[F] = implicitly[Monad[F]]

}

Once we have those, we can create the transformer, which basically just wraps the F[List[A]] and forwards the call to its map and flatMap function to the list by calling map on the containing functor and then calling map or flatMap resp. on the contained List/s.

final case class ListT[F[_] : Monad, A](fa: F[List[A]]) {
  def map[B](f: A => B) = ListT(Monad[F].map(fa)(_ map f))

  def flatMap[B](f: A => ListT[F, B]) = ListT(Monad[F].flatMap(fa) { _ match {
    case Nil => Monad[F].pure(List[B]())
    case list => list.map(f).reduce(_ ++ _).run
  }})

  def ++(that: ListT[F,A]) = ListT(Monad[F].flatMap(fa) { list1 =>
    Monad[F].map(that.run)(list1 ++ _)
  })

  def run = fa
}

Once we are done with modifying, we can get the resulting object by calling the run method on the ListT object. If you want, you can also add other list specific operations like in scalaz. This should be pretty straight forward. For example a :: could look as follows:

def ::(x: A) = ListT(Monad[F].map(fa)(x :: _))

Usage:

scala> ListT(Option(List(1,2,3)))
res6: ListT[Option,Int] = ListT(Some(List(1, 2, 3)))

scala> res6.map(_+45)
res7: ListT[Option,Int] = ListT(Some(List(46, 47, 48)))

scala> 13 :: res7
res8: ListT[Option,Int] = ListT(Some(List(13, 46, 47, 48)))

scala> res8.run
res10: Option[List[Int]] = Some(List(13, 46, 47, 48))

Answer 2

I think scalaz.ListT is incorrect in scalaz 7.0.x and 7.1.x.

https://github.com/scalaz/scalaz/issues/921

6.x version is correct. but it is same as StreamT.