typelevel / algebra
1
package algebra
2
package ring
3

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

7
trait MultiplicativeSemigroup[@sp(Int, Long, Float, Double) A] extends Any with Serializable {
8
  def multiplicative: Semigroup[A] =
9 2
    new Semigroup[A] {
10 2
      def combine(x: A, y: A): A = times(x, y)
11
    }
12

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

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

19
  protected[this] def positivePow(a: A, n: Int): A = {
20
    @tailrec def loop(b: A, k: Int, extra: A): A =
21 2
      if (k == 1) times(b, extra) else {
22 2
        val x = if ((k & 1) == 1) times(b, extra) else extra
23 2
        loop(times(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 tryProduct(as: TraversableOnce[A]): Option[A] =
34 0
    as.toIterator.reduceOption(times)
35
}
36

37
trait MultiplicativeCommutativeSemigroup[@sp(Int, Long, Float, Double) A] extends Any with MultiplicativeSemigroup[A] {
38 2
  override def multiplicative: CommutativeSemigroup[A] = new CommutativeSemigroup[A] {
39 2
    def combine(x: A, y: A): A = times(x, y)
40
  }
41
}
42

43
trait MultiplicativeMonoid[@sp(Int, Long, Float, Double) A] extends Any with MultiplicativeSemigroup[A] {
44 2
  override def multiplicative: Monoid[A] = new Monoid[A] {
45 2
    def empty = one
46 2
    def combine(x: A, y: A): A = times(x, y)
47
  }
48

49
  def one: A
50

51
  /**
52
    * Tests if `a` is one.
53
    */
54 0
  def isOne(a: A)(implicit ev: Eq[A]): Boolean = ev.eqv(a, one)
55

56
  override def pow(a: A, n: Int): A =
57 2
    if (n > 0) positivePow(a, n)
58 2
    else if (n == 0) one
59 0
    else throw new IllegalArgumentException("Illegal negative exponent to pow: %s" format n)
60

61
  /**
62
   * Given a sequence of `as`, compute the product.
63
   */
64
  def product(as: TraversableOnce[A]): A =
65 2
    as.foldLeft(one)(times)
66

67
  override def tryProduct(as: TraversableOnce[A]): Option[A] =
68 0
    if (as.isEmpty) None else Some(product(as))
69
}
70

71
trait MultiplicativeCommutativeMonoid[@sp(Int, Long, Float, Double) A] extends Any with MultiplicativeMonoid[A] with MultiplicativeCommutativeSemigroup[A] {
72 2
  override def multiplicative: CommutativeMonoid[A] = new CommutativeMonoid[A] {
73 2
    def empty = one
74 2
    def combine(x: A, y: A): A = times(x, y)
75
  }
76
}
77

78
trait MultiplicativeGroup[@sp(Int, Long, Float, Double) A] extends Any with MultiplicativeMonoid[A] {
79 0
  override def multiplicative: Group[A] = new Group[A] {
80 0
    def empty = one
81 0
    def combine(x: A, y: A): A = times(x, y)
82 0
    override def remove(x: A, y: A): A = div(x, y)
83 0
    def inverse(x: A): A = reciprocal(x)
84
  }
85

86 2
  def reciprocal(x: A): A = div(one, x)
87
  def div(x: A, y: A): A
88

89
  override def pow(a: A, n: Int): A =
90 2
    if (n > 0) positivePow(a, n)
91 2
    else if (n == 0) one
92 0
    else if (n == Int.MinValue) positivePow(reciprocal(times(a, a)), 1073741824)
93 0
    else positivePow(reciprocal(a), -n)
94
}
95

96
trait MultiplicativeCommutativeGroup[@sp(Int, Long, Float, Double) A] extends Any with MultiplicativeGroup[A] with MultiplicativeCommutativeMonoid[A] {
97 2
  override def multiplicative: CommutativeGroup[A] = new CommutativeGroup[A] {
98 2
    def empty = one
99 2
    def combine(x: A, y: A): A = times(x, y)
100 2
    override def remove(x: A, y: A): A = div(x, y)
101 2
    def inverse(x: A): A = reciprocal(x)
102
  }
103
}
104

105
trait MultiplicativeSemigroupFunctions[S[T] <: MultiplicativeSemigroup[T]] {
106
  def isMultiplicativeCommutative[A](implicit ev: S[A]): Boolean =
107 0
    ev.isInstanceOf[MultiplicativeCommutativeSemigroup[A]]
108

109
  def times[@sp(Int, Long, Float, Double) A](x: A, y: A)(implicit ev: S[A]): A =
110 0
    ev.times(x, y)
111
  def pow[@sp(Int, Long, Float, Double) A](a: A, n: Int)(implicit ev: S[A]): A =
112 0
    ev.pow(a, n)
113

114
  def tryProduct[A](as: TraversableOnce[A])(implicit ev: S[A]): Option[A] =
115 0
    ev.tryProduct(as)
116
}
117

118
trait MultiplicativeMonoidFunctions[M[T] <: MultiplicativeMonoid[T]] extends MultiplicativeSemigroupFunctions[M] {
119
  def one[@sp(Int, Long, Float, Double) A](implicit ev: M[A]): A =
120 2
    ev.one
121

122
  def isOne[@sp(Int, Long, Float, Double) A](a: A)(implicit ev0: M[A], ev1: Eq[A]): Boolean =
123 0
    ev0.isOne(a)
124

125
  def product[@sp(Int, Long, Float, Double) A](as: TraversableOnce[A])(implicit ev: M[A]): A =
126 0
    ev.product(as)
127
}
128

129
trait MultiplicativeGroupFunctions[G[T] <: MultiplicativeGroup[T]] extends MultiplicativeMonoidFunctions[G] {
130
  def reciprocal[@sp(Int, Long, Float, Double) A](x: A)(implicit ev: G[A]): A =
131 0
    ev.reciprocal(x)
132
  def div[@sp(Int, Long, Float, Double) A](x: A, y: A)(implicit ev: G[A]): A =
133 0
    ev.div(x, y)
134
}
135

136
object MultiplicativeSemigroup extends MultiplicativeSemigroupFunctions[MultiplicativeSemigroup] {
137
  @inline final def apply[A](implicit ev: MultiplicativeSemigroup[A]): MultiplicativeSemigroup[A] = ev
138
  /**
139
   * This method converts a multiplicative instance into a generic
140
   * instance.
141
   *
142
   * Given an implicit `MultiplicativeSemigroup[A]`, this method returns
143
   * a `Semigroup[A]`.
144
   */
145
  @inline final def multiplicative[A](implicit ev: MultiplicativeSemigroup[A]): Semigroup[A] =
146 0
    ev.multiplicative
147
}
148

149
object MultiplicativeCommutativeSemigroup extends MultiplicativeSemigroupFunctions[MultiplicativeCommutativeSemigroup] {
150
  @inline final def apply[A](implicit ev: MultiplicativeCommutativeSemigroup[A]): MultiplicativeCommutativeSemigroup[A] = ev
151
  /**
152
   * This method converts a multiplicative instance into a generic
153
   * instance.
154
   *
155
   * Given an implicit `MultiplicativeCommutativeSemigroup[A]`, this method returns
156
   * a `CommutativeSemigroup[A]`.
157
   */
158
  @inline final def multiplicative[A](implicit ev: MultiplicativeCommutativeSemigroup[A]): CommutativeSemigroup[A] =
159 0
    ev.multiplicative
160
}
161

162
object MultiplicativeMonoid extends MultiplicativeMonoidFunctions[MultiplicativeMonoid] {
163
  @inline final def apply[A](implicit ev: MultiplicativeMonoid[A]): MultiplicativeMonoid[A] = ev
164
  /**
165
   * This method converts a multiplicative instance into a generic
166
   * instance.
167
   *
168
   * Given an implicit `MultiplicativeMonoid[A]`, this method returns
169
   * a `Monoid[A]`.
170
   */
171
  @inline final def multiplicative[A](implicit ev: MultiplicativeMonoid[A]): Monoid[A] =
172 0
    ev.multiplicative
173
}
174

175
object MultiplicativeCommutativeMonoid extends MultiplicativeMonoidFunctions[MultiplicativeCommutativeMonoid] {
176
  @inline final def apply[A](implicit ev: MultiplicativeCommutativeMonoid[A]): MultiplicativeCommutativeMonoid[A] = ev
177
  /**
178
   * This method converts a multiplicative instance into a generic
179
   * instance.
180
   *
181
   * Given an implicit `MultiplicativeCommutativeMonoid[A]`, this method returns
182
   * a `CommutativeMonoid[A]`.
183
   */
184
  @inline final def multiplicative[A](implicit ev: MultiplicativeCommutativeMonoid[A]): CommutativeMonoid[A] =
185 0
    ev.multiplicative
186
}
187

188
object MultiplicativeGroup extends MultiplicativeGroupFunctions[MultiplicativeGroup] {
189
  @inline final def apply[A](implicit ev: MultiplicativeGroup[A]): MultiplicativeGroup[A] = ev
190
  /**
191
   * This method converts a multiplicative instance into a generic
192
   * instance.
193
   *
194
   * Given an implicit `MultiplicativeGroup[A]`, this method returns
195
   * a `Group[A]`.
196
   */
197
  @inline final def multiplicative[A](implicit ev: MultiplicativeGroup[A]): Group[A] =
198 0
    ev.multiplicative
199
}
200

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

Read our documentation on viewing source code .

Loading