Upgrade to Pro — share decks privately, control downloads, hide ads and more …

The Essence of Functional Structures - flatMap(...

The Essence of Functional Structures - flatMap(Oslo) 2017

Functional programming (FP) is about compositionality and equational reasoning. Due to these fundamental properties, FP is becoming one of the mainstream programming paradigms.
However, on the path of learning FP paradigm, we often get stuck with different abstractions such as Functor, Applicative, Monad and so on. That brings to this talk on the essence of functional structures. In this talk, we introduce concepts necessary to master the mostly-used functional structures, outline their core essences, and discuss intuitions on how to apply them in solving problems in a purely functional manner.

From scratch, we will construct the type classes to represent these structures in Scala. Starting with basic constructs such as Monoid, we will continue exploring structures such as Functor, Applicative, Monad, Foldable and finally, Traversable. Alongside, from the practical point of view, we will dive into the essence of these structures in encoding pure functional programs that are robust, comprehensible and correct-by-construction.

As an audience, I would get a comprehensive overview of several functional abstractions, learn about their core strengths and limitations and see how to use them in solving problems. No prior knowledge of advanced functional programming is assumed in this talk.

adilakhter

May 02, 2017
Tweet

More Decks by adilakhter

Other Decks in Programming

Transcript

  1. About Me Adil Akhter Lead Engineer at ING Amsterdam, The

    Netherlands http://coyoneda.xyz adilakhter
  2. val f: String => Int = s => s.length f:

    String 㱺 Int Domain Codomain C D E CD DE           
  3. val x = 1 // ← Value val add =

    (x: Int) => x + 1 // ← Functions are also values
  4. val addTwoInts: Int => (Int => Int) = x =>

    y => x + y // Returns a Function val addWithOne: Int => Int = addTwoInts (1) Return Type: Int ⇒ Int Partially applied
  5. val f: String => String = // ← normalizes string

    _.replaceAll("ß", "ss").replaceAll("[^a-zA-Z0-9-]+", "-") val g: String => Boolean = s => s == s.reverse // ← checks if `s` is palindrome
  6. val f: String => String = // ← normalizes string

    _.replaceAll("ß", "ss").replaceAll("[^a-zA-Z0-9-]+", "-") val g: String => Boolean = s => s == s.reverse // ← checks if `s` is palindrome val h = f >>> g h("ma;am") shouldEqual true f A B g B C h A C
  7. val f: String => String = // ← normalizes string

    _.replaceAll("ß", "ss").replaceAll("[^a-zA-Z0-9-]+", "-") val g: String => Boolean = s => s == s.reverse // ← checks if `s` is palindrome val h: (String) => (String, Boolean) = f &&& g h("ma;am") should be (("ma-am",true)) f (C, D) g A Combine Combinator
  8. trait JsonFormatter[A] { def toJson(a: A): String } case class

    Product(productId: String, description: String, price: Double) implicit val productFormatter = new JsonFormatter[Product] { def toJson(a: Product): String = s"""{ "productId": "${a.productId}", "description": "${a.description}", "price": ${a.price} }""" } val aProduct = Product("1", "Nike", 121.23) implicitly[JsonFormatter[Product]].toJson(aProduct) //{ "productId": "1", "description": "Nike", "price": 121.23 }
  9. case class Coordinate(longitude: Double, latitude: Double) def readCoordinate(): Coordinate =

    { println("Latitude:") val longitude = StdIn.readLine().toDouble println("Longitude:") val latitude = StdIn.readLine().toDouble Coordinate(longitude, latitude) }
  10. case class Coordinate(longitude: Double, latitude: Double) def readCoordinate(): Coordinate =

    { println("Latitude:") val longitude = StdIn.readLine().toDouble println("Longitude:") val latitude = StdIn.readLine().toDouble Coordinate(longitude, latitude) }
  11. case class Coordinate(longitude: Double, latitude: Double) def readCoordinate(): Coordinate =

    { println("Latitude:") val longitude = StdIn.readLine().toDouble ↩︎ println("Longitude:") val latitude = StdIn.readLine().toDouble ↩︎ Coordinate(longitude, latitude) }
  12. @ def maxValue(xs: List[Int]): String = s"Maximum value is ${xs.max}"

    @ val ints = List.empty[Int] @ maxValue(ints)
  13. @ def maxValue(xs: List[Int]): String = s"Maximum value is ${xs.max}"

    @ val ints = List.empty[Int] @ maxValue(ints) ↩︎ java.lang.UnsupportedOperationException: empty.max scala.collection.TraversableOnce$class.max(TraversableOnce.scala:229) scala.collection.AbstractTraversable.max(Traversable.scala:104) ammonite.session.cmd3$.<init>(cmd3.scala:1) ammonite.session.cmd3$.<clinit>(cmd3.scala:-1)
  14. @ def divideOneBy(y: Int): Double = 1/y @ divideOneBy(0) ↩︎

    java.lang.ArithmeticException: / by zero $sess.cmd2$.divideOneBy(cmd2.sc:2) $sess.cmd3$.<init>(cmd3.sc:1) $sess.cmd3$.<clinit>(cmd3.sc:-1)
  15. def map[B](f: A => B): Option[B] // map for Option[A]

    def map[B](f: A => B): List[B] // map for List[A] def map[B](f: A => B): Task[B] // map for Task[A]
  16. Identity @ def identity[A](x: A): A = x @ Option(1).map(identity)

    shouldEqual Option(1) @ None.map(identity) shouldEqual None
  17. Composition //normalizes string @ val f: String => String =

    _.replaceAll("ß", "ss").replaceAll("[^a-zA-Z0-9-]+", "-") //checks if a string is a palindrome @ val g: String => Boolean = s => s == s.reverse // compose f and g with `andThen` @ val h: String => Boolean = f >>> g // >>> == andThen
  18. Composition @ val lst = List("madam", "ßßß") // first `map`

    with `f` and then, `g` @ val l1 = lst.map(f).map(g) // map with h @ val l2 = lst.map(h) // ← h = f andThen g // l1 === l2 @ l1 should contain theSameElementsAs l2
  19. case class Container[A](unwrap: A) { override def equals(obj: scala.Any): Boolean

    = true } @ val f = (i: Int) ⇒ Container(i) @ val g = (c: Container[Int]) ⇒ c.unwrap @ val aSet = Set(1,2,3) @ aSet.map(f).map(g) // Set(1) shouldEqual aSet.map(f andThen g) // Set(1,2,3 )
  20. sealed trait Tree[A] case class Leaf[A](a: A) extends Tree[A] case

    class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A] val binaryTree = Node( Leaf("scala"), Node( Leaf("eXch;nge"), Leaf("ßß")))
  21. sealed trait Tree[A] case class Leaf[A](a: A) extends Tree[A] case

    class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A] implicit val TreeFunctor = new Functor[Tree] { def map[A, B](fa: Tree[A])(f: (A) => B): Tree[B] = fa match { case Leaf(a: A) => Leaf(f(a)) case Node(left, right) => Node(map(left)(f), map(right)(f)) } }
  22. @ val f: String => String = _.replaceAll("ß", "ss").replaceAll("[^a-zA-Z0-9-]+", "-")

    @ val transformedTree: Tree[String] = Functor[Tree].map(binaryTree)(f) @ transformedTree shouldEqual Node( Leaf("scala"), Node( Leaf("eXch-nge"), Leaf("ssss"))) // ← a tree with normalized strings
  23. @ val f: String => String = _.replaceAll("ß", "ss").replaceAll("[^a-zA-Z0-9-]+", "-")

    @ val transformedTree: Tree[String] = Functor[Tree].map(binaryTree)(f) @ transformedTree shouldEqual Node( Leaf("scala"), Node( Leaf("eXch-nge"), Leaf("ssss"))) // ← a tree with normalized strings
  24. @ val f: String => String = _.replaceAll("ß", "ss").replaceAll("[^a-zA-Z0-9-]+", "-")

    @ val transformedTree: Tree[String] = Functor[Tree].map(binaryTree)(f) @ transformedTree shouldEqual Node( Leaf("scala"), Node( Leaf("eXch-nge"), Leaf("ssss"))) // ← a tree with normalized strings
  25. Profit Time! def toJson [F[_]: Functor, A:JsonFormatter](fa: F[A]): F[String] =

    { val F = implicitly[Functor[F]] F.map(fa)(JsonFormatter[A].toJson) } @ val x: List[String] = toJson(List(Product("1", "Nike", 121.23), Product("2", "Addidas", 541))) @ val y: Option[String] = toJson(Option(Product("1", "Nike", 121.23))) @ val t: BinaryTree[Product] = Node(Leaf(Product("1", "Nike", 121.23)), Leaf(Product("2", "Addidas", 541))) @ val z: Tree[String] = toJson(t)
  26. @ val x = 1.some @ val y = 2.some

    @ val add = (x: Int) ⇒ (y:Int) ⇒ x + y Recap Functor allows mapping a function with one argument: f : A => B over each element of the structure F[_] ! Can we use Functor to add x and y ?
  27. def map [A, B](f : A => B): F[A] =>

    F[B] def map2[A, B, C](f : A => B => C): F[A] => F[B] => F[C] def map3[A, B, C, D](f : A => B => C => D): F[A] => F[B] => F[C] => F[D] . . . Can we somehow generalise to allow functions with any number of arguments?
  28. trait Applicative[F[_]] extends Functor[F] { def point[A](a: => A): F[A]

    // aka pure def ap[A, B](fa: => F[A])(f: => F[A => B]): F[B] //aka `apply`, <*> }
  29. @ 1.point[List] shouldEqual List(1) @ "scala".point[Option] shouldEqual Some("scala") @ val

    add: Int ⇒ Int ⇒ Int =>Int = x ⇒ y ⇒ z ⇒ x + y + z @ add.point[Option] shouldEqual Some(add) A A point
  30. implicit val OptionApplicative = new Applicative[Option] { def point[A](a: =>

    A): Option[A] = Some(a) def ap[A, B](fa: => Option[A])(f: => Option[A => B]): Option[B] = ??? }
  31. implicit val OptionApplicative = new Applicative[Option] { def point[A](a: =>

    A): Option[A] = Some(a) def ap[A, B](fa: => Option[A])(f: => Option[A => B]): Option[B] = f match { case None ⇒ None case Some(f) ⇒ ??? } }
  32. implicit val OptionApplicative = new Applicative[Option] { def point[A](a: =>

    A): Option[A] = Some(a) def ap[A, B](fa: => Option[A])(f: => Option[A => B]): Option[B] = f match { case None ⇒ None case Some(f) ⇒ fa match { case None ⇒ None case Some(a) ⇒ ??? } } }
  33. implicit val OptionApplicative = new Applicative[Option] { def point[A](a: =>

    A): Option[A] = Some(a) def ap[A, B](fa: => Option[A])(f: => Option[A => B]): Option[B] = f match { case None ⇒ None case Some(f) ⇒ fa match { case None ⇒ None case Some(a) ⇒ Some(f(a)) } } }
  34. implicit val OptionApplicative = new Applicative[Option] { def point[A](a: =>

    A): Option[A] = Some(a) def ap[A, B](fa: => Option[A])(f: => Option[A => B]): Option[B] = f match { case None ⇒ None case Some(f) ⇒ fa match { case None ⇒ None case Some(a) ⇒ Some(f(a)) } } } We can use Functor of Option, right?
  35. implicit val OptionApplicative = new Applicative[Option] { def point[A](a: =>

    A): Option[A] = Some(a) def ap[A, B](fa: => Option[A])(f: => Option[A => B]): Option[B] = f match { case None ⇒ None case Some(f) ⇒ fa.map(f) } }
  36. implicit val OptionApplicative = new Applicative[Option] { def point[A](a: =>

    A): Option[A] = Some(a) def ap[A, B](fa: => Option[A])(f: => Option[A => B]): Option[B] = f match { case None ⇒ None case Some(f) ⇒ fa.map(f) } }
  37. case class ApplicativeOps[F[_]: Applicative,A] (self: F[A]) { val F =

    implicitly[Applicative[F]] def <*>[B](f: F[A => B]): F[B] = F.app(self)(f) } implicit def ToApplicativeOps[F[_]: Applicative, A](v: F[A]): ApplicativeOps[F, A]= ApplicativeOps(v)
  38. case class ApplicativeOps[F[_]: Applicative,A] (self: F[A]) { val F =

    implicitly[Applicative[F]] def <*>[B](f: F[A => B]): F[B] = F.app(self)(f) } implicit def ToApplicativeOps[F[_]: Applicative, A](v: F[A]): ApplicativeOps[F, A]= ApplicativeOps(v)
  39. @ val xOpt = 1.some @ val yOpt = 2.some

    @ val zOpt = 3.some @ val add: Int ⇒ Int ⇒ Int => Int = x ⇒ y ⇒ z ⇒ x + y + z @ val addOpt = add.point[Option] // Option[(Int) => (Int) => (Int) => Int] @ val result = zOpt <*> (yOpt <*> (xOpt <*> addOpt)) // Some(6)
  40. @ val xOpt = 1.some @ val yOpt = 2.some

    @ val zOpt = 3.some @ val add: Int ⇒ Int ⇒ Int => Int = x ⇒ y ⇒ z ⇒ x + y + z @ val addOpt = add.point[Option] // Option[(Int) => (Int) => (Int) => Int] @ val result = zOpt <*> (yOpt <*> (xOpt <*> addOpt)) // Some(6)
  41. @ val addOpt: Option[Int => Int => Int => Int]

    = add.pure[Option] @ val addX : Option[Int => Int => Int] = xOpt <*> addOpt @ val addY : Option[Int => Int] = yOpt <*> addX @ val addZ : Option[Int] = zOpt <*> addY @ val result: Option[Int] = addZ
  42. @ val addOpt: Option[Int => Int => Int => Int]

    = add.pure[Option] @ val addX : Option[Int => Int => Int] = xOpt <*> addOpt @ val addY : Option[Int => Int] = yOpt <*> addX @ val addZ : Option[Int] = zOpt <*> addY @ val result: Option[Int] = addZ @ val result = zOpt <*> (yOpt <*> (xOpt <*> addOpt)) // Some(6)
  43. case class Product(productId: String, description: String, price: Double) def itemitemRecommendations(aProduct:

    Product): Task[List[Product]] def visualRecommendations(aProduct: Product): Task[List[Product]] def allRcommendations(aProduct: Product): Task[List[Product]] = (itemitemRecommendations(aProduct) |@| visualRecommendations(aProduct)) {_ ++ _} Independent Computations Pure Function
  44. trait Monad[F[_]] extends Applicative[F] { def bind[A, B](fa: F[A]) (f:

    A ⇒ F[B]): F[B] } Extends F[A] with f that depends on the result of F[A] A bind B f: A 㱺 B
  45. trait Monad[F[_]] extends Applicative[F] { def bind[A, B](fa: F[A]) (f:

    A ⇒ F[B]): F[B] } also known as ‘FlatMap‘
  46. A bind B B trait Monad[F[_]] extends Applicative[F] { def

    bind[A, B](fa: F[A]) (f: A ⇒ F[B]): F[B] } also known as ‘FlatMap‘
  47. case class Product(productId: String, description: String, price: Double) def allRecommendations(aProduct:

    Product): Task[List[Product]] // gets recommendations def product(id: String): Task[Product] // gets product from Product Service def recommendationsById(id: String): Task[List[Product]] = ???
  48. case class Product(productId: String, description: String, price: Double) def allRecommendations(aProduct:

    Product): Task[List[Product]] // gets recommendations def product(id: String): Task[Product] // gets product from Product Service def recommendationsById(id: String): Task[List[Product]] = for { p <- product("123123") recs <- allRecommendations(p) } yield recs Sequencing dependent computations
  49. case class Id[A](value: A) implicit val identityMonad = new Monad[Id]

    { def point[A](a: => A): Id[A] = Id(a) def bind[A, B](fa: Id[A])(f: (A) => Id[B]): Id[B] = f(fa.value) }
  50. case class Id[A](value: A) implicit val identityMonad = new Monad[Id]

    { def point[A](a: => A): Id[A] = Id(a) def bind[A, B](fa: Id[A])(f: (A) => Id[B]): Id[B] = f(fa.value) }
  51. @ val x: Id[Int] = Id(1) @ val y: Id[Boolean]

    = x.flatMap(i => Id(i%2 == 0)) @ for { x ← Id(1) y ← Id(x % 2 == 0) } yield y
  52. def readCoordinate(): Coordinate = { println("Latitude:") val longitude = StdIn.readLine().toDouble

    println("Longitude:") val latitude = StdIn.readLine().toDouble Coordinate(longitude, latitude) } Recall
  53. final case class IO[A](unsafePerformIO: () => A) def readLine2: IO[String]

    = IO(() => readLine()) def println2(s: String): IO[Unit] = IO(() => println(s))
  54. final case class IO[A](unsafePerformIO: () => A) def readLine2: IO[String]

    = IO(() => readLine()) def println2(s: String): IO[Unit] = IO(() => println(s)) def io[A](computation: =>A): IO[A] = IO(() => computation)
  55. final case class IO[A](unsafePerformIO: () => A) implicit val IOMonad:

    Monad[IO] = new Monad[IO] { def point[A](a: => A): IO[A] = IO(() => a) def bind[A, B](fa: IO[A])(f: (A) => IO[B]): IO[B] = IO(() => f(fa.unsafePerformIO()).unsafePerformIO()) }
  56. final case class IO[A](unsafePerformIO: () => A) implicit val IOMonad:

    Monad[IO] = new Monad[IO] { def point[A](a: => A): IO[A] = IO(() => a) def bind[A, B](fa: IO[A])(f: (A) => IO[B]): IO[B] = IO(() => f(fa.unsafePerformIO()).unsafePerformIO()) }
  57. final case class IO[A](unsafePerformIO: () => A) implicit val IOMonad:

    Monad[IO] = new Monad[IO] { def point[A](a: => A): IO[A] = IO(() => a) def bind[A, B](fa: IO[A])(f: (A) => IO[B]): IO[B] = IO(() => f(fa.unsafePerformIO()).unsafePerformIO()) } A
  58. final case class IO[A](unsafePerformIO: () => A) implicit val IOMonad:

    Monad[IO] = new Monad[IO] { def point[A](a: => A): IO[A] = IO(() => a) def bind[A, B](fa: IO[A])(f: (A) => IO[B]): IO[B] = IO(() => f(fa.unsafePerformIO()).unsafePerformIO()) } IO[B]
  59. final case class IO[A](unsafePerformIO: () => A) implicit val IOMonad:

    Monad[IO] = new Monad[IO] { def point[A](a: => A): IO[A] = IO(() => a) def bind[A, B](fa: IO[A])(f: (A) => IO[B]): IO[B] = IO(() => f(fa.unsafePerformIO()).unsafePerformIO()) } B
  60. final case class IO[A](unsafePerformIO: () => A) implicit val IOMonad:

    Monad[IO] = new Monad[IO] { def point[A](a: => A): IO[A] = IO(() => a) def bind[A, B](fa: IO[A])(f: (A) => IO[B]): IO[B] = IO(() => f(fa.unsafePerformIO()).unsafePerformIO()) } IO[B]
  61. @ val coordinateStringIO: IO[(String, String)] = for { _ ←

    println2("Latitude:") x ← readLine2 _ ← println2("Longitude:") y ← readLine2 } yield (x, y)
  62. @ val result: (String, String) = coordinateStringIO.unsafePerformIO() ↩︎ > Longitude:

    37.773972 ↩︎ > Latitude: -122.431297 ↩︎ // result = (37.773972,-122.431297)
  63. @ val coordinateIO: IO[Option[Coordinate]] = for { _ ← println2("Latitude:")

    x ← readLine2 _ ← println2("Longitude:") y ← readLine2 latitude <- io(Try(x.toDouble).toOption) longitude <- io(Try(y.toDouble).toOption) c <- io((latitude |@| longitude){Coordinate}) } yield c
  64. @ val coordinateIO: IO[Option[Coordinate]] = for { _ ← println2("Latitude:")

    x ← readLine2 _ ← println2("Longitude:") y ← readLine2 latitude <- io(Try(x.toDouble).toOption) longitude <- io(Try(y.toDouble).toOption) c <- io((latitude |@| longitude){Coordinate}) } yield c
  65. @ val coordinate: Option[Coordinate] = coordinateIO.unsafePerformIO() > Longitude: 37.773972 ↩︎

    > Latitude: -122.431297 ↩︎ // coordinate = Some(Coordinate(37.773972,-122.431297))
  66. Applicative Functor Monad map app bind f: A ⇒ F[B]

    f: A ⇒ B f: A1 ⇒ A2 ⇒ … ⇒ An
  67. trait Semigroup[A] { def append(a1: A, a2: ⇒ A): A

    } trait Monoid[A] extends Semigroup[A] { def zero: A }
  68. def optionMonoid[A](implicit m: Monoid[A]) = new Monoid[Option[A]]{ def zero: Option[A]

    = None def append(f1: Option[A], f2: ⇒ Option[A]): Option[A] = f1 match { case None ⇒ None case Some(a) ⇒ f2 match { case None ⇒ None case Some(b) ⇒ Option(m.append(a, b)) } }
  69. Profit Time! def reduce[A](list: List[A]) (implicit m: Monoid[A]): A =

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

    list match { case Nil => m.zero case x :: xs => m.append(x, reduce(xs)) } @ reduce(List(1,2,3)) shouldEqual 6 @ reduce(List("a","b","c")) shouldEqual "abc" @ reduce(List(Option(1), Option(2), Option(3))) shouldEqual Option(6)
  71. def reduce[F[_], A](fa: F[A]) (implicit F: Foldable[F], m: Monoid[A]): A

    = fa.foldMap(identity) // == fa.fold def reduce[A](list: List[A]) (implicit m: Monoid[A]): A = list match { case Nil => m.zero case x :: xs => m.append(x, reduce(xs)) } Profit Time!
  72. def reduce[F[_], A](fa: F[A]) (implicit F: Foldable[F], m: Monoid[A]): A

    = fa.foldMap(identity) @ reduce(List(Option(1), Option(2), Option(3))) shouldEqual Option(6) @ reduce(Node(Leaf("a"), Node(Leaf("b"), Leaf("c")))) shouldEqual "abc"
  73. trait Traverse[F[_]] extends Functor[F] with Foldable[F]{ def traverse[G[_]: Applicative, A,

    B] (fa: F[A])(f: A => G[B]): G[F[B]] def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] }
  74. trait Traverse[F[_]] extends Functor[F] with Foldable[F]{ def traverse[G[_]: Applicative, A,

    B] (fa: F[A])(f: A => G[B]): G[F[B]] def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] } Effectful Function
  75. trait Traverse[F[_]] extends Functor[F] with Foldable[F]{ def traverse[G[_]: Applicative, A,

    B] (fa: F[A])(f: A => G[B]): G[F[B]] def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] } Applicative Machinery for managing any possibility of Failure.
  76. sealed trait Tree[A] case class Leaf[A](a: A) extends Tree[A] case

    class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A] def leaf[A] = (n: A) => Leaf(n): Tree[A] def node[A] = (l: Tree[A]) => (r: Tree[A]) => Node(l, r): Tree[A] Creates an instance of Leaf. Creates an instance of Node with left and right Node.
  77. implicit val TreeTraverse = new Traverse[Tree] { def traverse[G[_], A,

    B](fa: Tree[A])(f: A => G[B])(implicit G: Applicative[G]): G[Tree[B]] = fa match { case Leaf(a) ⇒ f(a) <*> G.point(leaf[B]) case Node(l, r) ⇒ traverse(r)(f) <*> (traverse(l)(f) <*> G.point(node[B]) } }
  78. implicit val TreeTraverse = new Traverse[Tree] { def traverse[G[_], A,

    B](fa: Tree[A])(f: A => G[B])(implicit G: Applicative[G]): G[Tree[B]] = fa match { case Leaf(a) ⇒ f(a) <*> G.point(leaf[B]) // ← constructs G[Tree[B]] case Node(l, r) ⇒ traverse(r)(f) <*> (traverse(l)(f) <*> G.point(node[B]) } }
  79. implicit val TreeTraverse = new Traverse[Tree] { def traverse[G[_], A,

    B](fa: Tree[A])(f: A => G[B])(implicit G: Applicative[G]): G[Tree[B]] = fa match { case Leaf(a) ⇒ f(a) <*> G.point(leaf[B]) // ← constructs G[Tree[B]] case Node(l, r) ⇒ traverse(r)(f) <*> (traverse(l)(f) <*> G.point(node[B]) } } G[B]
  80. implicit val TreeTraverse = new Traverse[Tree] { def traverse[G[_], A,

    B](fa: Tree[A])(f: A => G[B])(implicit G: Applicative[G]): G[Tree[B]] = fa match { case Leaf(a) ⇒ f(a) <*> G.point(leaf[B]) // ← constructs G[Tree[B]] case Node(l, r) ⇒ traverse(r)(f) <*> (traverse(l)(f) <*> G.point(node[B]) } } G[B] G[B ⇒ Tree[B]]
  81. implicit val TreeTraverse = new Traverse[Tree] { def traverse[G[_], A,

    B](fa: Tree[A])(f: A => G[B])(implicit G: Applicative[G]): G[Tree[B]] = fa match { case Leaf(a) ⇒ f(a) <*> G.point(leaf[B]) // ← constructs G[Tree[B]] case Node(l, r) ⇒ traverse(r)(f) <*> (traverse(l)(f) <*> G.point(node[B]) } } G[B] G[B ⇒ Tree[B]] <*> ⇒ G[Tree[B]]
  82. implicit val TreeTraverse = new Traverse[Tree] { def traverse[G[_], A,

    B](fa: Tree[A])(f: A => G[B])(implicit G: Applicative[G]): G[Tree[B]] = fa match { case Leaf(a) ⇒ f(a) <*> G.point(leaf[B]) // ← constructs G[Tree[B]] case Node(l, r) ⇒ traverse(r)(f) <*> (traverse(l)(f) <*> G.point(node[B]) // ← G[Tree[B]] } }
  83. implicit val TreeTraverse = new Traverse[Tree] { def traverse[F[_], A,

    B](fa: Tree[A])(f: A => F[B])(implicit G: Applicative[F]): F[Tree[B]] = fa match { case Leaf(a) ⇒ f(a) <*> G.point(leaf[B]) case Node(l, r) ⇒ traverse(r)(f) <*> (traverse(l)(f) <*> G.point(node[B])) } } @ val binaryTree: Tree[Option[Int]] = Node(Leaf(Some(1)), Node(Leaf(Some(2)), Leaf(Some(3)))) @ binaryTree.sequence shouldEqual Some(Node(Leaf(1),Node(Leaf(2), Leaf(3)))) Option[Tree[Int]]
  84. 0. Functions are just values. 1. Always use Total Functions.

    2. Model Computation as Data. 3. Separate description of a Computation from its interpretation. 4. FP facilitates a uniform framework for programming with effects. 5. Apply Functional Abstractions that are correct by construction.
  85. Image Credit Hea Poh Lin From Noun Project Allen Wang

    From Noun Project Umesh.vgl From Noun Project aguycalledgary From Noun Project Shaun Moynihan From Noun Project