The Essence of Functional Structures - Scala eXchange2016

In this talk, you will get a practical overview of various functional structures that allows building powerful, highly-composable and purely-functional abstractions. The primary goal of this session is to delve into these structures and gain insight on applying them in solving real-world problems.

From scratch, you will learn to construct the Scala type classes to represent these structures. Starting with basic constructs such as Semigroups and Monoids, you will continue exploring structures such as Functors, Applicative Functors, Monads and finally, Monad Transformers. Alongside, from the practical point of view, you will discover the essence of these structures in encoding purely functional programs that are robust, comprehensible and correct-by-construction.

No prior knowledge of functional programming is assumed in this talk.

Transcript

2. About Me Adil Akhter Lead Engineer at ING Amsterdam, The Netherlands http://coyoneda.xyz adilakhter
4. 0. Concepts & Building Blocks. 1. Core Design Principles. 2. Few Purely Algebraic Structures.
5. Applicative Functor Monad Foldable Traversable
8. https://twitter.com/mfeathers/status/29581296216
9. https://xkcd.com/1312/
11. https://twitter.com/viktorklang/status/790172536281628672
13. https://twitter.com/ID_AA_Carmack/status/53512300451201024
15. Functions
16. Total Function
17. f A B Domain Codomain
18. val f: String => Int = s => s.length f: String 㱺 Int Domain Codomain C D E CD DE           
19. val x = 1 val add = (x: Int) => x + 1
20. val addTwoInts: Int => (Int => Int) = x => y => x + y val addWithOne: Int => Int = addTwoInts (1)
22. 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 f A B g B C h A C
23. 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
24. 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
25. Functions are values.
28. Int String Boolean F[Int] F[String] F[Boolean]
32. 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 }
33. Always Use Total Functions.
34. 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) }
35. 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) }
36. 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) }
38. @ def maxValue(xs: List[Int]): String = s"Maximum value is ${xs.max}"
39. @ def maxValue(xs: List[Int]): String = s"Maximum value is ${xs.max}" @ val ints = List.empty[Int] @ maxValue(ints)
40. @ 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)
41. @ def divideOneBy(y: Int): Double = 1/y
42. @ 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)
43. How to solve it?
44. def divideOneBy(y: Int): Double def divideOneBy(y: NonZeroInt): Double
45. Option sealed trait Option[A] case class Some[A](value: A) extends Option[A] case class None[A]() extends Option[A]
46. def divideOneBy(y: Int): Double def divideOneBy(y: Int): Option[Double]
48. A A B f Wrap Unwrap B Task[A] List[A] Option[A] Container Type
51. trait Functor[F[_]] { def map[A, B](fa: F[A])(f : A => B): F[B] } A map(f: A 㱺 B) B
52. 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]
53. LAWS
54. Identity @ def identity[A](x: A): A = x @ Option(1).map(identity) shouldEqual Option(1) @ None.map(identity) shouldEqual None
55. 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
56. 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
57. Does Set form a Functor?
58. 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 )
59. Example
60. 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("ßß")))
61. 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)) } }
62. @ 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
63. @ 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
64. @ 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
65. 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)
66. @ 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 ?
67. 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?
69. trait Applicative[F[_]] extends Functor[F] { def ap[A, B](fa: => F[A])(f: => F[A => B]): F[B] //aka `apply`, <*> def point[A](a: => A): F[A] // aka pure }
70. @ 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
71. implicit val OptionApplicative = new Applicative[Option] { def point[A](a: => A): Option[A] = // ... } ??? A A point
72. implicit val OptionApplicative = new Applicative[Option] { def point[A](a: => A): Option[A] = Some(a) // ... } A A point
73. A A㱺B ap B
74. https://twitter.com/jessitron/status/377554594618175488
75. 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] = ??? }
76. 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) ⇒ ??? } }
77. 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) ⇒ ??? } } }
78. 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)) } } }
79. 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?
80. 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) } }
81. 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) } }
82. 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)
83. 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)
84. Example
85. @ 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.pure[Option] // Option[(Int) => (Int) => (Int) => Int] @ val result = zOpt <*> (yOpt <*> (xOpt <*> addOpt)) // Some(6)
86. @ 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.pure[Option] // Option[(Int) => (Int) => (Int) => Int] @ val result = zOpt <*> (yOpt <*> (xOpt <*> addOpt)) // Some(6)
87. @ 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
88. @ 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)
89. @ val result = (xOpt |@| yOpt |@| zOpt) { (x, y, z) => x + y + z }
90. Example
91. 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
92. Recap Allows pure function to be applied on Effectful arguments.
94. Effectful Function Effectful Argument
95. trait Monad[F[_]] extends Applicative[F] { def bind[A, B](fa: F[A]) (f: A ⇒ F[B]): F[B] }
96. 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
97. trait Monad[F[_]] extends Applicative[F] { def bind[A, B](fa: F[A]) (f: A ⇒ F[B]): F[B] } also known as ‘FlatMap‘
98. A bind B B trait Monad[F[_]] extends Applicative[F] { def bind[A, B](fa: F[A]) (f: A ⇒ F[B]): F[B] }
99. Example
100. 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) }
101. 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) }
102. @ 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
103. Example
104. def readCoordinate(): Coordinate = { println("Latitude:") val longitude = StdIn.readLine().toDouble println("Longitude:") val latitude = StdIn.readLine().toDouble Coordinate(longitude, latitude) } Recall
105. final case class IO[A](unsafePerformIO: () => A)
106. final case class IO[A](unsafePerformIO: () => A) def readLine2: IO[String] = IO(() => readLine()) def println2(s: String): IO[Unit] = IO(() => println(s))
107. 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)
108. 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()) }
109. 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()) }
110. 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()) }
111. 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()) }
112. 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()) }
113. @ val coordinateStringIO: IO[(String, String)] = for { _ ← println2("Latitude:") x ← readLine2 _ ← println2("Longitude:") y ← readLine2 } yield (x, y)
114. Computation As Data Model Computation as Data.
115. @ val result: (String, String) = coordinateStringIO.unsafePerformIO()
116. @ val result: (String, String) = coordinateStringIO.unsafePerformIO() ↩︎ > Longitude: 37.773972 ↩︎ > Latitude: -122.431297 ↩︎ // result = (37.773972,-122.431297)
117. Computation As Data Separate description of a Computation from its interpretation.
118. @ 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
119. @ 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
120. @ val coordinate: Option[Coordinate] = coordinateIO.unsafePerformIO() > Longitude: 37.773972 ↩︎ > Latitude: -122.431297 ↩︎ // coordinate = Some(Coordinate(37.773972,-122.431297))
121. Example
122. case class Product(productId: String, description: String, price: Double) def product(id: String): Task[Product] // gets product from Product Service def allRcommendations(aProduct: Product): Task[List[Product]] = (itemitemRecommendations(aProduct) |@| visualRecommendations(aProduct)) {_ ++ _} def recommendations(id: String): Task[List[Product]] = ???
123. case class Product(productId: String, description: String, price: Double) def product(id: String): Task[Product] // get product from Product Service def allRcommendations(aProduct: Product): Task[List[Product]] = (itemitemRecommendations(aProduct) |@| visualRecommendations(aProduct)) {_ ++ _} def recommendations(id: String): Task[List[Product]] = for { p <- product("123123") recs <- allRecommendations(p) } yield recs Sequencing dependent computations
125. Applicative Functor Monad map app bind f: A ⇒ F[B] f: A ⇒ B f: A1 ⇒ A2 ⇒ … ⇒ An
126. Computation As Data FP facilitates a uniform framework for programming with effects.
129. trait Semigroup[A] { def append(a1: A, a2: ⇒ A): A } trait Monoid[A] extends Semigroup[A] { def zero: A }
133. LAWS
136. Can we implement a Monoid for Division of Integers?
137. Example
138. def optionMonoid[A](implicit m: Monoid[A]) = ???
139. 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)) } }
140. Profit Time! def reduce[A](list: List[A]) (implicit m: Monoid[A]): A = ???
141. 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)) }
142. 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)
144. trait Foldable[F[_]] { def foldMap[A, B](fa: F[A])(f: A ⇒ B)(implicit F: Monoid[B]): B }
145. 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)) }
146. 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"
147. https://twitter.com/daviottenheimer/status/532661754820829185
148. case class Product(productId: String, description: String, price: Int) @ products.foldMap(_.price)
150. 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]] }
151. 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
152. 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]] }
154. Example
155. 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.
156. 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]) } }
157. 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]) } }
158. 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]] } }
159. 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]]
160. Applicative Functor Monad Foldable Traversable
162. 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.
164. Questions ?
165. 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