Monad.scala

trait Functor[F[_]] {

  def unit[A](a: A): F[A]

  def map[A, B](f: A => B): F[A] => F[B] // ma => flatMap((a: A) => unit(f(a)))(ma)
  
}

trait Applicative[F[_]] extends Functor[F] {

  def apply[A,B](fab: F[A => B])(fa: F[A]): F[B] 
    // = map2(fa, fab)(a => a2b => a2b(a))
  
}


trait Monad[M[_]] extends Applicative[M] {

  def flatMap[A, B](f: A => M[B]): M[A] => M[B]
    // = ma => join(map(f)(ma))
    // = compose((ma: M[A]) => map(f)(ma), (x: M[B]) => x) 

  def join[A](m: M[M[A]]): M[A] = flatMap((a:M[A]) => a)(m)

  def apply[A,B](fab: M[A => B])(fa: M[A]): M[B] 
    = flatMap((a2b: A => B) => flatMap((a: A) => unit(a2b(a)))(fa))(fab)
    // = map2(fa, fab)(a => a2b => a2b(a))

}

trait Traversing[F[_]] {
  
  def traverse[A, B, M[_]](f: A => M[B])(fa: F[A])(implicit m : Applicative[F]): M[F[B]]
    = sequence(m.map(f)(fa)) 
  
  def sequence[A, M[_]](fma: F[M[A]])(implicit m : Applicative[F]): M[F[A]] 
    // = traverse((ma: M[A]) => ma)(fma)
}

object MonadicOperations {
  
  def compose[A, B, C, M[_]](f: A => M[B], g: B => M[C])(implicit m: Monad[M]): A => M[C]
    = a => m.flatMap(g)(m.flatMap(f)(m.unit(a)))
    // = a => join(map(g)(join(map(f)(unit(a)))))

  def map2[A,B,C, F[_]](fa: F[A], fb: F[B])(f: A => B => C)(implicit m: Applicative[F]): F[C]  
    = m.apply(m.apply(m.unit(f))(fa))(fb)
  
}


object MonadLaws {
  import MonadicOperations._

  def leftIdentity[A, B, M[+ _]](a: A, f: A => M[B])(implicit m: Monad[M]): Boolean = 
    m.flatMap(f)(m.unit(a)) == f(a)

  def rightIdentity[A, B, M[+ _]](ma: M[A], f: A => M[B])(implicit m: Monad[M]): Boolean = 
    m.flatMap(m.unit[A])(ma) == ma

  def associativity[A, B, C, M[+ _]](ma: M[A], f: A => M[B], g: B => M[C])(implicit m: Monad[M]): Boolean =
    m.flatMap(g)(m.flatMap(f)(ma)) == m.flatMap { (a: A) => m.flatMap(g)(f(a)) }(ma)

   
    
    
  def leftIdentityWithCompose[A, B, M[+ _]](a: A, f: A => M[B])(implicit m: Monad[M]): Boolean = 
    compose(f, (x : B) => m.unit(x)) == f

  def rightIdentityWithCompose[A, B, M[+ _]](a: A, f: A => M[B])(implicit m: Monad[M]): Boolean = 
    compose((x : A) => m.unit(x), f) == f
    
  def associativityWithCompose[A, B, C,  M[+ _]](f: A => M[B], g: B => M[C], h: C => M[C])(implicit m: Monad[M]): Boolean = 
    compose(f, compose(g, h)) == compose(compose(f, g), h)

}