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 .