typelevel / algebra
1
package algebra
2
package laws
3

4
import algebra.ring._
5

6
import algebra.laws.platform.Platform
7

8
import org.typelevel.discipline.Predicate
9

10
import org.scalacheck.{Arbitrary, Prop}
11
import org.scalacheck.Arbitrary._
12
import org.scalacheck.Prop._
13

14
object RingLaws {
15
  def apply[A : Eq : Arbitrary: AdditiveMonoid]: RingLaws[A] =
16 3
    withPred[A](new Predicate[A] {
17
      def apply(a: A): Boolean = Eq[A].neqv(a, AdditiveMonoid[A].zero)
18
    })
19

20 3
  def withPred[A: Eq: Arbitrary](pred0: Predicate[A]): RingLaws[A] = new RingLaws[A] {
21 3
    def Arb = implicitly[Arbitrary[A]]
22
    def pred = pred0
23 3
    val nonZeroLaws = new GroupLaws[A] {
24 3
      def Arb = Arbitrary(arbitrary[A] filter pred)
25 3
      def Equ = Eq[A]
26
    }
27
  }
28
}
29

30
trait RingLaws[A] extends GroupLaws[A] { self =>
31

32
  // must be a val (stable identifier)
33
  val nonZeroLaws: GroupLaws[A]
34
  def pred: Predicate[A]
35

36
  def withPred(pred0: Predicate[A], replace: Boolean = true): RingLaws[A] =
37 0
    RingLaws.withPred(if (replace) pred0 else pred && pred0)(Equ, Arb)
38

39
  def setNonZeroParents(props: nonZeroLaws.GroupProperties, parents: Seq[nonZeroLaws.GroupProperties]): nonZeroLaws.GroupProperties =
40 3
    new nonZeroLaws.GroupProperties(
41 3
      name = props.name,
42
      parents = parents,
43 3
      props = props.props: _*
44
    )
45

46
  implicit def Arb: Arbitrary[A]
47 3
  implicit def Equ: Eq[A] = nonZeroLaws.Equ
48

49
  // additive groups
50

51 3
  def additiveSemigroup(implicit A: AdditiveSemigroup[A]) = new AdditiveProperties(
52 3
    base = semigroup(A.additive),
53 3
    parents = Nil,
54 3
    Rules.serializable(A),
55 3
    Rules.repeat1("sumN")(A.sumN),
56 3
    Rules.repeat2("sumN", "+")(A.sumN)(A.plus)
57
  )
58

59 0
  def additiveCommutativeSemigroup(implicit A: AdditiveCommutativeSemigroup[A]) = new AdditiveProperties(
60 0
    base = commutativeSemigroup(A.additive),
61 0
    parents = List(additiveSemigroup)
62
  )
63

64 3
  def additiveMonoid(implicit A: AdditiveMonoid[A]) = new AdditiveProperties(
65 3
    base = monoid(A.additive),
66 3
    parents = List(additiveSemigroup),
67 3
    Rules.repeat0("sumN", "zero", A.zero)(A.sumN),
68 3
    Rules.collect0("sum", "zero", A.zero)(A.sum)
69
  )
70

71 3
  def additiveCommutativeMonoid(implicit A: AdditiveCommutativeMonoid[A]) = new AdditiveProperties(
72 3
    base = commutativeMonoid(A.additive),
73 3
    parents = List(additiveMonoid)
74
  )
75

76 3
  def additiveGroup(implicit A: AdditiveGroup[A]) = new AdditiveProperties(
77 3
    base = group(A.additive),
78 3
    parents = List(additiveMonoid),
79 3
    Rules.consistentInverse("subtract")(A.minus)(A.plus)(A.negate)
80
  )
81

82 3
  def additiveCommutativeGroup(implicit A: AdditiveCommutativeGroup[A]) = new AdditiveProperties(
83 3
    base = commutativeGroup(A.additive),
84 3
    parents = List(additiveGroup)
85
  )
86

87
  // multiplicative groups
88

89 3
  def multiplicativeSemigroup(implicit A: MultiplicativeSemigroup[A]) = new MultiplicativeProperties(
90 3
    base = semigroup(A.multiplicative),
91 3
    nonZeroBase = None,
92 3
    parent = None,
93 3
    Rules.serializable(A),
94 3
    Rules.repeat1("pow")(A.pow),
95 3
    Rules.repeat2("pow", "*")(A.pow)(A.times)
96
  )
97

98 3
  def multiplicativeCommutativeSemigroup(implicit A: MultiplicativeCommutativeSemigroup[A]) = new MultiplicativeProperties(
99 3
    base = semigroup(A.multiplicative),
100 3
    nonZeroBase = None,
101 3
    parent = Some(multiplicativeSemigroup)
102
  )
103

104 3
  def multiplicativeMonoid(implicit A: MultiplicativeMonoid[A]) = new MultiplicativeProperties(
105 3
    base = monoid(A.multiplicative),
106 3
    nonZeroBase = None,
107 3
    parent = Some(multiplicativeSemigroup),
108 3
    Rules.repeat0("pow", "one", A.one)(A.pow),
109 3
    Rules.collect0("product", "one", A.one)(A.product)
110
  )
111

112 3
  def multiplicativeCommutativeMonoid(implicit A: MultiplicativeCommutativeMonoid[A]) = new MultiplicativeProperties(
113 3
    base = commutativeMonoid(A.multiplicative),
114 3
    nonZeroBase = None,
115 3
    parent = Some(multiplicativeMonoid)
116
  )
117

118 3
  def multiplicativeGroup(implicit A: MultiplicativeGroup[A]) = new MultiplicativeProperties(
119 3
    base = monoid(A.multiplicative),
120 3
    nonZeroBase = Some(setNonZeroParents(nonZeroLaws.group(A.multiplicative), Nil)),
121 3
    parent = Some(multiplicativeMonoid),
122
    // pred is used to ensure y is not zero.
123 3
    "consistent division" -> forAll { (x: A, y: A) =>
124 3
      pred(y) ==> (A.div(x, y) ?== A.times(x, A.reciprocal(y)))
125
    }
126
  )
127

128 3
  def multiplicativeCommutativeGroup(implicit A: MultiplicativeCommutativeGroup[A]) = new MultiplicativeProperties(
129 3
    base = commutativeMonoid(A.multiplicative),
130 3
    nonZeroBase = Some(setNonZeroParents(nonZeroLaws.commutativeGroup(A.multiplicative), multiplicativeGroup.nonZeroBase.toSeq)),
131 3
    parent = Some(multiplicativeGroup)
132
  )
133

134
  // rings
135

136 3
  def semiring(implicit A: Semiring[A]) = new RingProperties(
137 3
    name = "semiring",
138 3
    al = additiveCommutativeMonoid,
139 3
    ml = multiplicativeSemigroup,
140 3
    parents = Seq.empty,
141 3
    Rules.distributive(A.plus)(A.times)
142
  )
143

144 3
  def rng(implicit A: Rng[A]) = new RingProperties(
145 3
    name = "rng",
146 3
    al = additiveCommutativeGroup,
147 3
    ml = multiplicativeSemigroup,
148 3
    parents = Seq(semiring)
149
  )
150

151 3
  def rig(implicit A: Rig[A]) = new RingProperties(
152 3
    name = "rig",
153 3
    al = additiveCommutativeMonoid,
154 3
    ml = multiplicativeMonoid,
155 3
    parents = Seq(semiring)
156
  )
157

158 3
  def ring(implicit A: Ring[A]) = new RingProperties(
159
    // TODO fromParents
160 3
    name = "ring",
161 3
    al = additiveCommutativeGroup,
162 3
    ml = multiplicativeMonoid,
163 3
    parents = Seq(rig, rng),
164 3
    "fromInt" -> forAll { (n: Int) =>
165 3
      Ring.fromInt[A](n) ?== A.sumN(A.one, n)
166
    },
167 3
    "fromBigInt" -> forAll { (ns: List[Int]) =>
168 3
      val actual = Ring.fromBigInt[A](ns.map(BigInt(_)).foldLeft(BigInt(1))(_ * _))
169 3
      val expected = ns.map(A.fromInt).foldLeft(A.one)(A.times)
170 3
      actual ?== expected
171
    }
172
  )
173

174
  // commutative rings
175

176 3
  def commutativeSemiring(implicit A: CommutativeSemiring[A]) = new RingProperties(
177 3
    name = "commutativeSemiring",
178 3
    al = additiveCommutativeMonoid,
179 3
    ml = multiplicativeCommutativeSemigroup,
180 3
    parents = Seq(semiring)
181
  )
182

183 3
  def commutativeRng(implicit A: CommutativeRng[A]) = new RingProperties(
184 3
    name = "commutativeRng",
185 3
    al = additiveCommutativeMonoid,
186 3
    ml = multiplicativeCommutativeSemigroup,
187 3
    parents = Seq(rng, commutativeSemiring)
188
  )
189

190 3
  def commutativeRig(implicit A: CommutativeRig[A]) = new RingProperties(
191 3
    name = "commutativeRig",
192 3
    al = additiveCommutativeMonoid,
193 3
    ml = multiplicativeCommutativeMonoid,
194 3
    parents = Seq(rig, commutativeSemiring)
195
  )
196

197 3
  def commutativeRing(implicit A: CommutativeRing[A]) = new RingProperties(
198 3
    name = "commutative ring",
199 3
    al = additiveCommutativeGroup,
200 3
    ml = multiplicativeCommutativeMonoid,
201 3
    parents = Seq(ring, commutativeRig, commutativeRng)
202
  )
203

204
  // boolean rings
205

206 3
  def boolRng(implicit A: BoolRng[A]) = RingProperties.fromParent(
207 3
    name = "boolean rng",
208 3
    parent = commutativeRng,
209 3
    Rules.idempotence(A.times)
210
  )
211

212 3
  def boolRing(implicit A: BoolRing[A]) = RingProperties.fromParent(
213 3
    name = "boolean ring",
214 3
    parent = commutativeRing,
215 3
    Rules.idempotence(A.times)
216
  )
217

218
  // Everything below fields (e.g. rings) does not require their multiplication
219
  // operation to be a group. Hence, we do not check for the existence of an
220
  // inverse. On the other hand, fields require their multiplication to be an
221
  // abelian group. Now we have to worry about zero.
222
  //
223
  // The usual text book definition says: Fields consist of two abelian groups
224
  // (set, +, zero) and (set \ zero, *, one). We do the same thing here.
225
  // However, since law checking for the multiplication does not include zero
226
  // any more, it is not immediately clear that desired properties like
227
  // zero * x == x * zero hold.
228
  // Luckily, these follow from the other field and group axioms.
229 3
  def field(implicit A: Field[A]) = new RingProperties(
230 3
    name = "field",
231 3
    al = additiveCommutativeGroup,
232 3
    ml = multiplicativeCommutativeGroup,
233 3
    parents = Seq(commutativeRing),
234 3
    "fromDouble" -> forAll { (n: Double) =>
235 3
      if (Platform.isJvm) {
236
        // TODO: BigDecimal(n) is busted in scalajs, so we skip this test.
237 3
        val bd = new java.math.BigDecimal(n)
238 3
        val unscaledValue = new BigInt(bd.unscaledValue)
239
        val expected =
240 3
          if (bd.scale > 0) {
241 3
            A.div(A.fromBigInt(unscaledValue), A.fromBigInt(BigInt(10).pow(bd.scale)))
242
          } else {
243 3
            A.fromBigInt(unscaledValue * BigInt(10).pow(-bd.scale))
244
          }
245 3
        Field.fromDouble[A](n) ?== expected
246
      } else {
247 0
        Prop(true)
248
      }
249
    }
250
  )
251

252
  // property classes
253

254
  class AdditiveProperties(
255
    val base: GroupLaws[A]#GroupProperties,
256
    val parents: Seq[AdditiveProperties],
257
    val props: (String, Prop)*
258
  ) extends RuleSet {
259 3
    val name = "additive " + base.name
260 3
    val bases = List("base" -> base)
261
  }
262

263
  class MultiplicativeProperties(
264
    val base: GroupLaws[A]#GroupProperties,
265
    val nonZeroBase: Option[nonZeroLaws.GroupProperties],
266
    val parent: Option[MultiplicativeProperties],
267
    val props: (String, Prop)*
268
  ) extends RuleSet with HasOneParent {
269 3
    val name = "multiplicative " + base.name
270 3
    val bases = Seq("base" -> base) ++ nonZeroBase.map("non-zero base" -> _)
271
  }
272

273
  object RingProperties {
274
    def fromParent(name: String, parent: RingProperties, props: (String, Prop)*) =
275 3
      new RingProperties(name, parent.al, parent.ml, Seq(parent), props: _*)
276
  }
277

278
  class RingProperties(
279
    val name: String,
280
    val al: AdditiveProperties,
281
    val ml: MultiplicativeProperties,
282
    val parents: Seq[RingProperties],
283
    val props: (String, Prop)*
284
  ) extends RuleSet {
285 3
    def bases = Seq("additive" -> al, "multiplicative" -> ml)
286
  }
287
}

Read our documentation on viewing source code .

Loading