sealed trait MyList[+A] {
  def flatMap[B](f: A => MyList[B]): MyList[B] = this match {
    case MyNil => MyNil
    case MyCons(head, tail) => f(head).append(tail.flatMap(f))
  }

  def append[AA >: A](other: MyList[AA]): MyList[AA] = this match {
    case MyNil => other
    case MyCons(head, tail) => MyCons(head, tail.append(other))
  }

  override def toString: String =
    "List(" + (this match {
      case MyNil => ""
      case MyCons(head, tail) => head.toString + "," + tail.toString
    }) + ")"
}

case object MyNil extends MyList[Nothing]
case class MyCons[+A](head: A, tail: MyList[A]) extends MyList[A]

object MyList {
  def pure[A](a: => A): MyList[A] = MyCons(a, MyNil)
}

trait Monad[M[_]] {
  def pure[A](a: => A): M[A]
  def flatMap[A,B](m: => M[A])(f: A => M[B]): M[B]
}

object Monad {
  implicit val listMonad: Monad[List] = new Monad[List] {
    def pure[A](a: => A): List[A] = List(a)
    def flatMap[A,B](m: => List[A])(f: A => List[B]): List[B] =
      m.flatMap(f)
  }

  implicit val myListMonad: Monad[MyList] = new Monad[MyList] {
    def pure[A](a: => A): MyList[A] = MyList.pure(a)
    def flatMap[A,B](m: => MyList[A])(f: A => MyList[B]): MyList[B] =
      m.flatMap(f)
  }
}

class MonadOps[M[_],A](value: M[A])(implicit m: Monad[M]) {
  def flatMap[B](f: A => M[B]): M[B] =
    m.flatMap(value)(f)

  def map[B](f: A => B): M[B] =
    m.flatMap(value){ a => m.pure(f(a)) }

  override def toString: String = value.toString
}

object MonadOps {
  implicit def toMonadOps[M[_],A](value: M[A])(implicit m: Monad[M]) =
    new MonadOps(value)(m)
}

object Main {
  def main(args: Array[String]): Unit = {
    val monadOps: MonadOps[List, Int] = List(1,2,3)
    val secondOps: MonadOps[List, Int] = monadOps.map { _ + 3 }
    println(secondOps)

    val Monad: Monad[List] = implicitly[Monad[List]]
    val list = List(1,2,3,4)
    val secondList = Monad.flatMap(list){ x => List(x + 3) }
    println(secondList)

    val ops: MonadOps[MyList, Int] = MyCons(3, MyCons(4, MyCons(5, MyNil)))
    val secOps: MonadOps[MyList, Int] = ops.map { _ + 2 }
    println(secOps)

    println(mapOverList(MyCons(1, MyCons(2, MyNil))){_ + 2})

    import MonadOps._
    val l: MyList[Int] = MyCons(1, MyCons(2, MyNil))
    println(l.map{_ + 2})
  }

  def mapOverList[A,B](l: MyList[A])(f: A => B): MyList[B] = {
    import MonadOps._
    l.map(f)
  }
}