DEV Community: William Lewis

Pretty-Printing is Compilation

William Lewis — Thu, 31 Oct 2024 12:27:41 +0000

Wadler's A Prettier Printer is a classic functional pearl. Someday I hope to understand it. Whether due to Haskell's laziness or my own—I struggled to reimplement his ideas in other languages (or even in Haskell, five minutes after reading the paper). Thankfully, Lindig recognized this problem and brought fire to the masses in Strictly Pretty. Yet even that wasn't dumbed-down enough for me.

But after spending some more time tinkering with the ideas from both papers, I think I finally get the picture.

Overview

As the title suggests, we'll think of pretty-printing as a process of compilation (and execution) of programs written in an abstract "document language". Like most programming languages, this document language—which we'll call
Doc—features expressions that can be composed together; this makes it easy for humans to reason about. We'll compile expressions in Doc to instructions in a kind of assembly language (ASM). Instructions in ASM are much easier to transform into strings.

Here's a schematic view of the process:

As a concrete example, suppose we want to pretty-print the nested list:

['onions', ['carrots', 'celery'], 'turnips']

Here's a Doc program for doing so:

group(
    '['
    + nest(
        4,
        br()
        + "'onions'"
        + ','
        + br(' ')
        + group(
            '['
            + nest(4, br() + "'carrots'" + ',' + br(' ') + "'celery'")
            + br()
            + ']'
        )
        + ','
        + br(' ')
        + "'turnips'"
    )
    + br()
    + ']'
)

We'll meet group, nest, etc. shortly. For now it's enough to get a general feel for the document language.

This program is then compiled (with certain "architectural parameters" set) into the ASM instructions:

TEXT '['
LINE 4
TEXT "'onions'"
TEXT ','
LINE 4
TEXT '['
TEXT ''
TEXT "'carrots'"
TEXT ','
TEXT ' '
TEXT "'celery'"
TEXT ''
TEXT ']'
TEXT ','
LINE 4
TEXT "'turnips'"
LINE 0
TEXT ']'

which are then interpreted as a string:

[
    'onions',
    ['carrots', 'celery'],
    'turnips'
]

One important feature alluded to above is that the compiler has a configurable "architectural parameter", which is a target maximum line width. Depending on the value of this parameter, the compiler will emit different ASM instructions for the same Doc program. In the example above we used a target width of 30. If we'd used 20 instead, the emitted assembly instructions would be different, as would the resulting string:

[
    'onions',
    [
        'carrots',
        'celery'
    ],
    'turnips'
]

And if we'd used 60, it would be:

['onions', ['carrots', 'celery'], 'turnips']

Printer Assembly Language

The assembly language is straightforward, so we'll tackle it first. We'll think of ASM instructions as controlling a really simple printing device that's only capable of doing two things:

Emitting a string of text.
Advancing to the next line, and indenting by a certain amount.

Hence ASM consists of only two instructions:

TEXT <text>, which emits a string of text.
LINE <indent>, which advances the printer to the next line, and then indents by indent spaces.

ASM programs are interpreted as strings by executing their instructions, one after the other. As an example, let's trace the execution of the program:

TEXT 'hello'
LINE 2
TEXT 'indented'
TEXT ' world'
LINE 0
TEXT 'goodbye'

We'll use a > to indicate the instruction being executed, and display the current output below. The ^ character will indicate the current location of the "printer head". We'll also use _ characters to indicate spaces, since these are otherwise difficult to track.

The first TEXT instruction causes the string 'hello' to be emitted:

> TEXT 'hello'
  LINE 2
  TEXT 'indented'
  TEXT ' world'
  LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
     ^

LINE 2 then advances to the next line and indents the head by 2 spaces:

  TEXT 'hello'
> LINE 2
  TEXT 'indented'
  TEXT ' world'
  LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
__
  ^

Then TEXT 'indented' causes 'indented' to be added:

  TEXT 'hello'
  LINE 2
> TEXT 'indented'
  TEXT ' world'
  LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
__indented
          ^

Followed by ' world', due to TEXT ' world':

  TEXT 'hello'
  LINE 2
  TEXT 'indented'
> TEXT ' world'
  LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
__indented world
                ^

LINE 0 advances the printer to the next line (and doesn't indent at all):

  TEXT 'hello'
  LINE 2
  TEXT 'indented'
  TEXT ' world'
> LINE 0
  TEXT 'goodbye'

== OUTPUT ==

hello
__indented world

^

And finally, TEXT 'goodbye' emits 'goodbye':

  TEXT 'hello'
  LINE 2
  TEXT 'indented'
  TEXT ' world'
  LINE 0
> TEXT 'goodbye'

== OUTPUT ==

hello
__indented world
goodbye
       ^

We'll represent ASM instructions as a "sum type":

TEXT instructions will be represented by Python strs.
LINE instructions will be represented by ints.

That is:

AsmInst = str | int

Interpreting a list of AsmInsts into the string they represent is just a matter of iterating over the instructions and "doing the right thing":

def interpret(insts: list[AsmInst]) -> str:
    """Interpret the ASM instructions as a string."""
    result = ""
    for inst in insts:
        match inst:
            case text if isinstance(text, str):
                result += inst
            case indent if isinstance(indent, int):
                result += f"\n{' ' * indent}"
    return result

For TEXT instructions, the interpreter appends the text to the result; for LINE instructions, the interpreter appends a newline ('\n') followed by indent spaces.

We can test interpret with the ASM instructions from the example above, translated into Python:

insts = ["hello", 2, "indented", " world", 0, "goodbye"]

print(interpret(insts))
# hello
#   indented world
# goodbye

The Doc Language (Teaser)

We like ASM because it's easy to interpret. But it's a pain to use. This motivates the more human-friendly Doc language. Whereas ASM programs are sequences of instructions, Doc programs are compositions of expressions. These expressions are summed up by the following grammar:

DocExpr = nil
        | DocExpr + DocExpr
        | str
        | br(str?)
        | nest(int, DocExpr)
        | group(DocExpr)

For example:

'test' + br() + 'ing' + br(' ') + 'this'

is a Doc expression, as is:

group(nest(2, 'test' + br() + 'ing' + br(' ') + 'this'))

What do these represent?

A Python str literal represents itself.
br() is a possible line break.
nest(indent, doc) creates a "nested" subexpression that's visually offset by indent spaces.
group(doc) delimits a subexpression in which all br()s are either treated as line breaks or not.
+ combines Doc expressions.
nil acts as an "empty" expression.

So, for instance:

'test' + br() + 'ing' + br(' ') + 'this

represents the string:

testing this

The second, more complex expression:

group(nest(2, 'test' + br() + 'ing' + br(' ') + 'this'))

may represent either:

testing this

or:

__test
__ing
__this

depending on the value of the target maximum line width "architectural parameter" provided to the compiler. So br expressions might either be treated as line breaks or regular text, in which case their text value is used (or '' if no text argument was provided).

We'll represent Doc expressions using strs and Python classes. In particular:

from __future__ import annotations
from dataclasses import dataclass

@dataclass
class Nil:
    pass

@dataclass
class Br:
    text: str = ""

@dataclass
class Nest:
    indent: int
    doc: DocExpr

@dataclass
class Group:
    doc: DocExpr

DocExpr = Nil | Concat | str | Br | Nest | Group

What about DocExpr + DocExpr? We'll represent those using an additional Concat class:

@dataclass
class Concat:
    car: DocExpr
    cdr: DocExpr

We want to support using + to combine expressions, so we need to implement __add__ and __radd__ on each of the variant classes. Adding two Doc expressions using + just constructs a Concat of the two. It's easy enough to do this manually, e.g.:

@dataclass
class Nil:
    def __add__(self: DocExpr, other: DocExpr) -> DocExpr:
        return Concat(self, other)

    def __radd__(self: DocExpr, other: DocExpr) -> DocExpr:
        return Concat(other, self)

But we can save ourselves some typing by defining a decorator to do it for us:

def with_add(cls):
    """Add suitable __add__ and __radd__ methods to cls so that instances of it
    can be concatenated using "+".
    """

    def add(self: DocExpr, other: DocExpr) -> DocExpr:
        return Concat(self, other)

    def radd(self: DocExpr, other: DocExpr) -> DocExpr:
        return Concat(other, self)

    setattr(cls, "__add__", add)
    setattr(cls, "__radd__", radd)

    return cls

The variant classes now look like:

@with_add
@dataclass
class Nil:
    pass

@with_add
@dataclass
class Concat:
    car: DocExpr
    cdr: DocExpr

@with_add
@dataclass
class Br:
    text: str = ""

@with_add
@dataclass
class Nest:
    indent: int
    doc: DocExpr

@with_add
@dataclass
class Group:
    doc: DocExpr

Our task now is to write a compiler that translates expressions in the Doc language into the equivalent ASM instructions, given some target maximum line width:

def compile(expr: DocExpr, max_len: int) -> list[AsmInst]:
    """Compile a Doc expression to a sequence of ASM instructions."""
    pass

However, it turns out to be simpler to first "lower" Doc expressions into expressions in an Intermediate Representation (IR) language, and then compile the IR expressions into ASM. Introduces this additional "pass" makes each step clearer.

An Intermediate Representation

So our schematic describing the pretty-printing process was a tad oversimplified. Here's the full picture:

IR expressions resemble Doc expressions in many ways:

IrExpr = str
       | br(str?)
       | nest(int, list[IrExpr])
       | group(list[IrExpr])

The key difference is that we no longer have + and nil expressions: these are converted to lists of IR expressions in the lowering process. Actually, that's all the lowering pass does:

def lower(expr: DocExpr) -> list[IrExpr]:
    pass

We first need to define IrExprs.
This ought to look familiar:

@dataclass
class BR:
    text: str

@dataclass
class NEST:
    indent: int
    insts: list[IrExpr]

@dataclass
class GROUP:
    insts: list[IrExpr]

IrExpr = str | BR | NEST | GROUP

All lower does is replace Nil() instances with an empty list ([]), and Concat(car, cdr) instances by appending the results of lowering the car and cdr expressions. The same treatment is applied to the subexpressions in Nest and Group. This is nothing more than a recursive "flattening" operation.

def lower(expr: DocExpr) -> list[IrExpr]:
    """Lower a Doc expression to an equivalent sequence of IR expressions."""
    match expr:
        case Nil():
            return []
        case Concat(car, cdr):
            return lower(car) + lower(cdr)
        case text if isinstance(text, str):
            return [text]
        case Br(text):
            return [BR(text)]
        case Nest(indent, expr):
            return [NEST(indent, lower(expr))]
        case Group(expr):
            return [GROUP(lower(expr))]
        case _:
            raise ValueError("expected a doc")

Testing lower with one of our example Doc expressions from above:

doc = Group(Nest(2, "test" + Br() + "ing" + Br(" ") + "this"))
print(lower(doc))

# [GROUP(insts=[NEST(indent=2, insts=['test', BR(text=''), 'ing', BR(text=' '), 'this'])])]

which is exactly what we expect.

The Compiler (Finally)

Now to the final step: compile. This function transforms IR expressions into ASM instructions, taking into account the target maximum line width:

def compile(exprs: list[IrExpr], max_len: int) -> list[AsmInst]:
    """Compile a sequence of IR expressions into a list of ASM instructions."""
    pass

Here's the rough idea of the algorithm:

The compiler maintains some "state" information:
- The current (horizontal) line position.
- The current indentation amount.
- Whether or not brs should be treated as line breaks or rendered "flat".
We iterate over the expressions, emitting some ASM instructions and updating the line position appropriately.

def compile(exprs: list[IrExpr], max_len: int) -> list[AsmInst]:
    """Compile a sequence of IR expressions into a list of ASM instructions."""
    pos = 0
    asm = []

    def process(expr, indent=0, flat=True):
        nonlocal pos, asm
        match expr:
            # Append ASM instructions for expr to asm, and update pos.
            # ...

    for expr in exprs:
        process(expr)

    return asm

process is where the magic happens:

def process(expr, indent=0, flat=True):
    nonlocal pos, asm
    match expr:
        case text if isinstance(text, str):
            asm.append(text)
            pos += len(text)
        case BR(text):
            if flat:
                asm.append(text)
                pos += len(text)
            else:
                asm.append(indent)
                pos = indent
        case NEST(nest_indent, nest_exprs):
            for nest_expr in nest_exprs:
                process(nest_expr, indent=indent + nest_indent, flat=flat)
        case GROUP(group_exprs):
            flat = fits_flat(group_exprs, max_len - pos)
            for group_expr in group_exprs:
                process(group_expr, indent=indent, flat=flat)

In short:

For text expressions, we emit a TEXT instruction and advance the position (pos) by the length of the text.
br expressions are handled depending on the value of flat:
- If flat is True, treat them as text.
- Otherwise, emit an INDENT instruction with the current indentation level, and reset the position to this value.
For nest expressions, we process all of the subexpressions, but with the current indentation level increased by the nest expression's indentation value.
Finally, for group expressions we first check if the entire group can be rendered flat without exceeding the remaining space. This determines the value of flat for all of the grouped subexpressions, which in turn decides whether brs are rendered as line breaks (or as text).

How does fits_flat work? It simply walks through the instructions in the group, treating brs as text, and stopping when either:

We've run out of space (width < 0), in which case the grouped subexpressions can't be rendered flat.
We've processed all subexpressions, in which case the group can be rendered flat.

def fits_flat(exprs: list[IrExpr], width: int) -> bool:
    """Can the list of IR expressions can be laid out flat without exceeding
    the provided width?"""
    if width < 0:
        return False
    elif not exprs:
        return True

    first, *rest = exprs
    match first:
        case text if isinstance(text, str):
            return fits_flat(rest, width - len(text))
        case BR(text):
            return fits_flat(rest, width - len(text))
        case NEST(_, nest_exprs):
            return fits_flat(nest_exprs + rest, width)
        case GROUP(group_exprs):
            return fits_flat(group_exprs + rest, width)

Putting it all Together

We can finally click the pieces together:

def layout(doc: DocExpr, max_len: int) -> str:
    """Transform a Doc expression into a string it represents, trying not to
    exceed a line width of max_len.
    """
    ir = lower(doc)
    asm = compile(ir, max_len)
    return interpret(asm)

The only remaining pieces of the pretty-printer interface are the document expression constructors:

nil = Nil()
br = Br
nest = Nest
group = Group

Let's try the example from the introduction:

doc = group(
    '['
    + nest(
        4,
        br()
        + "'onions'"
        + ','
        + br(' ')
        + group(
            '['
            + nest(4, br() + "'carrots'" + ',' + br(' ') + "'celery'")
            + br()
            + ']'
        )
        + ','
        + br(' ')
        + "'turnips'"
    )
    + br()
    + ']'
)

print(layout(doc, 60))
# ['onions', ['carrots', 'celery'], 'turnips']

print(layout(doc, 30))
# [
#     'onions',
#     ['carrots', 'celery'],
#     'turnips'
# ]

print(layout(doc, 20))
# [
#     'onions',
#     [
#         'carrots',
#         'celery'
#     ],
#     'turnips'
# ]

See the full source here.

How to "Program" in Doc

🚧 Under Construction 🚧

Common patterns.
How br, nest, and group interact.

Bells and Whistles

🚧 Under Construction 🚧

Adding a fold parameter group to force folding.

Sum Types in Python

William Lewis — Fri, 18 Oct 2024 18:13:13 +0000

Python is a lovely language. However, when working in Python I frequently find myself missing built-in support for sum types. Languages like Haskell and Rust make this kind of thing so easy:

data Op = Add | Sub | Mul
  deriving (Show)

data Expr
  = Lit Integer
  | BinOp Op Expr Expr
  deriving (Show)

val :: Expr -> Integer
val (Lit val) = val
val (BinOp op lhs rhs) =
  let x = val lhs
      y = val rhs
   in apply op x y

apply :: Op -> Integer -> Integer -> Integer
apply Add x y = x + y
apply Sub x y = x - y
apply Mul x y = x * y

val (BinOp Add (BinOp Mul (Lit 2) (Lit 3)) (Lit 4))
-- => 10

While Python doesn't support this kind of construction out-of-the-box, we'll see that types like Expr are nonetheless possible (and easy) to express. Furthermore, we can create a decorator that handles all of the nasty boilerplate for us. The result isn't too different from the Haskell example above:

# The `enum` decorator adds methods for constructing and matching on the
# different variants:
@enum(add=(), sub=(), mul=())
class Op:
    def apply(self, x, y):
        return self.match(
            add=lambda: x + y,
            sub=lambda: x - y,
            mul=lambda: x * y,
        )


# Recursive sum types are also supported:
@enum(lit=(int,), bin_op=lambda: (Op, Expr, Expr))
class Expr:
    def val(self):
        return self.match(
            lit=lambda value: value,
            bin_op=lambda op, lhs, rhs: op.apply(lhs.val(), rhs.val()),
        )


Expr.bin_op(
    Op.add(),
    Expr.bin_op(Op.mul(), Expr.lit(2), Expr.lit(3)),
    Expr.lit(4)
).val()
# => 10

Representing Sum Types

We'll represent sum types using a "tagged union". This is easy to grok by example:

class Expr:
    def lit(value):
        e = Expr()
        e.tag = "lit"
        e.value = value
        return e

    def bin_op(op, lhs, rhs):
        e = Expr()
        e.tag = "bin_op"
        e.op = op
        e.lhs = lhs
        e.rhs = rhs
        return e

Each variant is an instance of the same class (in this case Expr). Each one contains a "tag" indicating which variant it is, along with the data specific to it.

The most basic way to use an Expr is with an if-else chain:

class Expr:
    # ...
    def val(self):
        if self.tag == "lit":
            return self.value
        elif self.tag == "bin_op":
            x = self.lhs.val()
            y = self.rhs.val()
            return self.op.apply(x, y)

However, this has a few downsides:

The same if-else chain is repeated everywhere an Expr is used.
Changing the tag's value—say from "lit" to "literal"—breaks existing code.
Consuming sum types requires knowing implementation details (i.e. the tag and the names of the fields used by each variant).

Implementing `match`

We can avoid all of these issues by exposing a single, public match method used to consume sum types:

class Expr:
    # ...
    def match(self, handlers):
        # ...

But first we need to make the different variants a little more uniform. Instead of storing its data in various fields, each variant will now store it in a tuple named data:

class Expr:
    def lit(value):
        e = Expr()
        e.tag = "lit"
        e.data = (value,)
        return e

    def bin_op(op, lhs, rhs):
        e = Expr()
        e.tag = "bin_op"
        e.data = (op, lhs, rhs)
        return e

This allows us to implement match:

class Expr:
    # ...
    def match(self, **handlers):
        if self.tag in handlers:
            return handlers[self.tag](*self.data)
        else:
            raise RuntimeError(f"missing handler for {self.tag}")

In one fell swoop we've solved all of the problems noted above! As another example, and for a change of scenery, here's Rust's Option type transcribed in this fashion:

class Option:
    def some(x):
        o = Option()
        o.tag = "some"
        o.data = (x,)
        return o

    def none():
        o = Option()
        o.tag = "none"
        o.data = ()
        return o

    def match(self, **handlers):
        if self.tag in handlers:
            return handlers[self.tag](*self.data)
        else:
            raise RuntimeError(f"missing handler for {self.tag}")

    def __repr__(self):
        return self.match(
            some=lambda x: f"Option.some({repr(x)})",
            none=lambda: "Option.none()",
        )

    def __eq__(self, other):
        if not isinstance(other, Option):
            return NotImplemented
        return self.tag == other.tag and self.data == other.data

    def map(self, fn):
        return self.match(
            some=lambda x: Option.some(fn(x)),
            none=lambda: Option.none()
        )

Option.some(2).map(lambda x: x**2)
# => Option.some(4)

As a small quality of life benefit, we can support a special wildcard or "catchall" handler in match, indicated by an underscore (_):

def match(self, **handlers):
    if self.tag in handlers:
        return handlers[self.tag](*self.data)
    elif "_" in handlers:
        return handlers["_"]()
    else:
        raise RuntimeError(f"missing handler for {self.tag}")

This allows us to use match like:

def map(self, fn):
    return self.match(
        some=lambda x: Option.some(fn(x)),
        _=lambda: Option.none(),
    )

Implementing `enum`

As the Option class illustrates, a lot of the code needed to create sum types follows the same pattern:

class Foo:
    # For each variant:
    def my_variant(bar, quux):
        # Construct an instance of the class:
        f = Foo()
        # Give the instance a distinct tag:
        f.tag = "my_variant"
        # Save the values we received:
        f.data = (bar, quux)
        return f

    # This is always the same:
    def match(self, **handlers):
        if self.tag in handlers:
            return handlers[self.tag](*self.data)
        elif "_" in handlers:
            return handlers["_"]()
        else:
            raise RuntimeError(f"missing handler for {self.tag}")

Instead of writing this ourselves, let's write a decorator to generate these methods based on some description of the variants.

def enum(**variants):
    pass

What kind of a description? The simplest thing would be to supply a list of variant names, but we can do a little better by also providing the types of arguments that we expect. We'd use enum to automagically enhance our Option class like this:

# Add two variants:
# - One named `some` that expects a single argument of any type.
# - One named `none` that expects no arguments.
@enum(some=(object,), none=())
class Option:
    pass

The basic structure of enum looks like this:

def enum(**variants):
    def enhance(cls):
        # Add methods to the class cls.
        return cls

    return enhance

It's a function that returns another function, which will be called with the class we're enhancing as its only argument. Within enhance we'll attach methods for constructing each variant, along with match.

First, match, because it's just copy pasta:

def enhance(cls):
    def match(self, **handlers):
        if self.tag in handlers:
            return handlers[self.tag](*self.data)
        elif "_" in handlers:
            return handlers["_"]()
        else:
            raise ValueError(f"missing handler for {self.tag}")

    # Add a method named "match" to the class cls, whose value is the
    # `match` function defined above:
    setattr(cls, "match", match)

    return cls

Adding methods to construct each variant is only slightly more involved. We iterate over the variants dictionary, defining a method for each entry:

def enhance(cls):
    # ...
    for tag, sig in variants.items():
        setattr(cls, tag, make_constructor(tag, sig))

    return cls

where make_constructor creates a constructor function for a variant with tag (and name) tag, and "type signature" sig:

def enhance(cls):
    # ...
    def make_constructor(tag, sig):
        def constructor(*data):
            # Validate the data passed to the constructor:
            if len(sig) != len(data):
                raise ValueError(f"expected {len(sig)} items, not {len(data)}")
            for x, ty in zip(data, sig):
                if not isinstance(x, ty):
                    raise TypeError(f"expected {ty} but got {repr(x)}")

            # Just a generalization of what we've seen above:
            inst = cls()
            inst.tag = tag
            inst.data = data
            return inst

        return constructor

    for tag, sig in variants.items():
        setattr(cls, tag, make_constructor(tag, sig))

    return cls

Here's the full definition of enum for reference.

Bonus Features

More Dunder Methods

We can easily enhance our sum classes with __repr__ and __eq__ methods:

def enhance(cls):
    # ...
    def _repr(self):
        return f"{cls.__name__}.{self.tag}({', '.join(map(repr, self.data))})"

    setattr(cls, "__repr__", _repr)

    def _eq(self, other):
        if not isinstance(other, cls):
            return NotImplemented
        return self.tag == other.tag and self.data == other.data

    setattr(cls, "__eq__", _eq)

    return cls

With enhance improved in this fashion, we can define Option with minimal cruft:

@enum(some=(object,), none=())
class Option:
    def map(self, fn):
        return self.match(
            some=lambda x: Option.some(fn(x)),
            _=lambda: Option.none(),
        )

Recursive Definitions

Unfortunately, enum isn't (yet) up to the task of defining Expr:

@enum(add=(), sub=(), mul=())
class Op:
    pass

@enum(lit=(int,), bin_op=(Op, Expr, Expr))
class Expr:
    pass

# NameError: name 'Expr' is not defined

We're using the class Expr before it's been defined. An easy fix here is to simply call the decorator after defining the class:

class Expr:
    pass

enum(lit=(int,), bin_op=(Op, Expr, Expr))(Expr)

But there's a simple change we can make to support this: allow a "signature" to be a function that returns a tuple:

@enum(lit=(int,), bin_op=lambda: (Op, Expr, Expr))
class Expr:
    pass

All this requires is a small change in make_constructor:

def make_constructor(tag, sig):
    def constructor(*data):
        nonlocal sig
        # If sig is a "thunk", thaw it out:
        if callable(sig):
            sig = sig()

        # ...

Conclusion

Useful as it may be, our fancy new enum decorator isn't without its shortcomings. The most apparent is the inability to perform any kind of "nested" pattern matching. In Rust, we can do things like this:

fn foo<T: Debug>(x: Option<Option<T>>) {
    match x {
        Some(Some(value)) => println!("{:?}", value),
        _ => {}
    }
}

But we're forced to perform a double match to achieve the same result:

def foo(x):
    return x.match(
        some=lambda x1: x1.match(
            some=lambda value: print(value),
            _=lambda: None
        ),
        _=lambda: None
    )

That said, these kinds of cases seem relatively rare.

Another downside is that match requires constructing and calling lots of functions. This means it's likely much slower than the equivalent if-else chain. However, the usual rule of thumb applies here: use enum if you like its ergonomic benefits, and replace it with its "generated" code if it's too slow.

Arithmetic with Uncertainty

William Lewis — Sun, 15 Sep 2024 01:13:38 +0000

If you know the temperature in Fahrenheit, then it's easy enough to convert it to Celsius:

def f_to_c(f):
    """Convert Fahrenheit to Celsius."""
    return (f - 32) * 5 / 9

So if it's 68 degrees Fahrenheit, that's the same as f_to_c(68) = 20 degrees Celsius.

But what if we don't know the exact temperature? Maybe we have two thermometers and they disagree by a few degrees: one is showing 66 and the other 71. So we have a rough idea of what the temperature is like in Fahrenheit (somewhere between 66 and 71 degrees), and we'd like to convert this to an equivalently rough idea of what the temperature is like in Celsius.

In a sense, we'd like to simultaneously consider every possible value in the range [66, 71], calculate the equivalent Celsius temperature, and form a range from the resulting values. But because f_to_c is monotonic, we can simply compute the values at the endpoints and use those:

So knowing that the temperature is somewhere between 66 and 71 degrees Fahrenheit is the same as knowing that it's between f_to_c(66) ≈ 19 and f_to_c(71) ≈ 22 degrees Celsius.

One way to think about this computation is as a propagation of our uncertainty. Instead of calculating with numbers, like 68, we're operating on ranges of values, like [66, 71]. This is a crude representation of uncertainty to be sure, but — as we'll see — it's enough to begin to illustrate some neat ideas.

Arithmetic with Uncertainty

Our plan is to write an Ind class that represents uncertain or indeterminate values as ranges of numbers:

class Ind:
    """A representation of an uncertain or indeterminate value.

    Ind(a, b) represents our _knowledge_ that some value lies between a and b."""

    def __init__(self, lo, hi):
        self.lo = lo
        self.hi = hi

    def __eq__(self, other):
        a, b = self.lo, self.hi
        c, d = other.lo, other.hi
        return a == c and b == d

    def __str__(self):
        return f"[{self.lo}, {self.hi}]"

    def __repr__(self):
        return f"Ind({self.lo}, {self.hi})"

so that functions like f_to_c "just work" when applied to Ind objects:

f_temp = Ind(66, 71)
print(f_to_c(f_temp))
# => [18.88888888888889, 21.666666666666668]

In order to make this happen, operators like + and * need to "propagate uncertainty" like we've illustrated above. Now an object like Ind(a, b) represents an uncertain value that's somewhere between a and b: it might be as low as a or as high as b, and that's all we know. So given two Inds — [a, b] and [c, d] — their sum might be as small as a + c or as high as b + d:

class Ind:
    # ...

    def __add__(self, other):
        if isinstance(other, Ind):
            a, b = self.lo, self.hi
            c, d = other.lo, other.hi
            return Ind(a + c, b + d)
        else:
            # ...

What about the else case, where we're adding a number to an Ind? As an example, if you're heading to a class that you know will take exactly 50 minutes, and then walking with a friend for somewhere between 30 and 45 minutes, then between class and walking, you'll spend [50 + 30, 50 + 45] = [80, 95]minutes. So adding a number to anInd just "shifts" it by the number's value. One way to implement this is:

def __add__(self, other):
    if isinstance(other, Ind):
        # ...
    else:
        return Ind(self.lo + other, self.hi + other)

But we'll take a slightly different approach here that nonetheless produces the same result: we'll think of numbers — like the 50 minutes in the example above — as certain knowledge, and represent them as Inds for which lo == hi.

class Ind:
    # ...

    def certain(x):
        """Construct a representation of certainty."""
        return Ind(x, x)

Adding an Ind to a number is then a simple matter of promoting the number to a certain Ind and then adding them together:

def __add__(self, other):
    if isinstance(other, Ind):
        # ...
    else:
        return self + Ind.certain(other)

While we're at it, let's implement __radd__ so that we can add numbers to Inds as well:

def __radd__(self, other):
    return Ind.certain(other) + self

At this point, Ind is functional enough to calculate the "class, then walking" example:

50 + Ind(30, 45)
# => [80, 95]

Let's move on to multiplication. Multiplying two intervals is slightly more involved than addition, because the minimum and maximum values of the product of two intervals isn't always the product of the minimum and maximum values. Here are some examples showing several of the many different possible cases:

# [a, b] * [ c,  d] == [ e,  f]
  [1, 2] * [ 3,  5] == [ 3, 10]  # e = a*b  f = b*d
  [2, 4] * [-2, -1] == [-8, -2]  # e = b*c  f = a*d
  [1, 3] * [-1,  1] == [-3,  3]  # e = b*c  f = b*d
# Many more...

So which components form the min and max depends on the signs of the values and their positions relative to 0. The good news is that we don't actually need to decode the pattern here: instead we can just calculate the four possible products and use the smallest for the min and the largest for the max:

class Ind:
    # ...

    def __mul__(self, other):
        if isinstance(other, Ind):
            a, b = self.lo, self.hi
            c, d = other.lo, other.hi
            # Just consider all possible products.
            ac, ad, bc, bd = a * c, a * d, b * c, b * d
            return Ind(min(ac, ad, bc, bd), max(ac, ad, bc, bd))
        else:
            return self * Ind.certain(other)

    def __rmul__(self, other):
        return Ind.certain(other) * self

Let's quickly dispatch some more operations:

class Ind:
    # ...

    def __sub__(self, other):
        return self + -other

    def __neg__(self):
        return Ind(-self.hi, -self.lo)

    def __rsub__(self, other):
        return Ind.certain(other) - self

    def __truediv__(self, other):
        if isinstance(other, Ind):
            return self * other.reciprocal()
        else:
            return self / Ind.certain(other)

    def reciprocal(self):
        a, b = self.lo, self.hi
        a_inv, b_inv = 1 / a, 1 / b
        return Ind(min(a_inv, b_inv), max(a_inv, b_inv))

    def __rtruediv__(self, other):
        return Ind.certain(other) / self

These are fairly straightforward: we "rewrite" subtraction using addition and negation, and do the same with division in terms of multiplication and reciprocation.

The final operation we'll support is raising to an integer power. This one is slightly tricky: if the power is odd, then this is a monotonic operation, but if it's even, we need to be careful about intervals that straddle 0. As an example, consider the expression [-1, 1] ** 2, which we'll think of as simultaneously squaring every value between -1 and 1. The smallest resulting value is 0, not -1 ** 2:

class Ind:
    def __pow__(self, n):
        a, b = self.lo, self.hi
        an, bn = a**n, b**n

        if n % 2 == 0:
            if a < 0 and b > 0:
                return Ind(0, max(an, bn))
            return Ind(min(an, bn), max(an, bn))
        else:
            return Ind(an, bn)

Here's the complete implementation.

Let's try it out:

f_to_c(Ind(66, 71))
# => [18.88888888888889, 21.666666666666668]

Here are a few more examples: suppose we know that a cylinder's radius is between 10 and 10.5 cm, and that its height is between 12.5 and 13.5 cm. What do we know about its volume?

def cylinder_vol(r, h):
    """Compute the volume of a cylinder with radius r and height h."""
    return 3.14 * r**2 * h


r = Ind(10, 10.5)
h = Ind(12, 13.5)
print(cylinder_vol(r, h))
# => [3768.0, 4673.4975]

Or another: two objects in orbit are between 100 and 102 meters apart, but are drifting towards each other at a rate between 1 and 1.2 meters per second. How long before they collide?

def collision_time(dist, speed):
    """Calculate the time before two objects collide, assuming they're dist m
    apart, and approaching each other at speed m/s."""
    return dist / speed


dist = Ind(100, 102)
speed = Ind(1, 1.2)
print(collision_time(dist, speed))
# => [83.33333333333334, 102.0]

Now each of these problems would have been easy enough to solve manually, i.e. without using our Ind class. In fact, it's clear that all Ind is doing is mildly clever accounting. But the point is that Ind allows us to think at a higher, more abstract level. This is similar to how operations on, say, 3D vectors are "just" operations on their components, but the calculation with vectors is much simpler.

Dependence

Unfortunately there's a subtle problem with our Ind class, related to an issue not present in any of our familiar number systems:

x = Ind(-1, 1)

print(x**2)
# => [0, 1]

print(x * x)
# => [-1, 1]

Squaring a number isn't the same as multiplying it by itself!

Our Ind class isn't smart enough to know that both terms in the expression x * x are the same thing. There's a dependence here that we're not taking into account: the way we compute products assumes that both factors can vary independently of one another. In this case that amounts to assuming that the lefthand factor (x) can be -1 while — at the same time — the righthand factor (also x) can be 1. This isn't possible! But Ind isn't clever enough to detect this.

This notion of independence (and dependence) is a big theme in probability. When calculating with numbers, we don't need to concern ourselves with questions of "identity". But that changes when we consider ranges of values, and will continue to be the case as we consider more exotic, richer models of uncertainty.

Notice how x**2 is a "tighter" interval than x * x. Tighter intervals represent less uncertainty. This makes sense given that __pow__ has more information available to it than __mul__ (namely, that the thing being multiplied by itself n times is the same thing).

Unfortunately, there's no simple fix. One thing we might try is giving each Ind a unique ID, and then check these IDs when operating on them: if the IDs match, we treat them as the same, otherwise we assume that they're independent. This works for very simple calculations like x * x, but it doesn't scale to larger expressions, such as x * y * x + 3 * x. One problem is that compound expressions also have identities (e.g. in x * y + x * y, the two terms x * y are the same); another is that expressions might have "partial dependencies" on each other, like x * y and x.

Losing Information

While we're at it, here's another shortcoming: suppose you're waiting in line at the DMV. There are between 16 and 18 people in front of you (you're not sure if a few people are just there for moral support), and it appears to be taking between 2 and 15 minutes for each person to be served. How long are you going to be waiting?

def wait_time(line_len, wait_per_person):
    """Calculate how long you'll be waiting in line."""
    return line_len * wait_per_person


line_len = Ind(16, 18)
wait = Ind(2, 15)
print(wait_time(line_len, wait))
# => [32, 270]

270 minutes! You might be here a while...

But you probably won't be. The problem is that we're only going to be waiting 270 minutes if our most pessimistic estimations are correct: the line is as long as possible, and everyone takes 15 minutes. We probably don't think everyone will take 15 minutes, but rather that most people will take around 4-5 minutes, with a few people being served extra quickly, and a few very slowly. So our beliefs often have more of a structure to them, a kind of "shape" than we're unable to represent with Ind.

Ind is just too crude for all but the simplest problems. Nonetheless it illustrates several important ideas in probability:

The value of defining operations on compound or complex objects, and how these can be used to "propagate uncertainty" through transformations.
The problems posed by dependencies between the quantities we're operating on: we need to consider how the quantities vary with respect to one another.
The need for a richer representation of uncertainty, which will turn out to involve distributions.

Addendum

Our Ind class implements interval arithmetic, a well-known technique in numerical analysis. The dependency problem described above really is a tough nut to crack.

Introduction

William Lewis — Fri, 13 Sep 2024 17:56:28 +0000

We tend to think of random phenomena as the purview of probability — situations in which an element of chance is involved, such as flipping coins, rolling dice, or dealing cards. This has the unfortunate effect of obscuring a much broader view of the subject, as the study of uncertainty.

This view encompasses the usual one: when we flip a coin or deal a poker hand, we are uncertain about the outcome. But it's also much richer. For instance, we might not know some quantity precisely, such as the temperature outside or the mass of a planet, but that shouldn't stop us from performing calculations with it. Probability provides a frame of mind and tools for computing in the face of uncertainty.

We tend to think of randomness as an inherent quality in certain objects: dice and coins are random, billiard balls are not. A philosopher would call it "ontological". This leads to a lot of confusion! I remember scratching my head as an undergraduate, wondering "where" the randomness was. Uncertainty, on the other hand, is in our minds; it is "epistemological". So uncertainty isn't simply a more general topic, it has quite a different, and richer, flavor.

In this sequence of posts we approach various topics in probability and statistics from this point of view.

Disjoint Unions in C

William Lewis — Tue, 10 Sep 2024 00:59:09 +0000

It's not immediately clear how to express this Haskell type in C:

data Tree = Leaf Int | Inner Tree Tree

Unlike languages like Haskell and Rust, C lacks built-in support for
disjoint unions. However, it does provide all the ingredients we need to represent them, if we're willing to do a little extra typing.

The first thing to realize is that a disjoint union consists of:

A number of different variants
Each of which has some data associated with it.

In our binary tree example, we have two variants: "leaf" and "inner". The leaf variant stores a single integer (its data), and the inner variant stores two Trees (representing its left and right children).

We can represent such an animal in C using a struct with two fields:

A "type tag", typically an integer, indicating which variant is being represented.
A data field which stores the data associated with the variant.

It's convenient to define the different variant type tags using an enum:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

What about storing the data? This is the type of problem that unions exist to solve.

Unions

A union is just a chunk of memory capable of storing a number of different types of data. For instance, here's a union that can store either a 32-bit int or an array of 5 chars.

union int_or_chars {
        int num;
        char letters[5];
};

A variable whose type is union int_or_chars can hold either an int or an array of 5 chars at any particular time (just not both at the same time):

union int_or_chars quux;

// We can store an int:
quux.num = 42;
printf("quux.num = %d\n", quux.num);
// => quux.num = 42

// Or 5 chars:
quux.letters[0] = 'a';
quux.letters[1] = 'b';
quux.letters[2] = 'c';
quux.letters[3] = 'd';
quux.letters[4] = 0;
printf("quux.letters = %s\n", quux.letters);
// => quux.letters = abcd

// But not both. The memory is "shared", so the chars saved above are
// now being interpreted as an int:
printf("quux.num = %x\n", quux.num);
// quux.num = 64636261

return 0;

A union like union int_or_chars has at its disposal a chunk of memory big enough to hold the largest of its members. Here's a schematic showing how this works:

+ ---- + ---- + ---- + ---- + ---- +
| byte |      |      |      |      |
+ ---- + ---- + ---- + ---- + ---- +
|<--   int uses these 4  -->|
|<--  array of chars uses all 5 -->|

Which helps explain why printing quux.num resulted in "garbage" after we stored an array of chars in quux: it wasn't garbage, it was the string "abcd" being interpreted as an integer. (On my machine, quux.num is printed in hex as 64636261. The character 'a' has an ASCII value of 0x61, 'b' has a value of 0x62, 'c' is 0x63, and 'd' is 0x64. The order is reversed since my processor is little-endian.)

As a final note on unions, you might be surprised by the size reported by sizeof:

printf("%ld\n", sizeof(union int_or_chars));
// => 8

On my machine, the type union int_or_chars has a size of 8 bytes, not 5 like we might have expected. Some padding has been added because of alignment requirements stipulated by my processor's architecture.

Back to Binary Trees

We're now ready to continue translating the binary tree type from Haskell to C. We've already defined an enum to represent the variant's type. Now we need a union to store its data:

union tree_data {
        int leaf;
        struct inner_data inner;
};

where struct inner_data is a struct containing the left and right children of an "inner" variant:

struct inner_data {
        struct tree *left;
        struct tree *right;
};

Notice that the "inner" variant maintains pointers to its left and right children. The indirection is necessary because otherwise struct tree wouldn't have a fixed size.

With these pieces in place, we're ready to define our tree type:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

struct tree;
struct inner_data {
        struct tree *left;
        struct tree *right;
};

union tree_data {
        int leaf;
        struct inner_data inner;
};

// A representation of a binary tree.
struct tree {
        enum tree_type type;
        union tree_data data;
};

Playing with Trees

Let's write some functions to construct trees:

// Construct a leaf node.
struct tree *leaf(int value) {
        struct tree *t = malloc(sizeof(*t));
        t->type = TREE_LEAF;
        t->data.leaf = value;
        return t;
}

// Construct an inner node.
struct tree *inner(struct tree *left, struct tree *right) {
        struct tree *t = malloc(sizeof(*t));
        t->type = TREE_INNER;
        t->data.inner.left = left;
        t->data.inner.right = right;
        return t;
}

and print them:

void print_tree(struct tree *t) {
        switch (t->type) {
        case TREE_LEAF:
                printf("%d", t->data.leaf);
                return;
        case TREE_INNER:
                printf("(");
                print_tree(t->data.inner.left);
                printf(" ");
                print_tree(t->data.inner.right);
                printf(")");
                return;
        }
}

This allows us to translate the Haskell expression:

Inner (Inner (Leaf 1) (Leaf 2)) (Leaf 3)

into C as:

inner(inner(leaf(1), leaf(2)), leaf(3));

For example:

struct tree *t = inner(inner(leaf(1), leaf(2)), leaf(3));
print_tree(t);
// => ((1 2) 3)

As a slightly more interesting example, let's translate this depth-first search function:

-- Check if a value is in a tree.
search :: Int -> Tree -> Bool
search v (Leaf w) = v == w
search v (Inner l r) = search v l || search v r

Using our tree type:

// Check if a value is in a tree.
int search(int value, struct tree *t) {
        switch (t->type) {
        case TREE_LEAF:
                return t->data.leaf == value;
        case TREE_INNER:
                return (
                        search(value, t->data.inner.left) ||
                        search(value, t->data.inner.right)
                );
        }
}

It's certainly more verbose, but the translation process is straightforward (to the extent that a compiler could presumably do this sort of thing for us...).

Tradeoffs

We end with a little digression about the tradeoffs involved in an alternative representation. Specifically, suppose instead of:

union tree_data {
        int leaf;
        struct inner_data inner;
};

we used:

union tree_data {
        int leaf;
        struct inner_data *inner;
        //                ^ The difference.
};

In the first case, the union contains a struct inner_data, whereas in the second it stores a pointer to this struct. As a result, the first union is a bit larger at 16 bytes, vs 8 for the pointer version on my machine. Unfortunately it's not just inner nodes that are affected: leaf nodes use this same 16-byte union but only store a single (4-byte) int. This feels a bit wasteful.

However, that's not the whole story. We're going to pay for the extra indirection every time we access the left and right children of an inner node: reads aren't necessarily cheap, particularly if the memory pointed to isn't cached.

I suspect the main approach presented here is a better starting point in most cases, and that trying to shave a few bytes (white incurring additional reads) just ain't worth it until it is.

Levenshtein Distance

William Lewis — Fri, 30 Aug 2024 01:34:59 +0000

How many moves does it take to transform the word "alpha" into "aleph", where a move is one of the following actions?

Deleting a letter
Inserting a letter
Replacing one letter with another

For example, starting with "alpha":

Insert e after l, producing "alepha".
Delete the final a, giving "aleph".

This isn't the only possible sequence of moves, though. Here's another:

Replace p with e, giving "aleha".
Replace h with p, giving "alepa".
Replace a with h, producing "aleph".

For any source and target strings, there may be many ways of transforming one into the other. But there's always a shortest number of moves for doing so. This shortest number of moves is called the Levenshtein distance between the two strings, and that's what we're interested in today. For instance, we can go from "the" to "nap" in just three moves:

Replace t with n, giving "nhe".
Replace h with a, giving "nae".
Replace e with p, giving "nap".

Since there's no way to do it in fewer, the Levenshtein distance between "the" and "nap" is 3.

A Simple Recursive Algorithm

Our goal is to write the body of this function:

def dist(src, tgt):
    """
    Compute the Levenshtein distance between src and tgt.
    """
    pass

We can start be observing some base cases:

If the source string is "" (the empty string), we can't do any better than inserting all of the characters in the target string. Since there are len(tgt) such characters, dist("", tgt) == len(tgt)
Likewise if the target string is "", we can't do any better than deleting the letters from the source string. So dist(src, "") == len(src).

That's enough to get us started:

def dist(src, tgt):
    if not src:
        return len(tgt)
    elif not tgt:
        return len(src)

    # ...

If neither string is empty, then we compare the first characters in each. If they're the same, we don't need to perform any moves on these characters, and the distance between the two strings is simply the distance between the tails of the two:

def dist(src, tgt):
    if not src:
        return len(tgt)
    elif not tgt:
        return len(src)

    a, *src_tail = src
    b, *tgt_tail = tgt

    if a == b:
        return dist(src_tail, tgt_tail)

    # ...

If the first two characters don't match, it's not clear what the right move to perform is without peeking at the rest of the strings. In this case we just try all possible moves, and pick the one that results in the smallest distance:

def dist(src, tgt):
    if not src:
        return len(tgt)
    elif not tgt:
        return len(src)

    a, *src_tail = src
    b, *tgt_tail = tgt

    if a == b:
        return dist(src_tail, tgt_tail)

    return 1 + min(dist(src, tgt_tail), dist(src_tail, tgt), dist(src_tail, tgt_tail))

For example, dist(src, tgt_tail) (the first term in the min(...)
expression), is computing the distance between the source string and the rest (tail) of the target string. This corresponds to inserting the first character in the target string.

The second expression — dist(src_tail, tgt) — corresponds to deleting the first character in the source string; and the final expression — dist(src_tail, tgt_tail) — to replacing the first character in the source string with the first character in the target string. In each of the subexpressions, we're asking, "supposing I performed X move, what's the distance between the resulting strings?" We add 1 to the calculation to account for the single move that we're performing.

I find this slightly tricky to wrap my head around, but it's a little easier to grasp if we visualize the recursive calls that dist makes while computing the distance between two strings. For instance, to calculate dist("the", "tea"):

Link to image

Each box corresponds to a call to dist, and each arrow indicates the move made during the call to dist (the one exception is "skip", which isn't really a move; this occurs when the first two letters match).

Here's a trace of an even simpler calculation: dist("i", "an"), which might be easier to follow:

Link to image

These diagrams make a few things clear:

There are often multiple distinct minimal sequences of moves for transforming one string into another. For instance, to transform "the" into "tea", there are two paths containing the minimal 2 (non-skip) moves:
- Delete h and insert a.
- Replace h with e, and replace e with a.
There's a lot of redundant computation. For example, the subcomputation dist("e", "a") is performed twice while computing dist("the", "tea"). This is even more glaring in larger computations like:

brace yourself

Link to image

One consequence of observation (2) is that our current implementation of dist performs very slowly on anything other than small inputs. For instance, this calculation doesn't complete after even a minute on my machine:

dist("a man, a plan, a canal: panama", "a girl, a pearl, a lexus: canada")

In a minute we'll see a way to speed this up dramatically, but first (this is a lark after all), a quick diversion...

A Levenshtein Machein

It's not too difficult to modify dist to return a minimal sequence of moves for transforming one string into another, rather than the distance between them. We can think of this as a sequence of instructions to be executed by a machine that operates on the input string. For instance, applying the instruction sequence:

SKIP
REPLACE h WITH e
REPLACE e WITH a

to the string "the" produces the string "tea".

We'll need a way to represent the different moves applied to strings, AKA our instructions. For example, here's how we represent the "insert" instruction:

class Insert:
    def __init__(self, elt):
        self.elt = elt

    def __str__(self):
        return f"INSERT {self.elt}"

    def __eq__(self, rhs):
        return self.elt == rhs.elt

The other instructions are similar:

class Delete:
    def __init__(self, elt):
        self.elt = elt

    def __str__(self):
        return f"DELETE {self.elt}"

    def __eq__(self, rhs):
        return self.elt == rhs.elt


class Replace:
    def __init__(self, src, dst):
        self.src = src
        self.dst = dst

    def __str__(self):
        return f"REPLACE {self.src} WITH {self.dst}"

    def __eq__(self, rhs):
        return self.src == rhs.src and self.dst == rhs.dst


class Skip:
    def __str__(self):
        return "SKIP"

    def __eq__(self, rhs):
        return True

Generating instructions for transforming a source string into a target string is just a matter of tweaking the return statements in dist:

def gen_insts(src, tgt):
    """
    Generate a minimal sequence of instructions that transforms src into tgt.
    """
    if not src:
        return list(map(lambda y: Insert(y), tgt))
    elif not tgt:
        return list(map(lambda x: Delete(x), src))

    a, *src_tail = src
    b, *tgt_tail = tgt

    if a == b:
        return [Skip(), *gen_insts(src_tail, tgt_tail)]

    insert_b = gen_insts(src, tgt_tail)
    delete_a = gen_insts(src_tail, tgt)
    replace_ab = gen_insts(src_tail, tgt_tail)

    best = min(insert_b, delete_a, replace_ab, key=inst_count)

    if best is insert_b:
        return [Insert(b), *insert_b]
    elif best is delete_a:
        return [Delete(a), *delete_a]
    else:
        return [Replace(a, b), *replace_ab]

For example, when src is "", instead of returning a distance of len(tgt), we return a list of Insert instructions, one for each letter remaining in tgt. The only wrinkle is at the end. We first generate instruction sequences for the 3 different possible moves: inserting the first letter in the target string, deleting the first letter in the source string, and replacing the first letter in the source with the first letter in the target. We pick whichever involves the fewest (non-Skip) instructions:

def inst_count(insts):
    """
    Counts the number of nontrivial instructions in insts.
    """
    return len(list(filter(lambda i: not isinstance(i, Skip), insts)))

Here are the instructions produced by gen_insts("the", "tea"):

SKIP
DELETE h
SKIP
INSERT a

and by gen_insts("pagoda", "pierogi"):

SKIP
INSERT i
REPLACE a WITH e
REPLACE g WITH r
SKIP
REPLACE d WITH g
REPLACE a WITH i

Here's an example of what the initial internal state of the machine looks like:

+ --- + --- + --- +
|  t  |  h  |  e  |
+ --- + --- + --- +
   ^
   |
   j

output: []

-> SKIP
   DELETE h
   SKIP
   INSERT a

We maintain an index into the source string (j), an output list of characters, and a current instruction. Operating the machine is simply a matter of doing the right thing for each instruction:

If the instruction is INSERT c, append c to the output.
If it's DELETE c, don't add any characters to the output, but advance j.
If it's REPLACE c WITH d, append d to the output, and advance j.
Finally, if it's SKIP c, append c to the output, and advance j.

def run(src, insts):
    """
    Apply insts to src.
    """
    cs = []
    j = 0
    for i in insts:
        if isinstance(i, Insert):
            cs.append(i.elt)
        elif isinstance(i, Delete):
            if src[j] != i.elt:
                raise ValueError(f"Expected {i.elt}")
            j += 1
        elif isinstance(i, Replace):
            if src[j] != i.src:
                raise ValueError(f"Expected {i.src}")
            cs.append(i.dst)
            j += 1
        elif isinstance(i, Skip):
            cs.append(src[j])
            j += 1

    return "".join(cs)

And that's all there is to it. To summarize very concisely, for any src and tgt strings:

run(src, gen_insts(src, tgt)) == tgt

...and now, back to the main event.

Speeding Things Up

Memoize?

We noticed earlier that the same subtrees appear multiple times in any but the smallest traces. Any time the same computation is being performed multiple times, it's worth trying to speed things up with memoization. Memoizing our recursive dist implementation would have the effect of "merging" all of the common subtrees in the trace diagrams. Unfortunately, memoization isn't a panacea (alas, nothing is). Particularly when arguments are compound objects (like strings or lists), we incur the overhead of hashing them into things that can be used as keys in a cache. This overhead isn't too bad in this case, but there's a better approach.

Dynamic Programming

Memoization is really general: it works in cases where a function might conceivably be applied to an infinite variety of inputs. But in this case we know in advance the exact inputs whose results we want to cache in order to avoid redundant recomputations. Our recursive implementation performs these calculations on-demand, but we could
just as easily perform them in advance. The downside is that we might do more work than necessary, but the calculations involved are so simple that this doesn't matter.

Here's the idea: we allocate a two-dimensional array with a row for each suffix of the source string, and a column for each suffix of the target string. A string s has len(s) + 1 suffixes. For example:

"tea"[0:] == "tea"
"tea"[1:] == "ea"
"tea"[2:] == "a"
"tea"[3:] == ""

Here's the first part of our new implementation:

def dist(src, tgt):
    m = len(src)
    n = len(tgt)
    d = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

    # ...

We should visualize this table containing the letters of the source string running down the rows, and the letters of the target across the top. For instance, here's the table for the calculation dist("the", "tea"):

     t     e     a
  + --- + --- + --- + --- +
t |     |     |     |     |
  + --- + --- + --- + --- +
h |     |     |     |     |
  + --- + --- + --- + --- +
e |     |     |     |     |
  + --- + --- + --- + --- +
  |     |     |     |     |
  + --- + --- + --- + --- +

This table will contain the distances between all suffixes of the source and target strings. That is, the entry d[i][j] will contain dist(src[i:], tgt[j:]).

The first order of business is to populate these "empty suffix" cells using some boundary conditions, analogous to the base cases in the recursive implementation. Specifically, we know that

dist(src[i:], "") == len(src[i:])
                  == len(src) - i
                  == m - i

and likewise:

dist("", tgt[j:]) == len(tgt[j:])
                  == len(tgt) - j
                  == n - j

This allows us to fill out the rightmost column and bottom row:

     t     e     a
  + --- + --- + --- + --- +
t |     |     |     |  3  |
  + --- + --- + --- + --- +
h |     |     |     |  2  |
  + --- + --- + --- + --- +
e |     |     |     |  1  |
  + --- + --- + --- + --- +
  |  3  |  2  |  1  |  0  |
  + --- + --- + --- + --- +

As an example, there's a 2 in the rightmost column because:

d[1][3] == dist(src[1:], tgt[3:])
        == dist("he", "")
        == 2

and likewise there's a 3 in the bottom row because:

d[3][0] == dist(src[3:], tgt[0:])
        == dist("", "tea")
        == 3

Here's the code to initialize these cells:

def dist(src, tgt):
    # ...

    for i in range(m + 1):
        d[i][n] = m - i

    for j in range(n + 1):
        d[m][j] = n - j

    # ...

Filling in the remaining entries resembles the recursive cases in our original implementation. We iterate backwards through the rows and columns, starting from the known boundary and moving towards the upper left-hand corner:

def dist(src, tgt):
    # ...

    for i in reversed(range(m)):
        for j in reversed(range(n)):
            # Fill in the remaining cells in d.

    # ...

To compute the value of the cell d[i][j], we first check if the character at index i in the source string is the same as the character at index j in the target string (src[i] == tgt[j]). If so, the distance between src[i:] and tgt[j:] is the same as the distance between src[i + 1:] and tgt[i + 1:] (that is, the distance between the tails). But this is just the value at d[i + 1][j + 1]. So in this case, d[i][j] = d[i + 1][j + 1]:

def dist(src, tgt):
    # ...

    for i in reversed(range(m)):
        for j in reversed(range(n)):
            a = src[i]
            b = tgt[j]
            if a == b:
                d[i][j] = d[i + 1][j + 1]

    # ...

If src[i] != tgt[j], we need to consider the three possible moves we can make, just like in the recursive case. In this case, however, we've already computed the distances involved. The distance between the suffixes that results from inserting tgt[j] is located at d[i][j + 1], the result from deleting src[i] is at d[i + 1][j], and from replacing src[i] with tgt[j] is at d[i + 1][j + 1]. We just need to look them up and select the smallest:

def dist(src, tgt):
    # ...

    for i in reversed(range(m)):
        for j in reversed(range(n)):
            a = src[i]
            b = tgt[j]
            if a == b:
                d[i][j] = d[i + 1][j + 1]
            else:
                d[i][j] = 1 + min(d[i + 1][j], d[i][j + 1], d[i + 1][j + 1])

    # ...

Finally, we return d[0][0], which holds the distance between the suffixes src[0:] and tgt[0:], i.e. the original source and target strings themselves:

def dist(src, tgt):
    m = len(src)
    n = len(tgt)
    d = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

    for i in range(m + 1):
        d[i][n] = m - i

    for j in range(n + 1):
        d[m][j] = n - j

    for i in reversed(range(m)):
        for j in reversed(range(n)):
            a = src[i]
            b = tgt[j]
            if a == b:
                d[i][j] = d[i + 1][j + 1]
            else:
                d[i][j] = 1 + min(d[i + 1][j], d[i][j + 1], d[i + 1][j + 1])

    return d[0][0]

Tables for a number of different cases (including dist("the", "tea") are rendered here. Hovering over any of the cells shows the "move" that led to the cell's calculation (e.g. "Delete h"), a feature stolen from Wikipedia.

Using Less Space

The eagle-eyed will have noticed that, although we allocated a two-dimensional table for our calculations, we only ever referenced the previous row when computing the next. That is, when calculating d[1][2], we only referred to cells d[2][2], d[1][3] and d[2][3], and not, for instance, d[5][7]. We can take advantage of this fact by using two one-dimensional lists for our calculations, performing the computations in a kind of "leap frog" style.

Here's what that looks like:

     t     e     a
  +     +     +     +     +
t
  +     +     +     +     +
h
  + --- + --- + --- + --- +
e |     |     |     |     | <- v1
  + --- + --- + --- + --- +
  |  3  |  2  |  1  |  0  | <- v0
  + --- + --- + --- + --- +

We allocate two arrays, v0 and v1, and initialize v0 using the same boundary condition as before. We then iterate backwards over the suffixes of the target string, filling in the cells in v1 as we go. This requires little more than translating lookups in d to lookups in either v0 or v1:

d[i + 1][j] == v0[i][j]
d[i][j + 1] == v1[i][j + 1]
d[i + 1][j + 1] == v0[i][j + 1]

which allows us to populate the entries in v1:

     t     e     a
  +     +     +     +     +
t
  +     +     +     +     +
h
  + --- + --- + --- + --- +
e |  2  |  1  |  1  |  1  | <- v1
  + --- + --- + --- + --- +
  |  3  |  2  |  1  |  0  | <- v0
  + --- + --- + --- + --- +

We then swap the addresses pointed to by v0 and v1, effectively producing the following situation:

     t     e     a
  +     +     +     +     +
t
  + --- + --- + --- + --- +
h |     |     |     |     | <- v1
  + --- + --- + --- + --- +
e |  2  |  1  |  1  |  1  | <- v0
  + --- + --- + --- + --- +

  +     +     +     +     +

We just rinse and repeat until we've completed the top row, at which point the distance we're interested in is located in v0[0] (not v1[0], since we swap v0 and v1, even after the final iteration). Here's the implementation:

def dist(src, tgt):
    m = len(src)
    n = len(tgt)

    v0 = [n - j for j in range(n + 1)]
    v1 = [0 for _ in range(n + 1)]

    for i in reversed(range(m)):
        v1[n] = m - i
        for j in reversed(range(n)):
            a = src[i]
            b = tgt[j]
            if a == b:
                v1[j] = v0[j + 1]
            else:
                v1[j] = 1 + min(v1[j + 1], v0[j], v0[j + 1])

        v1, v0 = v0, v1

    return v0[0]

And that's all there is to it.

Addendum

I still have a few questions about why these algorithms work. For instance, why are we guaranteed to find the shortest sequence of moves by walking through the strings from start to finish? Is it obvious that there's nothing to be gained by first making some moves in the center of the source string, and then moving out towards the edges?

Backwards?

The implementations I've shown here are slightly different from the ones presented in the Wikipedia article. I wanted to keep the iterative and recursive algorithms as similar as possible; in the Wikipedia article, the recursive algorithm processes suffixes, whereas the iterative algorithms process prefixes. This isn't an issue, per se, but it does require convincing yourself that:

dist(src, tgt) == dist(src[::-1], tgt[::-1])

This seems totally reasonable, but it's not yet obvious to me...

Tools

I had a lot of fun building a few tools to help visualize these algorithms. The first, which renders the traces followed by the recursive implementation, is available at bin/trace.py. The second, which builds an HTML table showing the distance array populated by the iterative algorithm, is at bin/tabulate.py.

All of the code presented in this post and more is available on GitHub.

Priority Queues using Binary Heaps

William Lewis — Wed, 01 Sep 2021 19:30:32 +0000

Priority Queues using Binary Heaps

Suppose you want to write a task scheduler with the following properties: each task has a priority, tasks can be added in any order, and tasks should be removed according to their priority. A simple solution is to use an array and re-sort the elements every time a task is added. However, sorting is a lot of work, and — perhaps surprisingly — it's more work than needs to be done in this case. As we'll see, we still require some order, just not the total order of a sorted array. What we need is a binary heap.

Binary Heaps

“Heap” is unfortunately a rather ambiguous term, and doubly so in computing. For our purposes, a heap is nothing more than a binary tree with a special property. Specifically, a binary tree is a heap if every parent node is greater than or equal to its children.

Here's a heap:

And another:

Notice that in both cases, the greatest element (9) appears at the root. This is always the case: the greatest element in a heap can't have a parent, because each parent must be greater than or equal to its children. So it must be at the root. Furthermore, each subtree in the examples above has the heap property. This is also a necessary property of heaps.

Here are some trees that don't have the heap property:

In the first tree, 6 is a parent of 9, and 2 is a parent of 5. These are two violations of the heap property. What about the second tree, in which every parent is greater than or equal to its children? This tree fails to satisfy an additional property that heaps must have that we haven't yet mentioned. For reasons which will soon be made clear, we want heaps to be nice and compact, so in addition to the “heap property” outlined above, we also require that every generation be “filled”, except for possibly the last. Furthermore, if the last generation is not filled, we require that the nodes in it be “packed” to the left.

Adding and Removing Elements

At this point, heaps appear to be little more than binary trees with some rather arbitrary qualities. However, recall that the largest element in a heap is always at the root. To return to our motivating example (a scheduler), if we have a collection of tasks arranged in a heap, then the highest priority task is always located at the root. To return the highest priority task then, we simple remove and return the root.

But now we no longer have a heap. We'd like to combine the leftovers into a new heap, so that the next time we want to remove the highest priority task, we can simply pluck off the root as we did here.

This is where the (perhaps arbitrary-seeming) heap property shines. We first move the bottom-most, left-most element into the root position.

Now we've reconnected our tree, but the tree is not a heap. To restore the heap property, we first compare the new root element with its two children.

If it's smaller than either (and it's smaller than both in this case), we swap it with its larger child (6).

We then continue, with our focus now on the subtree into which we swapped the root. We compare the subtree's root (2) with its children (1 and 1).

But since the root is greater than or equal to both children, we stop. We've successfully restored the heap property.

This process of repeatedly comparing the tree's root with its children and swapping if necessary is called “sifting down”, and it converts any “compact” (in the sense described above) binary tree into a heap.

How does it work? After removing the root, we are left with two disconnected subtrees, but these subtrees are themselves both heaps. We then replaced the root with the bottom-most, left-most element (the only reason we choose this element is because it's the only one we can remove without destroying the tree's “compactness”). If this new root is greater than or equal to both its children, the new tree is a heap (since the root is greater than its children, which are greater than their children, and so on). If it's smaller than one of its children, we swap it with the greater of its two children. After this swap, the greatest element in the tree now sits at the root, and every element in the “unswapped” subtree is smaller than the new root element. Now only the “swapped” subtree needs to be re-heaped. We stop when either the root is greater than or equal to its children, or we reach the bottom of the tree.

In the worst case, how many iterations does this require? At most log(n), where n is the number of nodes in the tree. This is (potentially) significantly faster than re-sorting all of the elements, which might take n * log(n) steps.

How about adding new elements to a heap? We'll again need to re-heap the tree, but this time starting with the added element. This process is called “sifting up” and should have a familiar feel to it.

We add new elements in the bottom-most, left-most position (starting a new generation if necessary).

We then compare the new element with its parent.

If it's greater (as it is here), we swap the two; otherwise, we stop.

We then repeat this process.

This time, however, the element is not greater than its parent, so we're done. The heap property has been restored.

Sifting up works for more-or-less the same reason that sifting down does. In particular, it relies heavily on the fact that subtrees of heaps are themselves heaps. There's also a subtle point to be made here. Notice how the first two example heaps contain the exact same elements; they both have the heap property, and yet they're different trees. Unlike sorted arrays, which are uniquely determined by their elements, heaps permit a looser, more fluid organization. In a sense, the heap property requires just the right amount of order. As a result, re-heaping is quick.

A Compact Representation

Now that we understand the essential operations on heaps, we're ready to think about representation. “Compact” binary trees, like the ones we're interested in here, permit a particularly efficient implicit representation. While a more general recursive representation will do, the one we'll show here is far better in terms of both memory usage and cache-locality.

Specifically, a “compact” binary tree — in which every generation except for possibly the last is completely filled — can be represented using nothing more than an array with one element for each item in the tree. To encode a tree, its elements are stored in a breadth-first order: first the root, then its two children, then the nodes in the next generation, etc.

Here's the first example heap from above, along with its implicit array representation:

Using this represention, the left child of the node stored at index i is located at index 2i + 1, and the right child at 2i + 2. The parent of the node at index i is located at index ⌊(i - 1) / 2⌋, where ⌊n⌋ is the familiar "floor" function.

As an example, look at the node whose value is 6. It's stored at index 1, so its children can be found at indexes 2 * 1 + 1 = 3 and 2 * 1 + 2 = 4. Likewise, the node whose value is 2 is stored at index 5, and its parent — 5 — can be found at index ⌊(5 - 1) / 2⌋ = 2.

An Implementation in TypeScript

Let's see how to implement this in TypeScript. We'll start with this basic skeleton:

class BinaryHeap {
  private elements: number[] = [];

  isEmpty(): boolean {
    throw new Error('unimplemented');
  }

  push(x: number) {
    throw new Error('unimplemented');
  }

  peek(): number | null {
    throw new Error('unimplemented');
  }

  pop(): number | null {
    throw new Error('unimplemented');
  }
}

Note that we've decided to return null in the event that a user peeks or pops an empty heap. Alternatively, we could throw an error, or return something like Rust's Option type.

We'll store the data in our heap using the elements array. So to check if the heap is empty, we simply need to check if the elements array has length 0:

isEmpty(): boolean {
  return this.elements.length === 0;
}

Let's tackle pop next. If the heap is empty, we'll simply return null. If it's not, we need to remove the element at index 0 (this is the root), move the element at the last index (this is the bottom-most, left-most node) to index 0, and “sift down”. Finally, we'll return the previous root element.

class BinaryHeap {
  // ...

  pop(): number | null {
    if (this.elements.length === 0) {
      return null;
    }

    // Save the current root
    const root = this.elements[0];

    const last = this.elements.pop() as number;
    if (root !== last) {
      // Move the bottom-most, left-most node into the root's position
      this.elements[0] = last;

      // Sift down
      this.siftDown();
    }

    return root;
  }

  private siftDown() {
    throw new Error('unimplemented');
  }

  // ...
}

Remember how siftDown works: we compare a parent node to its children. If either of the children is greater than the parent, we swap the parent with the greater of the two. We stop whenever the current parent node is greater than or equal to its children (or has no children). Here's what that looks like:

private siftDown() {
  // Start at the root
  let parentIndex = 0;

  while (true) {
    const lChildIndex = 2 * parentIndex + 1;
    const rChildIndex = 2 * parentIndex + 2;

    const parentValue = this.elements[parentIndex];
    const lChildValue = this.elements[lChildIndex];
    const rChildValue = this.elements[rChildIndex];

    if (
      (lChildValue && lChildValue > parentValue) ||
      (rChildValue && rChildValue > parentValue)
    ) {
      // A swap is required
      if (rChildValue && rChildValue > lChildValue) {
        // Swap with right child
        this.elements[rChildIndex] = parentValue;
        this.elements[parentIndex] = rChildValue;
        parentIndex = rChildIndex;
      } else {
        // Swap with left child
        this.elements[lChildIndex] = parentValue;
        this.elements[parentIndex] = lChildValue;
        parentIndex = lChildIndex;
      }
    } else {
      // The parent is greater than its children (or has none)
      break;
    }
  }
}

By way of a break, let's implement peek next. Since the root is stored at index 0, peek just needs to return this value (or null if the heap is empty).

peek(): number | null {
  if (this.elements.length === 0) {
    return null;
  }

  return this.elements[0];
}

All that's left is push:

class BinaryHeap {
  // ...

  push(x: number) {
    // Add the new element at the bottom-most, left-most position in the tree
    this.elements.push(x);

    // Then sift up
    this.siftUp();
  }

  private siftUp() {
    throw new Error('unimplemented');
  }

  // ...
}

Compared to siftDown, siftUp is easy:

siftUp() {
  // Start at the most recently added node
  let focusedIndex = this.elements.length - 1;

  while (focusedIndex > 0) {
    const parentIndex = Math.floor((focusedIndex - 1) / 2);

    const focusedValue = this.elements[focusedIndex];
    const parentValue = this.elements[parentIndex];

    if (focusedValue > parentValue) {
      // A swap is required
      this.elements[focusedIndex] = parentValue;
      this.elements[parentIndex] = focusedValue;
      focusedIndex = parentIndex;
    } else {
      // The focused node is not greater than its parent
      break;
    }
  }
}

Here's the complete implementation.

Generalizing the Element Type

At the moment, our BinaryHeap is not very useful. It can only store numbers, whereas in many cases we'd like to store richer types of things. Fortunately, it's not difficult to generalize our current class to handle any type of element as long as it can be compared.

First, let's parameterize our class by some type variable A:

class BinaryHeap<A> {
  // ...
}

We need to update the type of the elements array: where it previously stored only numbers, we'll now store A's. We'll also have the user provide a comparator function when constructing a heap, which we'll store for later use in siftUp and siftDown.

class BinaryHeap<A> {
  private elements: A[] = [];

  constructor(private greaterThan: (x: A, y: A) => boolean) {}

  // ...
}

Now all that remains is to replace each appropriate occurrence of > with the user-provided greaterThan function. We also need to update the signatures of push, pop, and peek to expect and return elements of type A, instead of numbers:

class BinaryHeap<A> {
  private elements: A[] = [];

  constructor(private greaterThan: (x: A, y: A) => boolean) {}

  isEmpty(): boolean {
    return this.elements.length === 0;
  }

  push(x: A) {
    this.elements.push(x);
    this.siftUp();
  }

  private siftUp() {
    let focusedIndex = this.elements.length - 1;

    while (focusedIndex > 0) {
      const parentIndex = Math.floor((focusedIndex - 1) / 2);

      const focusedValue = this.elements[focusedIndex];
      const parentValue = this.elements[parentIndex];

      if (this.greaterThan(focusedValue, parentValue)) {
        this.elements[focusedIndex] = parentValue;
        this.elements[parentIndex] = focusedValue;
        focusedIndex = parentIndex;
      } else {
        break;
      }
    }
  }

  peek(): A | null {
    if (this.elements.length === 0) {
      return null;
    }

    return this.elements[0];
  }

  pop(): A | null {
    if (this.elements.length === 0) {
      return null;
    }

    const root = this.elements[0];
    const last = this.elements.pop() as A;
    if (root !== last) {
      this.elements[0] = last;
      this.siftDown();
    }

    return root;
  }

  private siftDown() {
    let parentIndex = 0;

    while (true) {
      const lChildIndex = 2 * parentIndex + 1;
      const rChildIndex = 2 * parentIndex + 2;

      const parentValue = this.elements[parentIndex];
      const lChildValue = this.elements[lChildIndex];
      const rChildValue = this.elements[rChildIndex];

      if (
        (lChildValue && this.greaterThan(lChildValue, parentValue)) ||
        (rChildValue && this.greaterThan(rChildValue, parentValue))
      ) {
        if (rChildValue && this.greaterThan(rChildValue, lChildValue)) {
          this.elements[rChildIndex] = parentValue;
          this.elements[parentIndex] = rChildValue;
          parentIndex = rChildIndex;
        } else {
          this.elements[lChildIndex] = parentValue;
          this.elements[parentIndex] = lChildValue;
          parentIndex = lChildIndex;
        }
      } else {
        break;
      }
    }
  }
}

Now, given some Task type, perhaps defined like so:

interface Task {
  priority: number;
  name: string;
}

we can create a BinaryHeap capable of storing tasks:

const heap = new BinaryHeap<Task>((t1, t2) => t1.priority > t2.priority);

heap.push({ priority: 4, name: 'warning' });
heap.push({ priority: 8, name: 'meltdown' });
heap.push({ priority: 1, name: 'todo' });
heap.push({ priority: 9, name: '!' });

console.log(heap.pop()); // => { priority: 9, name: '!' }
console.log(heap.pop()); // => { priority: 8, name: 'meltdown' }

Closing Thoughts

What we've shown here is a max heap; the opposite (dual?) of a max heap is a min heap, for which the heap property is reversed: every parent node is less than or equal to its children. What if you need a min heap but all you have is a max heap? All is not lost, since one can be converted into the other by picking the appropriate comparator (> for a max heap, and < for a min heap).

Binary heaps often appear in “real-time” systems in which tasks are constantly created and need to be handled according to their priority. As an example, React uses a binary heap in its scheduler package. The scheduler determines when various UI-related updates should be performed.

DEV Community: William Lewis

Pretty-Printing is Compilation

Overview

Printer Assembly Language

The Doc Language (Teaser)

An Intermediate Representation

The Compiler (Finally)

Putting it all Together

How to "Program" in Doc

Bells and Whistles

Sum Types in Python

Representing Sum Types

Implementing match

Implementing enum

Bonus Features

More Dunder Methods

Recursive Definitions

Conclusion

Arithmetic with Uncertainty

Arithmetic with Uncertainty

Dependence

Losing Information

Addendum

Introduction

Disjoint Unions in C

Unions

Back to Binary Trees

Playing with Trees

Tradeoffs

Levenshtein Distance

A Simple Recursive Algorithm

A Levenshtein Machein

Speeding Things Up

Memoize?

Dynamic Programming

Using Less Space

Addendum

Backwards?

Tools

Priority Queues using Binary Heaps

Priority Queues using Binary Heaps

Binary Heaps

Adding and Removing Elements

A Compact Representation

An Implementation in TypeScript

Generalizing the Element Type

Closing Thoughts

Implementing `match`

Implementing `enum`