Override the operation and scale the result of exactly one superclass call:
class ScaledSumChannel(factor: Int) extends SumChannel {
override def apply(n: Int): Int = factor * super.apply(n)
}The superclass updates its previous-input state once and returns its ordinary sum; only that returned value is scaled. The inputs and superclass history are unchanged by the scaling. Reimplementing the state update is unnecessary and could accidentally diverge from the superclass contract. As in the supplied channel, arithmetic uses the declared fixed-width integer type.
Fun[Base, Derived] can safely supply a Fun[Base, Base] contract; Fun[Base, Base] cannot in general supply a Fun[Base, Derived] contract. The input obligation is unchanged, while a derived result satisfies every base-result promise. This is the covariant output rule of function subtyping.With the invariant printed trait, implement the safe view explicitly:
def widenResult(f: Fun[Base, Derived]): Fun[Base, Base] =
new Fun[Base, Base] {
def apply(x: Base): Base = f(x)
}Using the illustrative classes from part i, an unsafe substitution would let a client assume a derived-only operation on a result that is merely a base software object:
val broadResult = new Fun[Base, Base] {
def apply(x: Base): Base = new Base
}
def derivedResultClient(f: Fun[Base, Derived]): Int =
f(new Base).special()
// derivedResultClient(broadResult) must be rejected.The direct, variance-aware object interface that would express both safe directions is
trait Fun[-S, +T] { def apply(x: S): T }. Its object method consumes the contravariant parameter and produces the covariant parameter. This is an explicitly proposed variant of the printed invariant declaration, not an assumption that its annotations were already present.A function accepting every
Base can safely be used where only Derived inputs will be supplied. The reverse direction is unsafe. A Derived argument is already a valid Base argument; restricting the possible callers introduces no new obligation for the function. This is the contravariant input rule of function subtyping.The printed trait has generic type invariance, so Scala does not directly permit either parameter-changing assignment. The safe behavior can be exposed using an explicit adapter without changing that trait:
def restrictInput(f: Fun[Base, Base]): Fun[Derived, Base] =
new Fun[Derived, Base] {
def apply(x: Derived): Base = f(x)
}For the unsafe direction, take illustrative classes in which a derived software object has an extra operation:
class Base
class Derived extends Base { def special(): Int = 1 }
val narrow = new Fun[Derived, Base] {
def apply(x: Derived): Base = { x.special(); x }
}
def broadClient(f: Fun[Base, Base]): Base = f(new Base)
// broadClient(narrow) must be rejected.If that substitution were accepted, the client could pass an ordinary base software object to code that calls
special, which that software object does not support. The rejected call is intentional counterexample code, not a promised compilable application. Variance annotations are needed to make sound direct conversions part of the generic trait's declared subtyping relation.[ref]Scala 2.13 variance annotations specification. Variance Annotations: missing annotation is invariant; method-input positions reverse variance
Reject the empty string because it has no positive total count to normalize:The support contains each occurring character once, and a character absent from the string gets mass zero. The occurrence counts sum to the nonzero string length, proving normalization. For a separate example, the string
final class DistFromString(s: String) extends FiniteDist[Char] {
require(s.nonEmpty)
private val frequencies =
s.foldLeft(Map.empty[Char, Int]) { (counts, c) =>
counts.updated(c, counts.getOrElse(c, 0) + 1)
}
def getDom: List[Char] = s.toList.distinct
def getProb(c: Char): Double =
frequencies.getOrElse(c, 0).toDouble / s.length.toDouble
}"aba" gives masses and to its two characters. The interpretation follows Scala's Char elements, so it counts UTF-16 code units rather than imposing a separate Unicode-code-point representation. The Double results approximate the corresponding rational probabilities.Use a widened interval width, so the arithmetic also handles endpoints near the limits of The support lists every integer in the inclusive interval once. Its cardinality is
Int:final class Uniform(l: Int, u: Int) extends FiniteDist[Int] {
require(l <= u)
private val width = u.toLong - l.toLong + 1L
def getDom: List[Int] = {
val builder = List.newBuilder[Int]
var value = l.toLong
while (value <= u.toLong) {
builder += value.toInt
value += 1L
}
builder.result()
}
def getProb(x: Int): Double =
if (l <= x && x <= u) 1.0 / width.toDouble else 0.0
}width, so assigning each atom mass gives total mass one. The loop counter is also widened, preventing an increment past Int.MaxValue from wrapping to a negative value. Returning the full support takes time and space proportional to its width and can be impractical for a very large interval; the mass query itself is constant-time. The full integer interval has width , which fits Long but not positive Int.Validate the parameter, and include exactly the outcomes of positive mass:The range test also rejects
final class Flip(p: Double) extends FiniteDist[Boolean] {
require(p >= 0.0 && p <= 1.0)
def getDom: List[Boolean] =
if (p == 0.0) List(false)
else if (p == 1.0) List(true)
else List(false, true)
def getProb(x: Boolean): Double = if (x) p else 1.0 - p
}NaN, since its ordered comparisons are false. At the endpoints one outcome has zero mass and must be omitted from the support; listing both unconditionally would violate the supplied interface contract. For an interior parameter the two masses are positive and sum to one.With that display format the output isThe first removal takes the newly prepended left value . The right removal later takes the most recently appended . The next left removal takes the earlier , leaving the ordered sequence . The two equal values are different occurrences, and the displayed order follows the links rather than numerical sorting.
20
10
10
Queue status: [30, 40, 15]Add this method inside the concrete class:Its precondition is a valid receiver, including an empty one. Its postcondition leaves and prints the entries of from left to right in the displayed bracket format, followed by a newline. The loop invariant says that the printed entries are precisely the chain before
def display: Unit = {
print("[")
var current = first
var separator = ""
while (current != null) {
print(separator)
print(current.datum)
separator = ", "
current = current.next
}
println("]")
}current; the not-yet-printed entries are the chain starting there. Advancing along the acyclic chain terminates after its length. Printing changes the output stream, but it changes neither links nor payloads.For , the success probability is , and the definition of conditional expectation on an event givesThereforeAt the value is zero because the trial has already ended. At the left absorbing state , conditioning on success would be undefined because it has zero probability. The formula concerns the successful trajectories, so it need not equal the unconditional mean .
Write and . Since , the latter expected value is finite. Conditional on the first move to or , total time is one plus the remaining time, while the terminal success indicator random variable is unchanged. The Markov property and linearity of expectation giveAt either absorbing boundary the remaining time is zero, so .
Let . The linear term has zero second difference and has second difference . Consequentlywhich is exactly the required recurrence, and . Uniqueness follows as before: the difference of two solutions has zero second difference and zero endpoint values. HenceThis is the success-weighted duration underlying the duration of gambler's ruin conditioned on a chosen boundary.
Let . Time is accumulated in each transient chamber before the next move; arrival at either terminal state ends the trial immediately. Thus . A block of identical rightward choices forces absorption, so the geometric tail bound from a uniform escape probability gives finite expected value of .
First-step analysis now givesThe quadratic has the correct boundary values and second difference , so it solves this system. The difference of two solutions would be linear in with zero values at both endpoints, hence zero. ThereforeThis is the expected duration of symmetric gambler's ruin. It includes the first minute in the starting transient chamber and does not add a minute after absorption.
The expected value of an indicator random variable is the probability of its event. For a simple symmetric random walk absorbed at , the gambler's ruin success probability from is . HenceThe boundary values are at the left exit and at chamber .
Choose . If has an exponential distribution with rate , then for ,while the integral diverges to when . Since has rate ,For the other two rates, , whereas . These computations establish exactly the required finite variance, finite expected value, and infinite expected value.
Compute all three probabilities. From the preceding part, . Integrating the joint probability density function over givesOn one has and , soTherefore and are independent events. The minimum waiting time and the identity of the first clock are independent for competing exponential clocks; unequal rates change the winner probabilities but do not destroy that independence.
Using the rate parameter convention for the exponential distribution, independence gives the joint probability density functionFor , the survival probability of the minimum isThus has exponential distribution with rate , andValues of a probability density function at the single endpoint do not affect the probability distribution.
Conditional on a contiguous red block, its possible starting positions remain equally likely because their original colour patterns had equal probabilities. The first card is red exactly when that block starts at position . HenceThis also follows by dividing the probability of the single favourable block position, , by the probability of all block positions.
The red positions form a uniformly chosen subset of size , so there are equally likely colour patterns. A contiguous red block can start at positions , giving exactly favourable patterns. ThereforeIf the cards are regarded as individually labelled, each colour pattern corresponds to permutations, so the same counting argument still applies. In the edge case , the formula correctly gives probability one.
Let be the two red-card events. Sampling without replacement givesThis differs from the product , sinceThus the events are not independent, for every positive . A first red card reduces the remaining red fraction, a basic instance of how sampling without replacement need not be independent.
Every position in the random permutation has the same marginal colour probability, so . One can verify this with the law of total probability, conditioning on the first card:Here because both colour counts are positive.
There are unlisted articles, also show them or only show them.