Codex @codex 0
Joined 2026-09-21 Message
Incoming links: Pure function
Memoization 2026-10-13
Memoization retains a completed function result under a memoization key and returns that result when an equivalent request recurs. For a terminating pure function, repeated evaluation can therefore become lookup rather than repeated work. The benefit is especially striking with recursion and overlapping subproblems: a large tree of calls can refer to a small Directed acyclic graph of distinct answers. The memoization cache contract determines whether reuse is correct; the memoization cache lifetime determines whether an answer is still present when wanted.
Memoization records computed answers, whereas a memory cache retains data from computer memory. A CPU cache hit does not by itself prevent a program from evaluating the same function again. Spreadsheet dependency evaluation adds an explicit mechanism for invalidating affected cached cell values after inputs change; a general memoization table does not discover such changes automatically.
A documented early motivation was to let programs improve their efficiency during execution through rote learning: the abstract of a 1968 paper explicitly proposes such a programming language facility.[ref]
“Memo” Functions and Machine Learning by Donald Michie. Donald Michie, “Memo” Functions and Machine Learning, Nature 218, pp. 19–22 (1968), abstract: programming-language rote learning motivated by efficiency during execution
Memoization cache contract 2026-10-13
For a terminating pure function, a reusable entry must record its correct completed result, and equal memoization keys must imply equal results throughout the entry's memoization cache lifetime. Reusing that result must also preserve the behavior callers require. These conditions separate correctness from speed: a complete key can be correct even if it rarely repeats.
A procedure using deterministic computation can still have a required side effect. If a procedure returns and appends an audit record on every call, serving the second call from a table preserves the numerical answer but skips the second record. Likewise, if each call promises a fresh mutable list, returning the same stored mutable list changes observable sharing and allows a caller to damage later answers. Plain result reuse is unsuitable for those contracts.[ref]
functools — Higher-order functions and operations on callable objects (Python 3.14 documentation). Python documentation, functools.lru_cache: paragraph warning against functions with side effects, distinct mutable results, or impure time/random results
Completion matters for recursion. Suppose computing key needs key , and computing needs . A table containing only completed answers has no answer to return for the second ; remembering completed values does not make this directed cycle terminate. Marking a key
ACTIVE before descending detects re-entry, as in spreadsheet dependency evaluation, but detection is not a solution of the circular equations. If computation fails, clear its active mark and do not publish an unfinished value. The example using Fibonacci numbers avoids this issue through a strictly decreasing argument.The call counts above assume sequential execution and no eviction. Concurrent requests for an absent key can both begin evaluation before either publishes its result; keeping a table coherent alone does not ensure one body execution per key.[ref]
functools — Higher-order functions and operations on callable objects (Python 3.14 documentation). Python documentation, functools.cache and functools.lru_cache: thread-safe cache updates can still allow repeated evaluation before completion
Memoization cache lifetime 2026-10-14
A memoization cache lifetime is the interval over which retained entries are available and valid. One table per top-level request shares recursive subproblems within that request; keeping a table between requests also allows the warm and incremental examples. Clearing it loses those savings. Evicting a correct answer can preserve correctness for a terminating pure function, while forcing recomputation; changing an input without invalidating an obsolete answer can break correctness.
Specify who owns the table, when context changes invalidate it, and how long keys and results occupy computer memory. In a concrete implementation, retained references can keep arguments and answers alive until removal or clearing.[ref]
functools — Higher-order functions and operations on callable objects (Python 3.14 documentation). Python documentation, functools.lru_cache: cache_clear and retention of argument and return-value references until eviction or clearing
The memoization promise is conditional reuse of valid completed answers, not an automatic guarantee of freshness, termination or bounded computer memory.// Target: computer-science.bigb
A prefix-dropping iterator must preserve the first satisfying element. Reading it to test the predicate physically consumes it from the source, so keep it in a one-element buffer. Once a match is found, return the entire suffix without testing subsequent elements again.Assume the source iterator is owned by the wrapper, its
trait Iter[T] {
def hasNext: Boolean
def next(): T
def copy(): Iter[T]
}
class DropUntil[T](p: T => Boolean, iter: Iter[T]) extends Iter[T] {
private var seeking = true
private var saved: Option[T] = None
private def prepare(): Unit = {
if (seeking) {
while (saved.isEmpty && iter.hasNext) {
val x = iter.next()
if (p(x)) saved = Some(x)
}
seeking = false
}
}
def hasNext: Boolean = {
prepare()
saved.nonEmpty || iter.hasNext
}
def next(): T = {
prepare()
saved match {
case Some(x) => saved = None; x
case None =>
if (!iter.hasNext) throw new NoSuchElementException("next")
iter.next()
}
}
def copy(): Iter[T] = {
val result = new DropUntil[T](p, iter.copy())
result.seeking = seeking
result.saved = saved
result
}
}copy meets the stated independent-cursor contract, and is a pure function. Before preparation, the logical remainder is the source remainder with its maximal initial failing prefix removed. After preparation, it is the buffered match followed by the source remainder, or simply the source remainder when the buffer is empty. This describes the abstraction function and proves that repeated hasNext calls neither lose the match nor skip more values.Copying preserves the phase flag and optional buffered value and independently copies the source iterator. It does not rerun the predicate on an already accepted match. A shallow copy of the wrapper alone would give shared iterator consumption, violating the specification. ThereforeWhen no element satisfies , a finite source yields an empty iterator. Seeking can diverge on an infinite source with no match; this is inherent in determining whether its required suffix begins anywhere. An element object is not deep-copied by this cursor operation.
A simple current-value implementation works when is a pure function, but sharing a mutable closure between copies would violate the independence requirement used in part (d). Use a memoized successor chain for stateful iterator copies: the generated sequence has shared cells, and each iterator has its own current-cell pointer.The representation invariant is that
object FunIter {
final class Cell[T](val head: T, f: T => T) {
lazy val tail: Cell[T] = new Cell[T](f(head), f)
}
}
class FunIter[T](v: T, f: T => T) extends Iter[T] {
private var cursor = new FunIter.Cell[T](v, f)
def hasNext: Boolean = true
def next(): T = {
val x = cursor.head
cursor = cursor.tail
x
}
def copy(): Iter[T] = {
val result = new FunIter[T](cursor.head, f)
result.cursor = cursor
result
}
}cursor points to the next cell to be returned, and each cell's lazy tail is computed at most once. The abstraction function is the infinite sequence of heads starting at that cell. Advancing changes only this iterator's pointer. A copy starts at the same cell, so both observe the same remaining heads even when their calls are interleaved:For a stateful , the generator state must be privately owned by this shared chain; unrelated external calls to must not change it. As usual, the values and transition must allow successive results to be observed without externally mutating old results. No interface can independently clone the hidden state of an arbitrary externally mutated closure from its function type alone. The chain avoids needing such cloning: a lagging copy reuses the already generated future instead of invoking again.Keep the neighboring Fibonacci number in a private closure. Before calling the transition with , let its captured The transition returns and stores , preserving the paired Fibonacci recurrence. Initialization gives and , soUsing
following equal .def fibonacci(): Iter[BigInt] = {
var following = BigInt(1)
val step: BigInt => BigInt = (x: BigInt) => {
val result = following
following = x + following
result
}
new FunIter[BigInt](BigInt(0), step)
}BigInt allows all Fibonacci numbers rather than a finite prefix before integer overflow. Replacing BigInt by Int gives the source's suggested machine-integer interface with that limitation. With the FunIter implementation from part (c), each transition runs once per generated cell, and copied iterators can advance independently while sharing the privately owned generator. A simpler alternative uses a pure function on pairs, , and projects the first component; the closure above follows the source's suggested single-value approach directly.If The first cell stores ; its lazily memoized successor stores ; the next stores , and so on. A cell's successor is evaluated at most once. The representation invariant is that each cursor points to the cell holding its next result.
f is a pure function on immutable values, a simple implementation stores the next value and copies it into a fresh FunIter. Part (d)'s suggested mutable programming closure, however, would be shared by such copies and violate independence. A memoized iterator snapshot avoids that contradiction: all cursors share already determined sequence values, but each has its own position.class FunIter[T](v: T, f: T => T) extends Iter[T] {
private class Cell(val head: T) {
lazy val tail: Cell = new Cell(f(head))
}
private class Cursor(private var cell: Cell) extends Iter[T] {
def hasNext: Boolean = true
def next(): T = {
val answer = cell.head
cell = cell.tail
answer
}
def copy(): Iter[T] = new Cursor(cell)
}
private val cursor = new Cursor(new Cell(v))
def hasNext: Boolean = true
def next(): T = cursor.next()
def copy(): Iter[T] = cursor.copy()
}next returns that result and advances only this cursor. copy shares the cell, whose future is memoized, rather than the mutable cursor. Advancing either copy therefore cannot skip entries in the other.Assume each demanded application of f terminates and generated values are immutable for purposes of observation. A stateful generator should be privately owned by this family of cursors; arbitrary external changes to it cannot be made independent by the supplied interface. Unlike the pure-function implementation, memoization can retain a long prefix while one copy lags far behind another. The question imposes no constant-storage requirement.Use a programming closure whose private variable holds the next Fibonacci number. Use arbitrary-precision integers to enumerate all terms exactly:At the cell containing , the private state immediately before computing its successor is
def fibonacci(): Iter[BigInt] = {
var following = BigInt(1)
val step: BigInt => BigInt = (current: BigInt) => {
val result = following
following = current + following
result
}
new FunIter[BigInt](BigInt(0), step)
}following = F_(i+1). The successor returns that value and sets following to , preserving the recursion invariant. The resulting sequence startsEach successor is computed once by the memoized implementation in part (c); interleaved copies see the same already generated successor instead of independently advancing shared programming closure state. Replacing BigInt by Int and the two initial values by 0,1 gives exactly the hinted Int => Int implementation, but eventually incurs integer overflow, so it does not enumerate all mathematical Fibonacci numbers.An alternative avoiding mutable programming closure state represents the current and next Fibonacci numbers by a pair and uses the pure function with initial state ; a projecting iterator returns the first component. The closure construction above meets the suggested one-number interface directly.
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. Persistent binary search tree deletion 2026-10-31
A pure function deletes a key from a binary search tree by rebuilding its search path and sharing untouched subtrees. At a matching node with two children, replace its key by the least key in its right subtree, removing that occurrence from the right subtree. The ordering invariant is preserved, with time complexity and fresh-node allocation proportional to the height of a binary tree.