My solution of monad excercises by Tony morris

Monads

// 1. Start here. Observe this trait
trait Monad[M[_]] {
  def flatMap[A, B](a: M[A], f: A => M[B]): M[B]
  def unital[A](a: A): M[A]
}
 
// A simple data type, which turns out to satisfy the above trait
case class Inter[A](f: Int => A)
 
// So does this.
case class Identity[A](a: A)
 
// Monad implementations
object Monad {
  // 2. Replace sys.error("todo") with an implementation
  def ListMonad: Monad[List] = new Monad[List] {
    def flatMap[A, B](a: List[A], f: A => List[B]): List[B] = a flatMap f
    def unital[A](a: A): List[A] = List(a)
  }
 
  // 3. Replace sys.error("todo") with an implementation
  def OptionMonad: Monad[Option] = new Monad[Option] {
    def flatMap[A, B](a: Option[A], f: A => Option[B]): Option[B] = a flatMap f
    def unital[A](a: A): Option[A] = Some(a)
  }
 
  // 4. Replace sys.error("todo") with an implementation
  def InterMonad: Monad[Inter] = new Monad[Inter] {
    def flatMap[A, B](a: Inter[A], f: A => Inter[B]): Inter[B] = {
      def _flatMap[A, B](a: Inter[A], f: A => Inter[B]):Int => B = (i: Int) => {
          (f compose a.f)(i) match { case Inter(f) => f(i) }
      }
      Inter(_flatMap(a, f))
    }
    def unital[A](a: A): Inter[A] = Inter(_ => a)    
  }
  // 5. Replace sys.error("todo") with an implementation
  def IdentityMonad: Monad[Identity] = new Monad[Identity] {
    def flatMap[A, B](a: Identity[A], f: A => Identity[B]): Identity[B] = f(a.a)
    def unital[A](a: A): Identity[A] = Identity(a)
  }
}
 
object MonadicFunctions {
  // 6. Replace sys.error("todo") with an implementation
  def sequence[M[_], A](as: List[M[A]], m: Monad[M]): M[List[A]] = {
    def _sequence(xs: List[M[A]], ma: M[List[A]]): M[List[A]] = xs match {
      case Nil => ma
      case x :: ys => _sequence(ys, m.flatMap(ma, (zs: List[A]) => m.flatMap(x, (a: A) => m.unital(zs :+ a)))) 
    }
    _sequence(as, m.unital(Nil))
  }
 
  // 7. Replace sys.error("todo") with an implementation
  def fmap[M[_], A, B](a: M[A], f: A => B, m: Monad[M]): M[B] = m.flatMap(a, (a:A) => m.unital(f(a)))
 
  // 8. Replace sys.error("todo") with an implementation
  def flatten[M[_], A](a: M[M[A]], m: Monad[M]): M[A] = m.flatMap(a, (a1: M[A]) => a1)
 
  // 9. Replace sys.error("todo") with an implementation
  def apply[M[_], A, B](f: M[A => B], a: M[A], m: Monad[M]): M[B] =
    m.flatMap(f, (f: A => B) => m.flatMap(a, (a: A) => m.unital(f(a))))  
 
  // 10. Replace sys.error("todo") with an implementation
  def filterM[M[_], A](f: A => M[Boolean], as: List[A], m: Monad[M]): M[List[A]] = {
    def _filterMOne(a: A): M[List[A]]= m.flatMap(f(a), (b: Boolean) => m.unital(if(b) List(a) else Nil))
    def _filterMAll(xs: List[A], acc: M[List[A]]): M[List[A]] = xs match {
      case Nil => acc
      case x :: ys => 
        _filterMAll(ys, 
          m.flatMap(acc, (zs: List[A]) => m.flatMap(_filterMOne(x), (zs1: List[A]) => m.unital(zs ::: zs1))))
    }  
    m.flatMap(m.unital(as), (as: List[A]) => _filterMAll(as, m.unital(Nil)))
  }
 
  // 11. Replace sys.error("todo") with an implementation
  def replicateM[M[_], A](n: Int, a: M[A], m: Monad[M]): M[List[A]] = {
    def _replicate(current: Int, ma: M[List[A]]): M[List[A]] = current match {
      case 0 => ma
      case _ => _replicate(current - 1, m.flatMap(ma, (xs: List[A]) => m.flatMap(a, (a: A) => m.unital(xs :+ a))))
    }
    _replicate(n, m.unital(Nil))
  }
  
  // 12. Replace sys.error("todo") with an implementation
  def lift2[M[_], A, B, C](f: (A, B) => C, a: M[A], b: M[B], m: Monad[M]): M[C] = {
    m.flatMap(a, (a: A) => m.flatMap(b, (b: B) => m.unital(f(a, b))))
  }
 
  // lift3, lift4, etc. Interesting question: Can we have liftN?
}