Programming language polymorphism lets one expression or operation work with values of different types or concrete representations. In object-oriented programming, subtype polymorphism lets a reference of an interface or superclass type designate instances of different implementing software classes. A call through that reference uses dynamic dispatch to select the receiver's overriding object method. For example, a routine taking
Book can invoke recall on a linked-list or an array-based implementation while depending only on the common abstract contract.Parametric polymorphism is another form: the type parameter in
FiniteDist[T] lets the same interface describe distributions over Booleans, integers or characters. A generic method introduces a further type parameter when its output type differs. Method overloading, in contrast, supplies several statically selected signatures with one name; it should not be confused with receiver-dependent dynamic dispatch. Correct substitutability also requires implementations to respect the common behavioral contract, not merely to share method names.Implement the Bernoulli distribution, taking special care that a zero-mass outcome is excluded from the support of a probability distribution:The precondition excludes NaN and all values outside , including infinities. The two masses are nonnegative and sum mathematically to one. Endpoint domains are singleton lists, while an interior parameter lists both outcomes exactly once. Treating
class Flip(p: Double) extends FiniteDist[Boolean] {
require(!p.isNaN && 0.0 <= p && p <= 1.0)
def getDom: List[Boolean] =
if (p == 0.0) List(false)
else if (p == 1.0) List(true)
else List(true, false)
def getProb(x: Boolean): Double =
if (x) p else 1.0 - p
}getDom as always containing both Booleans would violate its positive-support contract at the endpoints.The inclusive interval is nonempty exactly when . Reject with a failed precondition, rather than assigning a nonexistent normalization to an empty interval. Compute its width in The loop invariant says that and
Long before taking a reciprocal:class Uniform(l: Int, u: Int) extends FiniteDist[Int] {
require(l <= u, "Empty uniform interval")
private val width = u.toLong - l.toLong + 1L
private val mass = 1.0 / width.toDouble
def getProb(x: Int): Double =
if (l <= x && x <= u) mass else 0.0
def getDom: List[Int] = {
var x = l.toLong
var rev = List.empty[Int]
while (x <= u.toLong) {
rev = x.toInt :: rev
x += 1L
}
rev.reverse
}
}rev contains exactly the integers in reverse order. The loop variant is while the guard is true. Long handles both the full interval width and the increment past Int.MaxValue. At exit, reversing yields each support value once. All support values have mass , so their exact sum is one; Double approximates that rational number. Very large valid domains require correspondingly large lists and sufficient memory; that resource issue does not make the mathematical endpoint values invalid.Use relative character frequencies, an empirical distribution. A nonempty string is required because an empty sample has no normalized frequency distribution:
class DistFromString(s: String) extends FiniteDist[Char] {
require(s != null && s.nonEmpty, "A nonempty string is required")
private val chars = s.toList
private val domain = chars.distinct
def getDom: List[Char] = domain
def getProb(c: Char): Double =
chars.count(_ == c).toDouble / s.length.toDouble
}distinct removes repeated support entries without changing which characters occur. Every returned domain element has positive frequency, and every absent character has frequency zero. The occurrence counts partition the string's character positions, so their total is s.length, establishing normalization. For Scala, the masses are for a and each for S, c and l. The character units here are exactly the Char values supplied by s.toList; the interface does not specify a different notion of displayed text characters. The code has no explicit loop beyond the specified library traversals.Add the following concrete method inside The input finite probability distribution is assumed to satisfy its interface, with stable masses during construction, and
FiniteDist[T]. It forms a pushforward of a finite probability distribution, adding the masses of outcomes that map to the same result:def map[U](f: T => U): FiniteDist[U] = {
val source = getDom
val weighted = source.map(x => (f(x), getProb(x)))
val target = weighted.map(_._1).distinct
new FiniteDist[U] {
def getDom: List[U] = target
def getProb(y: U): Double =
weighted.filter(pair => pair._1 == y).map(_._2).sum
}
}f must be a total deterministic pure function on its finite support. Output values need stable equality consistent with the mathematical equality being modeled; mutating equality-relevant fields afterwards would undermine any finite-support implementation. Computing weighted once also prevents later queries from re-evaluating f inconsistently.Every source support element appears once in
weighted. The distinct operation lists each image value once; every such image has a positive mathematical mass because it has a positive-mass preimage. For each , filtering selects exactly those with , so getProb(y) is the required sum, with an empty sum of zero off the image. The fibers form a set partition of the original support, givingThus colliding images have their probabilities added, not overwritten. For a concrete check, mapping a uniform distribution on by parity gives probability to each of ; mapping every source value to one constant gives a singleton domain with total mass one. Floating-point rounding can make a computed total differ slightly from one; the proof is for exact mathematical masses, and the representation uses Double approximations. Articles by others on the same topic
There are currently no matching articles.