i have been playing around with defining the monad for State[S,_] entirely ad-hoc, defining an alias State[S,A] => S => (S,A) but it may not be possible because the monad is defined for a lambda type and i can't figure out how to pimp a lambda type to add implicits in a way that the compiler will actually pick up and use

gistfile1.scala

import language.higherKinds

object Stuff {

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

  object Monad {
    def apply[M[_]: Monad] = implicitly[Monad[M]]
  }

  implicit class MonadSyntax[A, M[_]: Monad](a: M[A]) {
    def map[B](f: A => B) = Monad[M].map(a, f)
    def flatMap[B](f: A => M[B]) = Monad[M].bind(a, f)
  }

  implicit class MonadSyntax2[A](a: A) {
    def point[M[_]: Monad]: M[A] = Monad[M].point(a)
  }

}

object Instances {
  import Stuff._

  type Id[A] = A

  implicit val IdMonad = new Monad[Id] {
    def map[A, B](ma: Id[A], f: A => B) = f(ma)
    def bind[A, B](ma: Id[A], f: A => Id[B]) = f(ma)
    def point[A](a: A): Id[A] = a
  }

  implicit val OptionMonad = new Monad[Option] {
    def map[A, B](ma: Option[A], f: A => B) = ma.map(f)
    def bind[A, B](ma: Option[A], f: A => Option[B]) = ma.flatMap(f)
    def point[A](a: A): Option[A] = Option(a)
  }

  type State[S, A] = S => (S, A)

  implicit def StateMonad[S] = new Monad[({ type l[a] = State[S, a] })#l] {
    def map[A, B](ma: State[S, A], f: A => B) = { s =>
      val (s0, a) = ma(s)
      (s0, f(a))
    }
    def bind[A, B](ma: State[S, A], f: A => State[S, B]) = { s =>
      val (s0, a) = ma(s)
      f(a)(s0)
    }
    def point[A](a: A): State[S, A] = { s => (s, a) }
  }

}

object Test2 {

  import Stuff._

  def fib[M[_]: Monad](n: Int): M[Int] =
    if (n > 1)
      for {
        a <- fib(n - 1)
        b <- fib(n - 2)
      } yield a + b
    else
      n.point

  {

    import Instances._

    println((1 to 10).toList.map(fib[Id]))
    println((1 to 10).toList.map(fib[Option]))
    println((1 to 10).toList.map(fib[({ type l[a] = State[String, a] })#l]).map(_.apply("foo"))) // :-/

    def get[S]: State[S, S] = s => (s, s)
    def put[S](s: S): State[S, Unit] = _ => (s, ())
    def mod[S, T](f: S => S): State[S, Unit] = s => (f(s), ())

    def x: State[Int, Int] = for {
      n <- get[Int] // doesn't compile; monad is defined for lambda type
      _ <- put(n + 1)
    } yield n

  }

}