Applied Functional Programming In Scala Day 1

Day1.scala

object Functions {

  /**
    * Functions
    * - Total (every element in the domain must have a representation in the co-domain)
    * - Deterministic (give always the same result for the same input)
    * - Not side effecting (the only result of the function is the mapped value)
    */

  /**
    * This is not a function as is not total.
    *
    * - it throws if is not defined for the input
    * - you cannot rely on the type signatures to know what's the behavior
    */
  def square(x: Int): Int = x match {
    case a if a > 0 => x * x
  }

  /**
    * To make the above total
    */
  def squareTotal(x: Int): Int = x * x


  /**
    * This is not a function as it is not deterministic.
    *
    * - they generate random bugs
    * - hard to test
    */
  def number(x: Int): Int =
    if (Math.random() < 0.5) x * 2
    else x * 3

  /**
    * To make the above deterministic
    */
  def numberDeterministic(x: Int): Int =
    if (x % 2 == 0) x * 2
    else x * 3


  /**
    * This is not a function as it has side effects
    */
  def triple(x: Int): Int = {
    println("Something")
    x * 3
  }

  /**
    * To make the above pure
    */
  def triplePure(x: Int): Int = x * 3

}

object EquationalThinking {

  def x = scala.io.StdIn.readLine()

  def replicate(s: String): String = s + s

  replicate(x)

  // Applying equational reasoning to the above
  // step 1
  replicate(scala.io.StdIn.readLine())

  // step 2
  scala.io.StdIn.readLine() + scala.io.StdIn.readLine()

  // this is changing the meaning of the program
}

object HigherOrderFunctions {

  /**
    * Any time a function accepts or returns a function is called higher order function
    */
  def filter(xs: List[Int])(f: Int => Boolean): List[Int] = ???

  /**
    * Either returns an error message or a parsed A and the remaining of the string
    */
  type Parser[A] = String => Either[String, (A, String)]

  val char: Parser[Char] =
    (input: String) => input.headOption.map(char => Right((char, input.drop(1)))).getOrElse(Left("No more input!"))

  def fail[A](error: String): Parser[A] =
    _ => Left(error)

  /**
    * Function combinator: combines functions to get functions of the same shape
    */
  def alt[A](l: Parser[A], r: Parser[A]): Parser[A] =
    (input: String) => l(input) match {
      case Left(_) => r(input)
      case x => x
    }

  def seq[A, B](fa: Parser[A], f: A => Parser[B]): Parser[B] =
    (input: String) => fa(input) match {
      case Left(err)              => Left(err)
      case Right((a, remaining))  => f(a)(remaining)
    }

  def pure[A](a: A): Parser[A] =
    (input: String) => Right(a, input)

  def map[A, B](fa: Parser[A])(f: A => B): Parser[B] =
    (input: String) => fa(input) match {
      case Left(err)              => Left(err)
      case Right((a, remaining))  => Right((f(a), remaining))
    }

  def pipe[A, B, C](fst: A => B)(snd: B => C): A => C =
    snd compose fst

  /**
    * Scala doesn't have polymorphic functions but has polymorphic methods
    *
    * scala methods accept type parameter list, and then a value parameter list, and then an implicit value parameter list
    */
  def identity[A](a: A): A = a
  // identity: A => (a: A) => A
  // there is no type for the type-name A

  def identity[A, B, C, D](a: A, b: B, c: C, d: D): A = ???
  // identity: [A, B, C, D] => (a: A, b: B, c: C, d: D) => A = ???

  /**
    * Function literals or lambdas in Scala cannot be polymorphic
    */
  val square: Int => Int =
    (x: Int) => x * x

  // val identity = ??? => A =
  //  (a: A) => a

  /**
    * A trick to workaround this is to create an object and exploit the apply method that,
    * being a method, supports parametric polymorphism
    */
  object identityPoly {
    def apply[A](a: A): A = a
  }

  identityPoly(1)
  identityPoly("foo")
  identityPoly(true)
}

object AlgebraicDataTypes {

  /**
    * Product types
    *
    * given the types A and B (the terms of the product) they compose types productwise (A x B). They are tuples of all the
    * possible combinations of an item from A and an item from B (a, b). The size is the size of A * the size of B
    *
    * in scala there are 2 idiomatic ways to represent product types:
    *
    * - case classes (named)
    * - tuples (unnamed)
    */
  final case class Person(name: String, age: Int)

  type Person2 = (String, Int)
  type Person3 = (String, Int, String, Float)

  /**
    * Sum types
    *
    * dual of product types. Given two types A and B (the terms of the sum), every element of the sum type is going
    * to be a value from A or a value from B and the size is size of A + size of B
    *
    * in scala there are two ways to represent them but they are not first class citizen of the language.
    *
    * - sealed trait (named) [NB: If the trait is not sealed it's not a sum type]
    * - either (unnamed)
    */
  sealed trait Fruit
  case object Apple   extends Fruit
  case object Banana  extends Fruit
  case object Mango   extends Fruit
  case object Grape   extends Fruit

  type Fruit2 = Either[Apple.type, Either[Banana.type, Either[Mango.type, Grape.type]]]


  /**
    * Example of ADT: Draft of GameWorld
    */
  sealed trait Item

  case class Player(
    nickname: String,
    inventory: List[Item],
    level: Int,
    position: (Int, Int)
  )

  sealed trait Cell
  case class Land() extends Cell
  case class Sea() extends Cell

  case class GameMap(
    world: Vector[Vector[Cell]]
  )

  case class GameWorld(
    player: Player,
    map: GameMap
  )
}

object KindsAndTypeConstructors {

  /**
    * Considering again the structure of a method's signature, the type parameters list is not just a list
    * of names, but is a list of names and kinds. In scala the syntax for describing the kinds is not consistent.
    * The kind * is represented differently from all the others.
    *
    * I the case of identity below the kind of A is *. If we could express it consistently it would be written
    *
    * def identity[A : *](a: A): A = ???
    *
    * Anyway in Scala any time there is nothing after the name of a type in the type parameters list
    * (like the identity below), a regular type of kind * has to be assumed
    */
  def identity[A](a: A): A = ???

  /**
    * If we define something like this
    *
    * def filter[F, A](xs: F[A]): F[A] = ???
    *
    * to use it like
    *
    * filter[List, Int](1 :: 2 :: 3 :: 4 :: Nil)
    *
    * It will not work. It doesn't make sense to apply A to as with that definition we have
    * set the kind of F to * (F : *). It is the same as writing
    *
    * val x = 2
    * x(2)
    *
    * at value level. What we have to do instead of
    *
    * def filter[F : *, A : *](xs: F[A]): F[A] = ???
    *
    * is
    *
    * def filter[F : * => *, A : *](xs: F[A]): F[A] = ???
    *
    * In Scala there is no such a syntax, but the kind annotation can be used to express kinds different from *.
    * In the example above using `F[_]` can be used for kinds * => * and omitting the annotation will
    * define the kind of regular types. See below
    */
  def filter[F[_], A](xs: F[A]): F[A] = ???

  // and the following use will compiles
  filter[List, Int](1 :: 2 :: 3 :: 4 :: Nil)

  /**
    * Example of kinds
    *
    * A : *
    * Option : * => *
    * List : * => *
    * String : *
    * Map : [*, *] => *
    * Tuple2 : [*, *] => *
    * Tuple4 : [*, *, *, *] => *
    * Either : [*, *] => *
    */

  trait StackLike[Stack[_]] {
    def empty[A]: Stack[A]
    def push[A](a: A, s: Stack[A]): Stack[A]
    def pop[A](s: Stack[A]): Option[(A, Stack[A])]
  }

  /**
    * Given the trait
    */
  trait Algorithm[Stack[Stack]] {
    def apply(implicit S: StackLike[Stack]): Stack[Int] = { S == S; ??? }
  }

  /**
    * The kind of Algorithm is
    *
    * Algorithm : (* => *) => *
    * (associated to the left)
    *
    *
    * Given the trait below
    */
  trait Module[Alg] {}

  /**
    * the following will not compile
    * type MyModule = Module[Algorithm]
    *
    * to make it work we need to change Module to
    */
  trait Module2[Alg[_[_]]] {}
  type MyModule = Module2[Algorithm]

  /**
    * Where the kind of Module2 is
    *
    * Module2 : ((* => *) => *) => *
    */
}

object TypeLambdas {

  /**
    * If we consider a function like
    */
  val plus: (Int, Int) => Int =
    (x, y) => x + y

  /**
    * sometimes it's easier to be able to partially apply it
    */
  val increment: Int => Int =
    plus(1, _)

  /**
    * Let's consider something like the below that allows to fold over
    * a structure
    */
  trait Foldable[F[_]] {
    def fold[Z, A](fa: F[A])(z: Z)(f: (Z, A) => Z): Z
  }

  val listFoldable = new Foldable[List] {
    def fold[Z, A](fa: List[A])(z: Z)(f: (Z, A) => Z): Z =
      fa.foldLeft(z)(f)
  }

  /**
    * if we wanted to implement a foldable for Map
    *
    * val mapFoldable = new Foldable[Map] { [...] }
    *
    * it wouldn't work as the kinds don't align
    *
    * F : * => *
    * Map : [*, *] => *
    *
    * to make it work I have to partially apply the kind. I could try
    *
    * def mapFoldable[K] = new Foldable[Map[K, _]] { [...] }
    *
    * But that doesn't work. A possible trick is to use an anonymous structural type
    *
    * ({ type Mpak[V] = Map[K, V] })#Mpak
    */
  def mapFoldable[K] = new Foldable[({ type Mpak[V] = Map[K, V] })#Mpak] {
    def fold[Z, A](fa: Map[K, A])(z: Z)(f: (Z, A) => Z): Z =
      fa.values.foldLeft(z)(f)
  }

  /**
    * It's very hard to read and error-prone. A possible solution is using a compiler plugin
    * called Kind Projector. With it the syntax becomes very elegant anc concise.
    * The above could be expressed
    */
  def mapFoldable2[K]: Foldable[Map[K, ?]] = new Foldable[Map[K, ?]] {
    def fold[Z, A](fa: Map[K, A])(z: Z)(f: (Z, A) => Z): Z =
      fa.values.foldLeft(z)(f)
  }

  /**
    * Another way would be using type aliases to explicitly partially apply the type
    */
  def mapFoldable3[K]{

    type MapK[V] = Map[K, V]

    new Foldable[MapK] {
      def fold[Z, A](fa: Map[K, A])(z: Z)(f: (Z, A) => Z): Z =
        fa.values.foldLeft(z)(f)
    }
  }
}

object PolymorphismAndTypeclasses {

  /**
    * considering a method with the signature below (fst) there is only a possible
    * way to implement it, and it's the way given. If we assume purity there's no
    * other way.
    */
  def fst[A, B](tuple: (A, B)): A = tuple._1

  trait Appendable[A] {
    def append(a: A, b: A): A
  }

  def foo[A](x: A)(implicit A: Appendable[A]): A = ???

  /**
    * If we try the same with foo instead, possible implementations could be
    *
    * A.append(x, x)
    * A.append(A.append(x, x), x)
    *
    * still a lot of possible ways but they are described by the type signature
    *
    * Polymorphism restricts the possible implementations, and even if is not
    * reducing to a single possible implementation still describes well what the class of
    * the implementations could do
    */

  def zip1[A](a: List[A], b: List[A]): List[(A, A)] = ???

  /**
    * The above can be still ambiguous. For instance we don't know if the items from the first list
    * go first or second in the result. Or even if this changes with the position.
    * With the following is impossible to invert the order in the reult tuples
    */
  def zip2[A, B](a: List[A], b: List[B]): List[(A, B)] = ???

  /**
    * There is still a problem because we don't know what to do with the extra items
    * if the lists are not the same size. A lot of details can be taken off. The steps
    * below demonstrates a possible way
    */
  def zip3[A, B, C](a: List[A], b: List[B], f: Either[B, (A, B)] => C): List[C] = ???

  def zip4[A, B, C](a: List[A], b: List[B], f: Either[B, Either[A, (A, B)]] => C)(zero: C, smash: (C, C) => C): C = ???

  def zip5[A, B, C : Monoid](a: List[A], b: List[B], f: A \&/ B): C = ???

  def zip6[F[_] : Apply, A, B, C : Monoid](a: F[A], b: F[B], f: A \&/ B): C = ???

  /**
    * Sometimes we need to know some structure to know how to implement something.
    * The purpose is to introduce the minimum amount of structure to write an implementation.
    * We don't want too introduce too much structured though as the space of the possible implementations
    * explodes otherwise. We can do it with type classes
    *
    * Below we would like to say that we can compare two `A`s but we cannot do it with that signature
    */
  def sort0[A](list: List[A]): List[A] = ???

  /**
    * Type classes are not intended as traits in object oriented. They are a different
    * usage of the `trait` construct
    */
  sealed trait Ordering
  case object LT extends Ordering
  case object GT extends Ordering
  case object ET extends Ordering

  /**
    * A Typeclass is a bundle of types and functions
    */
  trait Ord[A] {
    def compare(l: A, r: A): Ordering
  }

  /**
    * The instances of a Typeclass provide materialization of it for different types
    */
  val intOrd = new Ord[Int] {
    def compare(l: Int, r: Int): Ordering =
      if(l < r) LT
      else if (l > r) GT
      else ET
  }

  /**
    * This type class describes things that can be compared. Is the minimum structure we need
    * to know how to sort items from A.
    *
    * Now we can implement sort
    */
  def sort[A](list: List[A])(ord: Ord[A]): List[A] =
    list match {
      case Nil      => Nil
      case x :: xs  =>
        val (lessThan, notLessThan) = xs.partition(a => ord.compare(x, a) == LT)
        sort(lessThan)(ord) ++ (x :: Nil) ++ sort(notLessThan)(ord)
    }

  sort(1 :: 2 :: 3 :: Nil)(intOrd)

  /**
    * some syntactic help can here can come from implicits
    */
  implicit val intOrd2 = new Ord[Int] {
    def compare(l: Int, r: Int): Ordering =
      if(l < r) LT
      else if (l > r) GT
      else ET
  }

  def sort1[A : Ord](list: List[A]): List[A] =
    list match {
      case Nil      => Nil
      case x :: xs  =>
        val (lessThan, notLessThan) = xs.partition(a => implicitly[Ord[A]].compare(x, a) == LT)
        sort1(lessThan) ++ (x :: Nil) ++ sort1(notLessThan)
    }

  /**
    * using implicitly is ugly, it's better to use an helper.
    * Adding this apply to the companion object of the typeclass will allow a nicer syntax
    */
  object Ord {
    def apply[A](implicit inst: Ord[A]): Ord[A] = inst
  }

  /**
    * So the above becomes
    */
  def sort2[A : Ord](list: List[A]): List[A] =
    list match {
      case Nil      => Nil
      case x :: xs  =>
        val (lessThan, notLessThan) = xs.partition(a => Ord[A].compare(x, a) == LT)
        sort2(lessThan) ++ (x :: Nil) ++ sort2(notLessThan)
    }

  /**
    * Considering the typeclass structure we will probably will have to decide where to put the instance.
    *
    * A good set of rules is:
    *
    * - If we are defining an instance of a type that we don't control (such as for Int) -> we should put the instance
    * in the companion object of the type class. Scalac will find it in scope (called implicit scope)
    *
    * - If we are defining our own type (like Room below) -> we should put the instance in the companion object
    * of the type we define and control.
    *
    * Anyway, is important not to have orphan instances at all, so not to have more than one possible instance of
    * the typeclass for a specific type, that's selected through import. The problem here is that in case
    * of orphan instances, changing an import we can brake a program and the type system would not identify
    * the problem.
    */
  case class Room(name: String, number: Int)
  object Room {
    implicit val intOrd2 = new Ord[Room] {
      def compare(l: Room, r: Room): Ordering =
        if(l.name < r.name) LT
        else if (l.name > r.name) GT
        else {
          if(l.number < r.number) LT
          else if (l.number > l.number) GT
          else ET
        }
    }
  }

  /**
    * If we really need to have more than one instance for the same type (we shouldn't typeclasses should be coherent),
    * we should use newtypes, so that the user can select the which instance is summoning and doesn't delegate
    * this to the Scala implicit resolution. This way even changing an import the behavior of the program will not change.
    */
  class ReverseRoom(val room: Room) extends AnyVal
  object ReverseRoom {
    // Instances for this new type go here
  }

  /**
    * Sometimes we might want to have an object oriented style syntax (call the method using the dot notation
    * from the type instance). In this case there's a pattern to create that
    */
  implicit class OrdSyntax[A](l: A) {
    def =?=(r: A)(implicit O: Ord[A]): Ordering = O.compare(l, r)
  }

  /**
    * So I can write the sort using the syntax (x =?= a) == LT
    */
  def sort3[A : Ord](list: List[A]): List[A] =
    list match {
      case Nil      => Nil
      case x :: xs  =>
        val (lessThan, notLessThan) = xs.partition(a => (x =?= a) == LT)
        sort3(lessThan) ++ (x :: Nil) ++ sort3(notLessThan)
    }

  /**
    * The reason why typeclasses are more expressive than subtyping is that you can define instances
    * (so functionality, behaviors) for types that you don't control
    *
    * In cases when to define an instance we need to summon anohter instance (the instance depends on another one)
    * we can do that like below (see A : Ord)
    */
  implicit def ordList[A : Ord] = new Ord[List[A]] {
    def compare(l: List[A], r: List[A]): Ordering =
      (l, r) match {
        case (Nil, Nil) => ET
        case (Nil, _)   => LT
        case (_, Nil)   => GT
        case (x :: xs, y :: ys) =>
          x =?= y match {
            case LT => LT
            case GT => GT
            case ET => compare(xs, ys)
          }
      }
  }

  (1 :: 2 :: 3 :: 4 :: Nil) =?= (5 :: 6 :: 7 :: 8 :: Nil)

  /**
    * Typeclasses usually come with laws. They define what's needed to have valid instances of a typeclass.
    * The laws constraint the behavior that can be expected by the typeclass. If an instance doesn't satisfy the laws
    * we cannot expect for that instance to have the behavior that the typeclass describes.
    *
    * Let's consider examples where the laws are in the comments
    */
  trait Semigroup[A] {
    // associativity law: append(append(a, b), c) == append(a, append(b, c))
    def append(a1: A, a2: A): A
  }

  trait Monoid[A] extends Semigroup[A] {
    // identity law:
    //   append(zero, a) == a
    //   append(a, zero) == a
    def zero: A
  }
  object Monoid {
    def apply[A](implicit I: Monoid[A]): Monoid[A] = I
  }

  /**
    * without laws we cannot completely define a typeclass' behavior. With the traits above, we could define
    * all the operations for a type, but if the associativity or the identity are not satisfied we couldn't call
    * them semigroup or monoid instances
    */

  implicit val intMonoid = new Monoid[Int] {
    def zero: Int = 0
    def append(a1: Int, a2: Int): Int = a1 + a2
  }

  /**
    * Now if we want to create another monoid we don't want to create another instance for the same type.
    * As said earlier we will use newtypes
    */
  class MultInt(val value: Int) extends AnyVal

  implicit val multIntMonoid = new Monoid[MultInt] {
    def zero: MultInt = new MultInt(1)
    def append(a1: MultInt, a2: MultInt): MultInt =
      new MultInt(a1.value * a2.value)
  }

  def reduce[A: Monoid](list: List[A]): A =
    list match {
      case Nil      => Monoid[A].zero
      case x :: xs  => Monoid[A].append(x, reduce(xs))
    }

  /**
    * This adds a bit of verbosity but the types are sound in the sense that
    * it will allow us to chose the monoid and will not delegate it to the implicit resolution
    *
    * A possible way to use it is below.
    */
  reduce(1 :: 2 :: 3 :: Nil) // Summons Int Monoid
  reduce(
    (1 :: 2 :: 3 :: Nil).map(new MultInt(_)) // Summons MultInt Monoid
  )
}

object TypeclassExercise {

  import AlgebraicDataTypes._

  case class FruitBlend(l: List[Fruit])

  trait Blender[A, B] {
    // blend(a, blend(b, c)) == blend(blend(a, b), c)
    // blend(a, b) == blend(b, a)
    def blend(a: A, b: B): FruitBlend
  }

  object Blender {
    def apply[A <: Fruit, B <: Fruit](implicit A: Blender[A, B]): Blender[A, B] = A

    implicit def appleBlend[B <: Fruit]: Blender[Apple.type, B] =
      new Blender[Apple.type , B] {
        def blend(a: Apple.type, b: B): FruitBlend = FruitBlend(a :: b :: Nil)
      }
  }

  implicit class BlenderSyntax[A <: Fruit](a: A) {
    def blend[B <: Fruit](b: B)(implicit BL: Blender[A, B]) = BL.blend(a, b)
  }

  /**
    * Another example
    */
  trait Navigatable[A] {
    def goSouth(a: A): Option[A]
    def goNorth(a: A): Option[A]
    def goEast(a: A): Option[A]
    def goWest(a: A): Option[A]

    // laws:
    //   goSouth(a0).flatMap(a => gotNorth(a) == Some(a)).orElse(true)
    //   ... and so on
  }
}

object Functor {

  case class Identity[A](run: A)
  case class Empty[A]()

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

  object Functor {

    implicit val listFunctor = new Functor[List] {
      def fmap[A, B](f: A => B): List[A] => List[B] = _ map f
    }

    implicit def funcFunction[X] = {

      type FunctionF[B] = X => B

      new Functor[FunctionF] {
        def fmap[A, B](f: A => B): (X => A) => (X => B) =
          ff => f compose ff
      }
    }

    implicit val identityFunctor = new Functor[Identity] {
      def fmap[A, B](f: A => B): Identity[A] => Identity[B] =
        ff => Identity(f(ff.run))
    }
  }

  case class StreamT[F[_], A](run: F[(A, Option[StreamT[F, A]])])
}

object NaturalTransformation {

  trait NaturalTransformation[F[_], G[_]] {
    def apply[A](fa: F[A]): G[A]
  }

  type ~>[F[_], G[_]] = NaturalTransformation[F, G]

  object NaturalTransformation {

    def apply[F[_], G[_]](implicit INST: F ~> G): F ~> G = INST

    implicit val listToOption: List ~> Option = new NaturalTransformation[List, Option] {
      def apply[A](fa: List[A]): Option[A] = fa.headOption
    }

    implicit val optionToList: Option ~> List = new NaturalTransformation[Option, List] {
      def apply[A](fa: Option[A]): List[A] =
        fa.fold(Nil: List[A])(List(_))
    }
  }
}

object Applicative {

  import Functor._

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

    // F[A => A] => F[A] => F[B]
    def ap[A, B](fab: F[A => B]): F[A] => F[B]

    // ap in term of zip
    def ap1[A, B](fab: F[A => B]): F[A] => F[B] =
      fa => fmap((t: (A => B, A)) => t._1(t._2))(zip(fab, fa))

    def zip[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
      ap(fmap((a: A) => (b: B) => (a, b))(fa))(fb)
  }

  object Apply {

    implicit val identityApply = new Apply[Identity] {

      def ap[A, B](fab: Identity[A => B]): Identity[A] => Identity[B] =
        fa => Identity(fab.run(fa.run))

      def fmap[A, B](f: A => B): Identity[A] => Identity[B] =
        ff => Identity(f(ff.run))
    }

    implicit val optionApply = new Apply[Option] {
      def ap[A, B](fab: Option[A => B]): Option[A] => Option[B] =
        fa => (fab, fa) match {
          case (Some(ab), Some(a))  => Some(ab(a))
          case _                    => None
        }

      def fmap[A, B](f: A => B): Option[A] => Option[B] = _ map f
    }
  }

  trait Applicative[F[_]] extends Apply[F] {
    def point[A](a: A): F[A]
  }

  trait Monad[F[_]] extends Applicative[F] {
    def join[A](ffa: F[F[A]]): F[A]

    def bind[A, B](fa: F[A])(f: A => F[B]): F[B] =
      join(fmap(f)(fa))
  }
}

object examplesMonadTransformers {

  lazy val result1: Option[Int] =
    for {
      a <- Option(1)
      b <- if (a == 2) result1 else Option(2)
    } yield a + b

  /**
    * this will be translated to
    */
  val result2: Option[Int] =
    Option(1).flatMap(a =>
      Option(2).map(b =>
        a + b
      )
    )

  /**
    * We have to respect the functor inside the for. If we want to do other operations we can use the
    * variable definition
    */
  val result3: Option[Int] =
    for {
      a <- Option(1)
      b =  if (a == 2) 4 else 5
    } yield a + b

  /**
    * If we write something like
    *
    * val result4: Option[Int] =
    *   for {
    *     a <- Option(1)
    *     b =  List(1, 2, 3)
    *   } yield a + b
    *
    * it won't compile, as we're trying to join different monad and that's not allowed by the types (see map).
    * So what if we need to handle something like the below
    */

  def f[A]: Future[Option[List[A]]] = ???

  /**
    * To work with that would require a lot of nested map and flatMap. That's because Monads don't compose
    * as they have a lot of structure (so they are powerful) and they lose flexibility. 
    * If compared to Functors for instance, they can describe much more powerful behavior than simple mapping but
    * they are more constrained in the structure and lose the possibility of composition (that instead Functor has).
    *
    * The way to stack Monads as they don't compose is monad transformers
    */
  import Functor._

  final case class OptionT[F[_], A](run: F[Option[A]]) {

    def map[B](f: A => B)(implicit F: Functor[F]): OptionT[F, B] =
      OptionT(
        F.fmap((v: Option[A]) => v.map(a => f(a)))(run)
      )

    def flatMap[B](f: A => OptionT[F, B])(implicit F: Monad[F]): OptionT[F, B] =
      OptionT(
        F.bind(run)((v: Option[A]) => v match {
          case None => F.point(Option.empty[B])
          case Some(a) => f(a).run
        })
      )
  }

  object OptionT {
    def point[F[_], A](a: A)(implicit F: Monad[F]): OptionT[F, A] =
      OptionT(F.point(Some(a)))
  }
}