HigherKinded.scala

 trait Functor[F[_]] {
        def map[A,B](fa: F[A])(f: A => B): F[B]
    }

    trait Applicative[F[_]] extends Functor[F] {
        def unit[A](a: => A): F[A]

        def map2[A,B,C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]

        def map[A,B](fa: F[A])(f: A => B): F[B] =
            map2(fa, unit(()))((a, _) => f(a))

        def traverse[A,B](as: List[A])(f: A => F[B]): F[List[B]] =
            as.foldRight(unit(List[B]()))((a, fbs) => map2(f(a), fbs)(_ :: _))
    }

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

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

        def flatMap[A,B](ma: F[A])(f: A => F[B]): F[B]

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

        def map2[A,B,C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C] =
            flatMap(fa)(a => map(fb)(b => f(a, b)))

    }

    trait IO[A] { self =>

        def run(): A

        def map[B](f: A => B): IO[B] = new IO[B] {def run(): B = f(self.run())}

        def flatMap[B](f: A => IO[B]): IO[B] = new IO[B] {def run(): B = f(self.run()).run()}

    }

    object IO extends Monad[IO] {

        def unit[A](a: => A): IO[A] = new IO[A] { def run() = a }

        def flatMap[A,B](fa: IO[A])(f: A => IO[B]) = fa flatMap f

        def apply[A](a: => A): IO[A] = unit(a)

    }