1 /*
2 
3 Copyright 2018 Sebastian B. Galkin
4 
5 This file is part of paraseba/scaladores-may-2018-talk.
6 
7 paraseba/scaladores-may-2018-talk is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11 
12 paraseba/scaladores-may-2018-talk is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16 
17 You should have received a copy of the GNU General Public License
18 along with Foobar.  If not, see <http://www.gnu.org/licenses/>.
19 
20 */
21 
22 package monoid.monoids
23 
24 import scala.collection.immutable._
25 import scala.collection.parallel.TaskSupport
26 
27 trait Semigroup[M] {
28 
29   def append(a: M, b: => M): M
30 
31 }
32 
33 trait Monoid[M] extends Semigroup[M] {
34 
35   def zero: M
36 
37 }
38 
39 object Monoid {
40   def apply[A:Monoid]: Monoid[A] = implicitly[Monoid[A]]
41 }
42 
43 object Semigroup {
44   def apply[A:Semigroup]: Semigroup[A] = implicitly[Semigroup[A]]
45 }
46 
47 object SemigroupSyntax {
48   @SuppressWarnings(Array("org.wartremover.warts.ImplicitConversion"))
49   implicit def ToSemigroupOps[A:Semigroup](v: A): SemigroupOps[A] =
50     new SemigroupOps[A](v)
51 
52   final class SemigroupOps[A:Semigroup](val self: A) {
53     def |+|(other: => A): A =
54       Semigroup[A].append(self, other)
55   }
56 }
57 
58 object SimpleMonoids {
59   import SemigroupSyntax._
60 
61   implicit def intAddMon: Monoid[Int] = new Monoid[Int] {
62     def zero = 0
63     def append(a: Int, b: => Int): Int = a + b
64   }
65 
66 
67   // is this really a monoid?
68   implicit def floatAddMon: Monoid[Double] = new Monoid[Double] {
69     def zero: Double = 0
70     def append(a: Double, b: => Double): Double = a + b
71   }
72 
73   implicit def intMulMon: Monoid[Int] = new Monoid[Int] {
74     def zero = 1
75     def append(a: Int, b: => Int): Int = a * b
76   }
77 
78   implicit def freeMon[A]: Monoid[List[A]] = new Monoid[List[A]] {
79     def zero: List[A] = List()
80     def append(as: List[A], bs: => List[A]): List[A] = as ++ bs
81   }
82 
83   def firstMon[A]: Monoid[Option[A]] = new Monoid[Option[A]] {
84     def zero = None
85     def append(a: Option[A], b: => Option[A]): Option[A] = a orElse b
86   }
87 
88   implicit def optionMon[A:Semigroup]: Monoid[Option[A]] =
89     new Monoid[Option[A]] {
90 
91       def zero: Option[A] = None
92 
93       def append(a: Option[A], b: => Option[A]): Option[A] =
94         (a,b) match {
95           case (a, None) => a
96           case (None, b) => b
97           case (Some(a), Some(b)) => Some(a |+| b)
98         }
99   }
100 
101   implicit def endoMon[A]: Monoid[A => A] = new Monoid[A => A] {
102     def zero: A => A = identity
103     def append(f: A => A, g: => (A => A)): A => A = g andThen f
104   }
105 
106   implicit def monFunSemi[A, B:Semigroup]: Semigroup[A => B] =
107     new Semigroup[A => B] {
108 
109       def append(f: A => B, g: => (A => B)): A => B =
110         a => f(a) |+| g(a)
111     }
112 
113   implicit def monFunMon[A, B:Monoid]: Monoid[A => B] =
114     new Monoid[A => B] {
115 
116       def zero: A => B = _ => Monoid[B].zero
117 
118       def append(f: A => B, g: => (A => B)): A => B =
119         a => f(a) |+| g(a)
120   }
121 
122   //(implicit am: Monoid[A], implicit bm: Monoid[B])
123   implicit def pairMon[A: Monoid, B: Monoid]: Monoid[(A,B)] = new Monoid[(A, B)] {
124 
125     def zero: (A,B) = (Monoid[A].zero, Monoid[B].zero)
126 
127     def append(x: (A, B), y: => (A, B)): (A,B) =
128       (x._1 |+| y._1, x._2 |+| y._2)
129   }
130 
131   implicit def tripleMon[A: Monoid, B: Monoid, C: Monoid]: Monoid[(A,B,C)] = new Monoid[(A, B, C)] {
132 
133     def zero: (A,B,C) = (Monoid[A].zero, Monoid[B].zero, Monoid[C].zero)
134 
135     def append(x: (A, B, C), y: => (A, B, C)): (A,B, C) =
136       (x._1 |+| y._1, x._2 |+| y._2, x._3 |+| y._3)
137   }
138 
139 
140   def mconcat[A:Monoid](as: Traversable[A]): A =
141     as.foldLeft(Monoid[A].zero)(_ |+| _)
142 
143   def sum(xs: Traversable[Int]): Int =
144     mconcat(xs)(intAddMon)
145 
146   def first[A](xs: Traversable[Option[A]]): Option[A] =
147     mconcat(xs)(firstMon)
148 
149   def concat[A](xs: Traversable[List[A]]): List[A] =
150     mconcat(xs)(freeMon)
151 
152   def sumO[A](xs: Traversable[Option[Int]]): Option[Int] =
153     mconcat(xs)(optionMon(intAddMon))
154 
155   def foldMap[A, M:Monoid](as: Traversable[A], f: A => M): M =
156     as.foldLeft(Monoid[M].zero) { _ |+| f(_) }
157 
158   def foldMap2[A, M:Monoid](as: Traversable[A], f: A => M): M =
159     mconcat(as.map(f))
160 
161   def filter[A](as: List[A], f: A => Boolean): List[A] =
162     foldMap(as, (a:A) => if (f(a)) List(a) else List())(freeMon)
163 
164   val allMonoid: Monoid[Boolean] = new Monoid[Boolean] {
165     def zero: Boolean = true
166     def append(a: Boolean, b: => Boolean): Boolean = a && b
167   }
168 
169 
170   implicit val mon: Monoid[Boolean] = allMonoid
171 
172   @SuppressWarnings(Array("org.wartremover.warts.Equals"))
173   val numbers: Iterable[Int] = 1.to(100).filter(
174     // we only add zero to exercise the method, not really needed
175     ((n:Int) => n % 2 == 0) |+| ((n:Int) => n >= 10) |+| ((n:Int) => n < 20) |+| Monoid[ Int=> Boolean].zero
176   )
177 
178   def minMon[A:Ordering]: Monoid[Option[A]] = new Monoid[Option[A]] {
179     def zero: Option[A] = None
180 
181     def append(a: Option[A], b: => Option[A]): Option[A] = (a, b) match {
182       case (None, x) => x
183       case (x, None) => x
184       case (Some(x), Some(y)) => Some(Ordering[A].min(x,y))
185     }
186   }
187 
188   def maxMon[A:Ordering]: Monoid[Option[A]] = new Monoid[Option[A]] {
189     def zero: Option[A] = None
190 
191     def append(a: Option[A], b: => Option[A]): Option[A] = (a, b) match {
192       case (None, x) => x
193       case (x, None) => x
194       case (Some(x), Some(y)) => Some(Ordering[A].max(x,y))
195     }
196   }
197 
198   def maxSemi[A:Ordering]: Semigroup[A] = new Semigroup[A] {
199     def append(a: A, b: => A): A = Ordering[A].max(a,b)
200   }
201 
202   def minSemi[A:Ordering]: Semigroup[A] = new Semigroup[A] {
203     def append(a: A, b: => A): A = Ordering[A].min(a,b)
204   }
205 
206   def min[A: Ordering](as: Traversable[A]): Option[A] =
207     foldMap(as, (a:A) => Option(a))(minMon) // map and reduce
208 
209   def max[A: Ordering](as: Traversable[A]): Option[A] =
210     foldMap(as, (a:A) => Option(a))(maxMon) // map and reduce
211 
212   def minMaxMon[A:Ordering]: Monoid[(Option[A], Option[A])] = pairMon(minMon, maxMon)
213 
214   def minmax[A: Ordering](as: Traversable[A]): Option[(A,A)] =
215     foldMap(as, (a:A) => (Option(a), Option(a)))(minMaxMon) match {
216       case (Some(mi), Some(ma)) => Some((mi,ma))
217       case _ => None
218     }
219 }
220 
221 
222 object Parallel {
223 
224   import SemigroupSyntax._
225 
226   // We receive a Task Support to make testing easier, thread pools are shared between tests
227   def mconcat[A:Monoid](as: Traversable[A])(ts: TaskSupport): A = {
228     val parAs = as.par
229     parAs.tasksupport = ts
230     parAs.fold(Monoid[A].zero)(_ |+| _)
231   }
232 }
233 
234 object Stats {
235 
236   sealed abstract class MeanVar
237   final case object EmptyMeanVar extends MeanVar
238   final case class MeanVarV(m1: Double, m2: Double, n: Long) extends MeanVar
239 
240   object MeanVar {
241     import SimpleMonoids.foldMap
242 
243     def singleton(x: Double): MeanVar = MeanVarV(x, 0, 1)
244 
245     def sample(xs: Traversable[Double]): MeanVar =
246       foldMap(xs, singleton)
247 
248     def mean: MeanVar => Option[Double] = {
249       case MeanVarV(m1, _, _) => Some(m1)
250       case _ => None
251     }
252 
253     def variance: MeanVar => Option[Double] = {
254       case MeanVarV(_, _, 1) => Some(0)
255       case MeanVarV(_, m2, n) => Some(m2/(n - 1.0))
256       case _ => None
257     }
258 
259     def sampleSize: MeanVar => Long = {
260       case MeanVarV(_, _, n) => n
261       case _ => 0
262     }
263 
264     implicit val meanVarMonoid: Monoid[MeanVar] = new Monoid[MeanVar] {
265       def zero: MeanVar = EmptyMeanVar
266 
267       def append(a: MeanVar, b: => MeanVar): MeanVar = (a, b) match {
268         case (MeanVarV(m1a, m2a, na), MeanVarV(m1b, m2b, nb)) => {
269           val (nt, delta) = (na + nb, m1b - m1a)
270           MeanVarV((na * m1a + nb * m1b ) / nt,
271                    m2a + m2b + delta * delta * na * nb / nt,
272                    nt)
273         }
274 
275         case (EmptyMeanVar, a) => a
276         case (a, EmptyMeanVar) => a
277       }
278     }
279   }
280 
281 
282 
283 }