typelevel / algebra
1
package algebra
2
package lattice
3

4
import ring.BoolRng
5
import scala.{specialized => sp}
6

7
/**
8
 * Generalized Boolean algebra, that is, a Boolean algebra without
9
 * the top element. Generalized Boolean algebras do not (in general)
10
 * have (absolute) complements, but they have ''relative complements''
11
 * (see [[GenBool.without]]).
12
 */
13
trait GenBool[@sp(Int, Long) A] extends Any with DistributiveLattice[A] with BoundedJoinSemilattice[A] { self =>
14
  def and(a: A, b: A): A
15 2
  override def meet(a: A, b: A): A = and(a, b)
16

17
  def or(a: A, b: A): A
18 2
  override def join(a: A, b: A): A = or(a, b)
19

20
  /**
21
   * The operation of ''relative complement'', symbolically often denoted
22
   * `a\b` (the symbol for set-theoretic difference, which is the
23
   * meaning of relative complement in the lattice of sets).
24
   */
25
  def without(a: A, b: A): A
26

27
  /**
28
   * Logical exclusive or, set-theoretic symmetric difference.
29
   * Defined as `a\b ∨ b\a`.
30
   */
31 2
  def xor(a: A, b: A): A = or(without(a, b), without(b, a))
32

33
  /**
34
   * Every generalized Boolean algebra is also a `BoolRng`, with
35
   * multiplication defined as `and` and addition defined as `xor`.
36
   */
37 2
  def asBoolRing: BoolRng[A] = new BoolRngFromGenBool(self)
38
}
39

40
/**
41
 * Every Boolean rng gives rise to a Boolean algebra without top:
42
 *  - 0 is preserved;
43
 *  - ring multiplication (`times`) corresponds to `and`;
44
 *  - ring addition (`plus`) corresponds to `xor`;
45
 *  - `a or b` is then defined as `a xor b xor (a and b)`;
46
 *  - relative complement `a\b` is defined as `a xor (a and b)`.
47
 *
48
 * `BoolRng.asBool.asBoolRing` gives back the original `BoolRng`.
49
 *
50
 * @see [[algebra.lattice.GenBool.asBoolRing]]
51
 */
52
class GenBoolFromBoolRng[A](orig: BoolRng[A]) extends GenBool[A] {
53 2
  def zero: A = orig.zero
54 2
  def and(a: A, b: A): A = orig.times(a, b)
55 2
  def or(a: A, b: A): A = orig.plus(orig.plus(a, b), orig.times(a, b))
56 2
  def without(a: A, b: A): A = orig.plus(a, orig.times(a, b))
57 0
  override def asBoolRing: BoolRng[A] = orig
58
}
59

60
private[lattice] class BoolRngFromGenBool[@sp(Int, Long) A](orig: GenBool[A]) extends BoolRng[A] {
61 2
  def zero: A = orig.zero
62 2
  def plus(x: A, y: A): A = orig.xor(x, y)
63 2
  def times(x: A, y: A): A = orig.and(x, y)
64
}
65

66
trait GenBoolFunctions[G[A] <: GenBool[A]] extends BoundedJoinSemilatticeFunctions[G] with MeetSemilatticeFunctions[G] {
67 0
  def and[@sp(Int, Long) A](x: A, y: A)(implicit ev: G[A]): A = ev.and(x, y)
68 0
  def or[@sp(Int, Long) A](x: A, y: A)(implicit ev: G[A]): A = ev.or(x, y)
69 0
  def without[@sp(Int, Long) A](x: A, y: A)(implicit ev: G[A]): A = ev.without(x, y)
70 0
  def xor[@sp(Int, Long) A](x: A, y: A)(implicit ev: G[A]): A = ev.xor(x, y)
71
}
72

73
object GenBool extends GenBoolFunctions[GenBool] {
74
  @inline final def apply[@sp(Int, Long) A](implicit ev: GenBool[A]): GenBool[A] = ev
75
}

Read our documentation on viewing source code .

Loading