Share
Embed
Will it Blend? - ScalaSyd February 2015
Sometimes merging or appending collections together doesn't work as expected.
Video: http://goo.gl/hQxxqz
Code: http://goo.gl/aQUifC
Filippo Vitale
February 11, 2015
Transcript
96 slides
-
value value value Map Set key value key value key
value List v v v v -
Blending Appending Lists List(1, 2, 3) ++ List(4, 5, 6)
== List(1, 2, 3, 4, 5, 6) http://www.scala-lang.org/api/current/#scala.collection.immutable.List http://docs.scala-lang.org/overviews/collections/seqs.html def ++[B](that: Traversable[B]): List[B] Returns a new list containing the elements from the left hand operand followed by the elements from the right hand operand. -
Blending Adding Sets Set(1, 2, 3) ++ Set(4, 5, 6)
== Set(5, 1, 6, 2, 3, 4) http://www.scala-lang.org/api/current/#scala.collection.immutable.Set http://docs.scala-lang.org/overviews/collections/sets.html def ++[B](that: Traversable[B]): Set[B] Returns a new set containing the elements from the left hand operand followed by the elements from the right hand operand. -
Blending Adding Sets Set(1, 2, 3) ++ Set(4, 5, 6)
== Set(5, 1, 6, 2, 3, 4) Set(1, 2) ++ Set(2, 3) == Set(1, 2, 3) -
Immutable Collection Hierarchy Traversable Seq Set Map List HashSet HashMap
http://docs.scala-lang.org/tutorials/FAQ/collections.html -
Blending Adding Maps Map() ++ Map("a" -> 1) == Map("a"
-> 1) http://www.scala-lang.org/api/current/#scala.collection.immutable.Map http://docs.scala-lang.org/overviews/collections/maps.html def ++[B](that: Traversable[(A, B)]): Map[A, B] Returns a new map containing the elements from the left hand operand followed by the elements from the right hand operand. -
Blending Adding Maps Map("a" -> Set(1, 2)) ++ Map("a" ->
Set(2, 3)) == ??? http://www.scala-lang.org/api/current/#scala.collection.immutable.Map http://docs.scala-lang.org/overviews/collections/maps.html def ++[B](that: Traversable[(A, B)]): Map[A, B] Returns a new map containing the elements from the left hand operand followed by the elements from the right hand operand. -
Map("a" -> Set(1, 2)) ++ Map("a" -> Set(2, 3)) ==
??? 1: Map("a" -> Set(1, 2)) 2: Map("a" -> Set(1, 2, 3)) 3: Map("a" -> Set(2, 3)) 4: RuntimeException 5: Compiler Error What is the result of “blending” those Maps? -
Map("a" -> Set(1, 2)) ++ Map("a" -> Set(2, 3)) ==
??? 1: 2: 3: Map("a" -> Set(2, 3)) 4: 5: What is the result of “blending” those Maps? -
Map("a" -> Set(1, 2)) ??? Map("a" -> Set(2, 3)) Map("a"
-> Set(1, 2, 3)) -
Map with values as Set (of Int) “a” Set(1, 2)
“key b” Set(4, 7, 5) “key c” Set(9, 4) “a” Set(2, 3) “key c” Set(3, 4) “key d” Set(5, 6) val ma: Map[String, Set[Int]] val mb: Map[String, Set[Int]] -
Map with values as Set (of Int) “a” Set(1, 2)
“a” Set(2, 3) “a” Set(1, 2) ++ Set(2, 3) -
Map with values as Set (of Int) “a” Set(1, 2)
“a” Set(2, 3) “a” Set(1, 2, 3) -
def blend(ma: Map[String, Set[Int]], mb: Map[String, Set[Int]]) : Map[String, Set[Int]]
= { for ((k, v) <- mb) { ??? } } -
def blend(ma: Map[String, Set[Int]], mb: Map[String, Set[Int]]) : Map[String, Set[Int]]
= { val result = mutable.Map() ++ ma for ((k, v) <- mb) { ??? } result.toMap } -
def blend(ma: Map[String, Set[Int]], mb: Map[String, Set[Int]]) : Map[String, Set[Int]]
= { val result = mutable.Map() ++ ma mb foreach { case (k, v) => ??? } result.toMap } -
def blend(ma: Map[String, Set[Int]], mb: Map[String, Set[Int]]) : Map[String, Set[Int]]
= { val result = mutable.Map() ++ ma mb foreach { case (k, v) => if (result.contains(k)) result += k -> (result(k) ++ v) else result += k -> v } result.toMap } -
def blend(ma: Map[String, Set[Int]], mb: Map[String, Set[Int]]) : Map[String, Set[Int]]
= { } (ma /: mb) { case (result,(k, v)) => if (result.contains(k)) result + (k -> (result(k) ++ v)) else result + (k -> v) } val result = mutable.Map() ++ ma mb foreach { case (k, v) => if (result.contains(k)) result += k -> (result(k) ++ v) else result += k -> v } result.toMap -
def blend(ma: Map[String, Set[Int]], mb: Map[String, Set[Int]]) : Map[String, Set[Int]]
= { } (ma /: mb) { case (result,(k, v)) => if (result.contains(k)) result + (k -> (result(k) ++ v)) else result + (k -> v) } val result = mutable.Map() ++ ma mb foreach { case (k, v) => if (result.contains(k)) result += k -> (result(k) ++ v) else result += k -> v } result.toMap mb.foldLeft(ma) { ... } -
def blend(ma: Map[String, Set[Int]], mb: Map[String, Set[Int]]) : Map[String, Set[Int]]
= { } (ma /: mb) { case (result,(k, v)) => if (result.contains(k)) result + (k -> (result(k) ++ v)) else result + (k -> v) } val result = mutable.Map() ++ ma mb foreach { case (k, v) => if (result.contains(k)) result += k -> (result(k) ++ v) else result += k -> v } result.toMap -
def blend(ma: Map[String, Set[Int]], mb: Map[String, Set[Int]]) : Map[String, Set[Int]]
= { } (ma /: mb) { case (result,(k, v)) => if (result.contains(k)) result + (k -> (result(k) ++ v)) else result + (k -> v) } val result = mutable.Map() ++ ma mb foreach { case (k, v) => if (result.contains(k)) result += k -> (result(k) ++ v) else result += k -> v } result.toMap -
def blend(ma: Map[String, Set[Int]], mb: Map[String, Set[Int]]) : Map[String, Set[Int]]
= { (ma /: mb) { case (result,(k, v)) => if (result.contains(k)) result + (k -> (result(k) ++ v)) else result + (k -> v) } } -
(ma /: mb) { case (result,(k, v)) => result +
(k -> { result.get(k) match { case Some(vr) => vr ++ v case None => v } } -
(ma /: mb) { case (result,(k, v)) => result +
(k -> { result.get(k) match { case Some(vr) => vr ++ v case None => v } // .map(_ ++ v).getOrElse(v) // // // }} -
(ma /: mb) { case (result,(k, v)) => result +
(k -> { result.get(k) match { case Some(vr) => vr ++ v case None => v } // .map(_ ++ v).getOrElse(v) // .some(_ ++ v).none(v) // // }} -
(ma /: mb) { case (result,(k, v)) => result +
(k -> { result.get(k) match { case Some(vr) => vr ++ v case None => v } // .map(_ ++ v).getOrElse(v) // .some(_ ++ v).none(v) // .fold(v)(_ ++ v) // }} -
(ma /: mb) { case (result,(k, v)) => result +
(k -> { result.get(k) match { case Some(vr) => vr ++ v case None => v } // .map(_ ++ v).getOrElse(v) // .some(_ ++ v).none(v) // .fold(v)(_ ++ v) // .cata(_ ++ v, v) }} -
(ma /: mb) { case (result,(k, v)) => result +
(k -> { result.get(k) match { case Some(vr) => vr ++ v case None => v } // .map(_ ++ v).getOrElse(v) // .some(_ ++ v).none(v) // .fold(v)(_ ++ v) // .cata(_ ++ v, v) }} http://stackoverflow.com/questions/5328007/why-doesnt-option-have-a-fold-method http://en.wikipedia.org/wiki/Catamorphism “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire” -
(ma /: mb) { case (result,(k, v)) => result +
(k -> { result.get(k) match { case Some(vr) => vr ++ v case None => v } // .map(_ ++ v).getOrElse(v) // .some(_ ++ v).none(v) // .fold(v)(_ ++ v) // .cata(_ ++ v, v) }} http://stackoverflow.com/questions/5328007/why-doesnt-option-have-a-fold-method http://en.wikipedia.org/wiki/Catamorphism “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire” -
(ma /: mb) { case (result, (k, v)) => result
+ (k -> result.get(k).cata(_ ++ v, v)) } val result = mutable.Map() ++ ma mb foreach { case (k, v) => result += (k -> result.get(k).cata(_ ++ v, v)) } -
def blend(ma: Map[String, Set[Int]], mb: Map[String, Set[Int]]) : Map[String, Set[Int]]
= (ma /: mb) { case (result, (k, v)) => result + (k -> result.get(k).cata(_ ++ v, v)) } Map[String, Set[Int]] Map[String, Map[Int, Set[Int]]] -
def blend(ma: Map[String, Map[Int, Set[Int]]], mb: Map[String, Map[Int, Set[Int]]]) :
Map[String, Map[Int, Set[Int]]] = (ma /: mb) { case (result, (k, v)) => result + ??? // { ??? => { ??? } } } Map[String, Set[Int]] Map[String, Map[Int, Set[Int]]] -
trait Blendable[A] { def blend(ma: A, mb: A): A }
new Blendable[...] { def blend(ma: ..., mb: ...): ... = ??? } -
trait Blendable[A] { def blend(ma: A, mb: A): A }
new Blendable[...] { def blend(ma: ..., mb: ...): ... = ??? } x10 Developer -
What blended “as expected”? List using the ++ binary operator
Set using the ++ binary operator List(1, 2, 3) ++ List(4, 5, 6) == List(1, 2, 3, 4, 5, 6) Set(1, 2) ++ Set(2, 3) == Set(1, 2, 3) -
(List, ++) (Set, ++) (1 blend 2) == ??? What
about Int? -
(List, ++) (Set, ++) (Int, +) (1 blend 2) ==
1 + 2 == 3 What about Int? -
(List, ++) (Set, ++) (Int, +) (String, +) ("ab" blend
"cd") == ("ab" + "cd") == "abcd" String -
(List, ++) (Set, ++) (Int, +) (String, +) (Map[...], Blendable[...].blend)
Blendable[Map[String, Set[Int]]].blend(ma, mb) Map[String, Set[Int]] -
What is a Semigroup? Michael Barr, Charles Wells - Category
Theory for Computing Science Semigroups “A semigroup is a set S together with an associative binary operation m: S × S → S” -
Closure Property http://en.wikipedia.org/wiki/Closure_(mathematics) trait Semigroup[T] { def op(a: T, b:
T): T } For all a, b in T, the result of the operation a ⋅ b is also in T: ∀a, b ∈ T : a∙b ∈ T -
http://en.wikipedia.org/wiki/Closure_(mathematics) trait Semigroup[T] { def op(a: T, b: T): T
} def op(a: Boolean, b: Boolean): Boolean def op(a: Int, b: Int): Boolean ✓ ✘ Closure Property -
Associative Property http://en.wikipedia.org/wiki/Associative_property trait Semigroup[T] { def op(a: T, b:
T): T } For all a, b, and c in T, the equation (a ⋅ b) ⋅ c = a ⋅ (b ⋅ c) holds: ∀a, b, c ∈ T : (a∙b)∙c = a∙(b∙c) (a op b) op c == a op (b op c) -
What is a Semigroup? Michael Barr, Charles Wells - Category
Theory for Computing Science Semigroups “A semigroup is a set S together with an associative binary operation m: S × S → S” -
Scalaz and Semigroup implicit def setSemigroup[A]:Semigroup[Set[A]] = new Semigroup[Set[A]] {
def append(f1: Set[A], f2: => Set[A]) = f1 ++ f2 } -
Scalaz and Semigroup implicit def setSemigroup[A]:Semigroup[Set[A]] = new Semigroup[Set[A]] {
def append(f1: Set[A], f2: => Set[A]) = f1 ++ f2 } op -
Scalaz and Semigroup import scalaz.syntax.semigroup._ import scalaz.std.list._ Set(1, 2) |+|
Set(2, 3) res0: scala.collection.immutable.Set[Int] = Set(1, 2, 3) -
Scalaz and Semigroup import scalaz.syntax.semigroup._ import scalaz.std.list._ List(1, 2) |+|
List(3, 4) res0: scala.collection.immutable.List[Int] = List(1, 2, 3, 4) -
Scalaz and Semigroup import scalaz.syntax.semigroup._ import scalaz.std.string._ "a" |+| "b"
|+| "c" res0: String = abc -
/** * A semigroup in type F must satisfy two
laws: * * - '''closure''': `∀ a, b in F, append(a, b)` is also in `F`. * - '''associativity''': `∀ a, b, c` in `F`, the equation * `append(append(a, b), c) = append(a, append(b , c))` holds. */ trait SemigroupLaw { def associative(f1: F, f2: F, f3: F)(implicit F: Equal[F]): Boolean = F.equal(append(f1, append(f2, f3)), append(append(f1, f2), f3)) } -
import scalaz.scalacheck.ScalazProperties._ semigroup.laws[String].check semigroup.laws[Set[Int]].check semigroup.laws[List[String]].check semigroup.laws[Map[Int, Int]].check + semigroup.associative: OK,
passed 100 tests. + semigroup.associative: OK, passed 100 tests. + semigroup.associative: OK, passed 100 tests. + semigroup.associative: OK, passed 100 tests. -
Map("a" -> Set(1, 2)) |+| Map("a" -> Set(2, 3)) res0:
...immutable.Map[...] = Map(a -> Set(1, 2, 3)) -
Map("a" -> Set(1, 2)) |+| Map("a" -> Set(2, 3)) “Some
data structures form interesting semigroups as long as the types of the elements they contain also form semigroups.” “adapted” from: Functional Programming in Scala - Part 3 - Chapter 10 Monoids -
Map("a" -> Map("aa" -> Map("aaa" -> Map("aaaa" -> List(1, 3),
"aaab" -> List(2, 4))))) |+| Map("a" -> Map("aa" -> Map("aaa" -> Map("aaaa" -> List(5, 7), "aaab" -> List(6, 8))))) Map(a->Map(aa->Map(aaa->Map(aaaa->List(1, 3, 5, 7), aaab->List(2, 4, 6, 8))))) -
Map("a" -> 1, "b" -> 4) |+| Map("a" -> 2)
res0: ...immutable.Map[...] = Map(a -> 3, b -> 4) -
1.some |+| 2.some res0: Option[Int] = Some(3) 1.some |+| none[Int]
res1: Option[Int] = Some(1) -
implicit def optionMonoid[A: Semigroup]: ... def append(f1: Option[A], f2: =>
Option[A]) = (f1, f2) match { case (Some(a1), Some(a2)) => Some(Semigroup[A].append(a1, a2)) case (Some(a1), None) => f1 case (None, sa2 @ Some(a2)) => sa2 case (None, None) => None } } -
Customised Semigroup case class MeetupOrganiser(name: String, meetup: String, yowCommunityAward: Int)
val jed = MeetupOrganiser("Jed", "scalasyd", 1) val mark = MeetupOrganiser("Mark", "scalasyd", 0) val leo = MeetupOrganiser("Leonardo", "clj-syd", 0) -
Customised Semigroup case class MeetupOrganiser(name: String, meetup: String, yowCommunityAward: Int)
implicit val meetupOrganiserSemigroup = new Semigroup[MeetupOrganiser] { def append(f1: MeetupOrganiser, f2: => MeetupOrganiser): MeetupOrganiser = if (f1.yowCommunityAward >= f2.yowCommunityAward) f1 else f2 } -
Customised Semigroup implicit val meetupOrganiserArbitrary: Arbitrary[MeetupOrganiser] = Arbitrary(for { n
<- arbitrary[String] m <- arbitrary[String] r <- arbitrary[Int] } yield MeetupOrganiser(n, m, r)) implicit val meetupOrganiserEqual: Equal[MeetupOrganiser] = Equal.equal(_ == _) semigroup.laws[MeetupOrganiser].check + semigroup.associative: OK, passed 100 tests. -
Customised Semigroup mark |+| leo res0: MeetupOrganiser = MeetupOrganiser(Mark,scalasyd,0) mark
|+| leo |+| jed res1: MeetupOrganiser = MeetupOrganiser(Jed,scalasyd,1) NonEmptyList(mark, leo, jed).suml1 res2: MeetupOrganiser = MeetupOrganiser(Jed,scalasyd,1)