typelevel / algebra
1
package algebra
2
package ring
3

4
import scala.{ specialized => sp }
5
import scala.annotation.tailrec
6

7
trait AdditiveSemigroup[@sp(Int, Long, Float, Double) A] extends Any with Serializable {
8 0
  def additive: Semigroup[A] = new Semigroup[A] {
9 0
    def combine(x: A, y: A): A = plus(x, y)
10 0
    override def combineAllOption(as: TraversableOnce[A]): Option[A] = trySum(as)
11
  }
12

13
  def plus(x: A, y: A): A
14

15
  def sumN(a: A, n: Int): A =
16 0
    if (n > 0) positiveSumN(a, n)
17 0
    else throw new IllegalArgumentException("Illegal non-positive exponent to sumN: %s" format n)
18

19
  protected[this] def positiveSumN(a: A, n: Int): A = {
20
    @tailrec def loop(b: A, k: Int, extra: A): A =
21 2
      if (k == 1) plus(b, extra) else {
22 2
        val x = if ((k & 1) == 1) plus(b, extra) else extra
23 2
        loop(plus(b, b), k >>> 1, x)
24
      }
25 2
    if (n == 1) a else loop(a, n - 1, a)
26
  }
27

28
  /**
29
   * Given a sequence of `as`, combine them and return the total.
30
   *
31
   * If the sequence is empty, returns None. Otherwise, returns Some(total).
32
   */
33
  def trySum(as: TraversableOnce[A]): Option[A] =
34 0
    as.toIterator.reduceOption(plus)
35
}
36

37
trait AdditiveCommutativeSemigroup[@sp(Int, Long, Float, Double) A] extends Any with AdditiveSemigroup[A] {
38 0
  override def additive: CommutativeSemigroup[A] = new CommutativeSemigroup[A] {
39 0
    def combine(x: A, y: A): A = plus(x, y)
40 0
    override def combineAllOption(as: TraversableOnce[A]): Option[A] = trySum(as)
41
  }
42
}
43

44
trait AdditiveMonoid[@sp(Int, Long, Float, Double) A] extends Any with AdditiveSemigroup[A] {
45 0
  override def additive: Monoid[A] = new Monoid[A] {
46 0
    def empty = zero
47 0
    def combine(x: A, y: A): A = plus(x, y)
48 0
    override def combineAllOption(as: TraversableOnce[A]): Option[A] = trySum(as)
49 0
    override def combineAll(as: TraversableOnce[A]): A = sum(as)
50
  }
51

52
  def zero: A
53

54
  /**
55
    * Tests if `a` is zero.
56
    */
57 2
  def isZero(a: A)(implicit ev: Eq[A]): Boolean = ev.eqv(a, zero)
58

59
  override def sumN(a: A, n: Int): A =
60 2
    if (n > 0) positiveSumN(a, n)
61 2
    else if (n == 0) zero
62 0
    else throw new IllegalArgumentException("Illegal negative exponent to sumN: %s" format n)
63

64
  /**
65
   * Given a sequence of `as`, compute the sum.
66
   */
67
  def sum(as: TraversableOnce[A]): A =
68 2
    as.foldLeft(zero)(plus)
69

70
  override def trySum(as: TraversableOnce[A]): Option[A] =
71 2
    if (as.isEmpty) None else Some(sum(as))
72
}
73

74
trait AdditiveCommutativeMonoid[@sp(Int, Long, Float, Double) A] extends Any with AdditiveMonoid[A] with AdditiveCommutativeSemigroup[A] {
75 2
  override def additive: CommutativeMonoid[A] = new CommutativeMonoid[A] {
76 2
    def empty = zero
77 2
    def combine(x: A, y: A): A = plus(x, y)
78 2
    override def combineAllOption(as: TraversableOnce[A]): Option[A] = trySum(as)
79 2
    override def combineAll(as: TraversableOnce[A]): A = sum(as)
80
  }
81
}
82

83
trait AdditiveGroup[@sp(Int, Long, Float, Double) A] extends Any with AdditiveMonoid[A] {
84 0
  override def additive: Group[A] = new Group[A] {
85 0
    def empty = zero
86 0
    def combine(x: A, y: A): A = plus(x, y)
87 0
    override def remove(x: A, y: A): A = minus(x, y)
88 0
    def inverse(x: A): A = negate(x)
89 0
    override def combineAllOption(as: TraversableOnce[A]): Option[A] = trySum(as)
90 0
    override def combineAll(as: TraversableOnce[A]): A = sum(as)
91
  }
92

93
  def negate(x: A): A
94 2
  def minus(x: A, y: A): A = plus(x, negate(y))
95

96
  override def sumN(a: A, n: Int): A =
97 2
    if (n > 0) positiveSumN(a, n)
98 2
    else if (n == 0) zero
99 2
    else if (n == Int.MinValue) positiveSumN(negate(plus(a, a)), 1073741824)
100 2
    else positiveSumN(negate(a), -n)
101
}
102

103
trait AdditiveCommutativeGroup[@sp(Int, Long, Float, Double) A] extends Any with AdditiveGroup[A] with AdditiveCommutativeMonoid[A] {
104 2
  override def additive: CommutativeGroup[A] = new CommutativeGroup[A] {
105 2
    def empty = zero
106 2
    def combine(x: A, y: A): A = plus(x, y)
107 2
    override def remove(x: A, y: A): A = minus(x, y)
108 2
    def inverse(x: A): A = negate(x)
109 2
    override def combineAllOption(as: TraversableOnce[A]): Option[A] = trySum(as)
110 2
    override def combineAll(as: TraversableOnce[A]): A = sum(as)
111
  }
112
}
113

114
trait AdditiveSemigroupFunctions[S[T] <: AdditiveSemigroup[T]] {
115

116
  def isAdditiveCommutative[A](implicit ev: S[A]): Boolean =
117 0
    ev.isInstanceOf[AdditiveCommutativeSemigroup[_]]
118

119
  def plus[@sp(Int, Long, Float, Double) A](x: A, y: A)(implicit ev: S[A]): A =
120 0
    ev.plus(x, y)
121

122
  def sumN[@sp(Int, Long, Float, Double) A](a: A, n: Int)(implicit ev: S[A]): A =
123 0
    ev.sumN(a, n)
124

125
  def trySum[A](as: TraversableOnce[A])(implicit ev: S[A]): Option[A] =
126 0
    ev.trySum(as)
127
}
128

129
trait AdditiveMonoidFunctions[M[T] <: AdditiveMonoid[T]]  extends AdditiveSemigroupFunctions[M] {
130
  def zero[@sp(Int, Long, Float, Double) A](implicit ev: M[A]): A =
131 2
    ev.zero
132

133
  def isZero[@sp(Int, Long, Float, Double) A](a: A)(implicit ev0: M[A], ev1: Eq[A]): Boolean =
134 0
    ev0.isZero(a)
135

136
  def sum[@sp(Int, Long, Float, Double) A](as: TraversableOnce[A])(implicit ev: M[A]): A =
137 0
    ev.sum(as)
138
}
139

140
trait AdditiveGroupFunctions[G[T] <: AdditiveGroup[T]]  extends AdditiveMonoidFunctions[G] {
141
  def negate[@sp(Int, Long, Float, Double) A](x: A)(implicit ev: G[A]): A =
142 0
    ev.negate(x)
143
  def minus[@sp(Int, Long, Float, Double) A](x: A, y: A)(implicit ev: G[A]): A =
144 0
    ev.minus(x, y)
145
}
146

147
object AdditiveSemigroup extends AdditiveSemigroupFunctions[AdditiveSemigroup] {
148
  @inline final def apply[A](implicit ev: AdditiveSemigroup[A]): AdditiveSemigroup[A] = ev
149
  /**
150
   * This method converts an additive instance into a generic
151
   * instance.
152
   *
153
   * Given an implicit `AdditiveSemigroup[A]`, this method returns a
154
   * `Semigroup[A]`.
155
   */
156
  @inline final def additive[A](implicit ev: AdditiveSemigroup[A]): Semigroup[A] =
157 0
    ev.additive
158
}
159

160
object AdditiveCommutativeSemigroup extends AdditiveSemigroupFunctions[AdditiveCommutativeSemigroup] {
161
  @inline final def apply[A](implicit ev: AdditiveCommutativeSemigroup[A]): AdditiveCommutativeSemigroup[A] = ev
162
  /**
163
   * This method converts an additive instance into a generic
164
   * instance.
165
   *
166
   * Given an implicit `AdditiveCommutativeSemigroup[A]`, this method returns a
167
   * `CommutativeSemigroup[A]`.
168
   */
169
  @inline final def additive[A](implicit ev: AdditiveCommutativeSemigroup[A]): CommutativeSemigroup[A] =
170 0
    ev.additive
171
}
172

173
object AdditiveMonoid extends AdditiveMonoidFunctions[AdditiveMonoid] {
174
  @inline final def apply[A](implicit ev: AdditiveMonoid[A]): AdditiveMonoid[A] = ev
175
  /**
176
   * This method converts an additive instance into a generic
177
   * instance.
178
   *
179
   * Given an implicit `AdditiveMonoid[A]`, this method returns a
180
   * `Monoid[A]`.
181
   */
182
  @inline final def additive[A](implicit ev: AdditiveMonoid[A]): Monoid[A] =
183 0
    ev.additive
184
}
185

186
object AdditiveCommutativeMonoid extends AdditiveMonoidFunctions[AdditiveCommutativeMonoid] {
187
  @inline final def apply[A](implicit ev: AdditiveCommutativeMonoid[A]): AdditiveCommutativeMonoid[A] = ev
188
  /**
189
   * This method converts an additive instance into a generic
190
   * instance.
191
   *
192
   * Given an implicit `AdditiveCommutativeMonoid[A]`, this method returns a
193
   * `CommutativeMonoid[A]`.
194
   */
195
  @inline final def additive[A](implicit ev: AdditiveCommutativeMonoid[A]): CommutativeMonoid[A] =
196 0
    ev.additive
197
}
198

199
object AdditiveGroup extends AdditiveGroupFunctions[AdditiveGroup] {
200
  @inline final def apply[A](implicit ev: AdditiveGroup[A]): AdditiveGroup[A] = ev
201
  /**
202
   * This method converts an additive instance into a generic
203
   * instance.
204
   *
205
   * Given an implicit `AdditiveGroup[A]`, this method returns a
206
   * `Group[A]`.
207
   */
208
  @inline final def additive[A](implicit ev: AdditiveGroup[A]): Group[A] =
209 0
    ev.additive
210
}
211

212
object AdditiveCommutativeGroup extends AdditiveGroupFunctions[AdditiveCommutativeGroup] {
213
  @inline final def apply[A](implicit ev: AdditiveCommutativeGroup[A]): AdditiveCommutativeGroup[A] = ev
214
  /**
215
   * This method converts an additive instance into a generic
216
   * instance.
217
   *
218
   * Given an implicit `AdditiveCommutativeGroup[A]`, this method returns a
219
   * `CommutativeGroup[A]`.
220
   */
221
  @inline final def additive[A](implicit ev: AdditiveCommutativeGroup[A]): CommutativeGroup[A] =
222 0
    ev.additive
223
}

Read our documentation on viewing source code .

Loading