implicit conversion to a monad

[Ka Ter]

Hi,

I'm trying to get into the monad and monad transformer stuff. I wrote an
Identity monad and an IdentityT. Latter one should be able
to wrap arbitrary other monads (and simply does nothing). But as a monad
transformer is also a monad, why can't I compose an IdentityT with an
IdentityT in the test method below? What is the missing implicit conversion?

object MonadTest
{
trait Monad[M[_]]
{
def point[B](value: B): M[B]
def fmap[A, B](m: M[A])(f: A => B): M[B]
def bind[A, B](m: M[A])(f: A => M[B]): M[B]
}

case class Identity[A](val value: A)

case class IdentityT[M[_] : Monad, A](val value: M[A])

object Implicits
{
implicit object IdentityMonad extends Monad[Identity]
{
def point[B](value: B) = Identity(value)
def fmap[A, B](m: Identity[A])(f: A => B) = point(f(m.value))
def bind[A, B](m: Identity[A])(f: A => Identity[B]) =
point(f(m.value).value)
}

implicit def identityTMonadInstance[M[_] : Monad] = new
Monad[({type O[X] = IdentityT[M, X]})#O]
{
val inner = implicitly[Monad[M]]

def point[B](value: B): IdentityT[M, B] =
IdentityT(inner.point(value))
def fmap[A, B](m: IdentityT[M, A])(f: A => B): IdentityT[M,
B] = IdentityT(inner.fmap(m.value)(f))
def bind[A, B](m: IdentityT[M, A])(f: A => IdentityT[M, B]):
IdentityT[M, B] = IdentityT(
inner.bind(m.value)((a: A) => f(a).value))
}
}

def test =
{
import Implicits._

val i = Identity(5)
val it = IdentityT(i)
val itt = IdentityT(it) // ERROR: Does not compile! Which
implicit conversion does I need?
}
}

--
Best Regards

Ka Ter

[Stephen Compall]

On Mon, 2013-01-14 at 17:38 +0100, Ka Ter wrote:

Hi,

I'm trying to get into the monad and monad transformer stuff. I wrote an
Identity monad and an IdentityT.

I'll start by picking out the parts that matter:

import scalaz.Monad

case class Identity[A](val value: A)

implicit object IdentityMonad extends Monad[Identity

] {
  def point[A](a: => A): Identity[A] = sys error "whatever"
  def bind[A, B](fa: Identity[A])(f: A => Identity[B]): Identity[B] =
    sys error "whatever"
}

case class IdentityT[M[_], A](val value: M[A])
object IdentityT {
  implicit def idtmonad[M[_]: Monad, A, B] =
    new Monad[({type λ[α] = IdentityT[M, α]})#λ] {
      def point[A](a: => A): IdentityT[M, A] = sys error "whatever"
      def bind[A, B](fa: IdentityT[M, A])(f: A => IdentityT[M, B]
                    ): IdentityT[M, B] =
        sys error "whatever"
    }
}

And so we

scala> val i = Identity(42)
i: Identity[Int] = Identity(42)

scala> val it = IdentityT(i)
it: IdentityT[Identity,Int] = IdentityT(Identity(42))

scala> val itt = IdentityT(it)
<console>:13: error: no type parameters for method apply: (value: M[A])IdentityT[M,A] in object IdentityT exist so that it can be applied to arguments (IdentityT[Identity,Int])
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : IdentityT[Identity,Int]
 required: ?M
       val itt = IdentityT(it)
                 ^

The essence of the problem is that scalac is trying to fill a M[A] argument with something of the shape X[Y, Z], and doesn't know how.

scalaz provides the tools to solve your problem. Add to IdentityT's companion:

import scalaz.Unapply

/** Unpack `M0[F0[_], B0]` to `[b]M0[F0, b]` and `B`. */
implicit def unapplyMFB2[TC[_[_]], M0[_[_], _], F0[_], B0
                       ](implicit TC0: TC[({type λ[α] = M0[F0, α]})#λ]) =
  new Unapply[TC, M0[F0, B0]] {
    type M[X] = M0[F0, X]
    type A = B0
    def TC = TC0
    def apply(ma: M0[F0, B0]) = ma
  }

def lift[MA](fa: MA)(implicit U: Unapply[Monad, MA]): IdentityT[U.M, U.A] =
  IdentityT(U(fa))

Just like before (please forgive me for adding newlines to REPL's output):

scala> val i = Identity(42)
i: Identity[Int] = Identity(42)

scala> val it = IdentityT lift i
it: IdentityT[scalaz.Unapply[scalaz.Monad,Identity[Int]]
                {type M[X] = Identity[X]; type A = Int}#M,
              Int]
  = IdentityT(Identity(42))

scala> it: IdentityT[Identity, Int]
it: IdentityT[Identity, Int]
res1: IdentityT[Identity,Int] = IdentityT(Identity(42))

Note that it reduced to the type you expected; you can run the reduction above by reading the it inferred type.

We haven't even used unapplyMFB2 yet though (which could be included in Unapply.scala in scalaz, if you like):

scala> IdentityT lift res1
res2: IdentityT[scalaz.Unapply[scalaz.Monad,IdentityT[Identity,Int]]
                  {type M[X] = IdentityT[Identity,X]; type A = Int}#M,
                Int]
  = IdentityT(IdentityT(Identity(42)))

scala> val itt = IdentityT lift it
itt: IdentityT[scalaz.Unapply[scalaz.Monad,IdentityT[scalaz.Unapply[scalaz.Monad,Identity[Int]]
                                                       {type M[X] = Identity[X]; type A = Int}#M,
                                                     Int]]
                 {type M[X] = IdentityT[scalaz.Unapply[scalaz.Monad,Identity[Int]]
                                          {type M[X] = Identity[X]; type A = Int}#M,
                                        X];
                  type A = Int}#M,
               Int]
  = IdentityT(IdentityT(Identity(42)))

Note that no matter the form, you get the right result. I'll wait here while you trace what that itt's Unapply should reduce to:

scala> itt: IdentityT[({type F[A] = IdentityT[Identity, A]})#F, Int]
res3: IdentityT[[A]IdentityT[Identity,A],Int] = IdentityT(IdentityT(Identity(42)))

Now try IdentityT lift (IdentityT lift (IdentityT lift itt)). I'll wait here again, while you wait for scalac to figure out what you're saying.

I hope you enjoyed this adventure, and have a newfound appreciation for the inference you get when working with mtl in Haskell.

-- Stephen Compall ^aCollection allSatisfy: [:each|aCondition]: less is better

[Ka Ter]

Hi Stephen,

thank you very much for the detailed explanation. This was the missing glue that prevented me from applying monads to my graph based framework for a very long time. All attempts using type lambdas and even casts failed. The only thing that worked are explicit defined types but this is unapplicable for users who want to define monad based graph traversals. Below you find my test code.
Again: thank you!

Best Regards

Ka Ter

/**
 * This works.
 */
object MonadTest3
{
	import scalaz.Unapply
	
	trait Monad[M[_]]
	{
		def point[B](value: B): M[B]
		def fmap[A, B](m: M[A])(f: A => B): M[B]
		def bind[A, B](m: M[A])(f: A => M[B]): M[B]
	}	
	
	case class Identity[A](val value: A)

	case class IdentityT[M[_], A](val value: M[A])
	
	object IdentityT
	{
		def lift[MA](ma: MA)(implicit U: Unapply[Monad, MA]): IdentityT[U.M, U.A] = IdentityT(U(ma))
	}

	object Implicits 
	{
		implicit object IdentityMonad extends Monad[Identity]
		{
			def point[B](value: B) = Identity(value)
			def fmap[A, B](m: Identity[A])(f: A => B) = point(f(m.value))
			def bind[A, B](m: Identity[A])(f: A => Identity[B]) = point(f(m.value).value)
		}
			
		implicit def identityTMonadInstance[M[_]](implicit monad: Monad[M]) = 
			new Monad[({type O[X] = IdentityT[M, X]})#O]
		{			
			def point[B](value: B): IdentityT[M, B] = IdentityT(monad.point(value))
			def fmap[A, B](m: IdentityT[M, A])(f: A => B): IdentityT[M, B] = IdentityT(monad.fmap(m.value)(f))
			def bind[A, B](m: IdentityT[M, A])(f: A => IdentityT[M, B]): IdentityT[M, B] = IdentityT(
					monad.bind(m.value)(a => f(a).value))
		}
		
		implicit class Monadic[A, M1[_]](value: M1[A])(implicit m1: Monad[M1])
		{
			def map[B](f: A => B): M1[B] = m1.fmap(value)(f)
		}
		
		implicit class MonadicT[A, M1[_], M2[_[_],_]](value: M2[M1, A])
			(implicit m2: Monad[({type O[X] = M2[M1, X]})#O])
		{
			def map[B](f: A => B): M2[M1, B] = m2.fmap(value)(f)
		}
			
		implicit def unapplyMFB2[M0[_[_],_], F0[_], B0](implicit TC0: Monad[({type λ[α] = M0[F0, α]})#λ]) =
				new Unapply[Monad, M0[F0, B0]] 
		{
		    type M[X] = M0[F0, X]
		    type A = B0
		    def TC = TC0
		    def apply(ma: M0[F0, B0]): M[B0] = ma
		}		
	}	
	
	def test =
	{
		import Implicits._

		val i = Identity(5)		
		val it = IdentityT.lift(i)		
		val itt = IdentityT.lift(it)		
		val ittt = IdentityT.lift(itt)
				
		println( i.map(_ + 1) )		
		println( it.map(_ + 2) )
		println( itt.map(_ + 3) )
		println( ittt.map(_ + 3) )
	}
	
	def main(args: Array[String]): Unit =
	{
		test
	}
}