Algebras for Weighted Search

Donnacha Oisín Kidney & Nicolas Wu · ICFP 2021 · ACM

Prereqs: 🍞 Fritz 2020 (Kleisli composition). Familiarity with monads helps.

Weighted search is parameterized by a semiring. Choose the semiring and you choose the semantics: natural numbers for counting, reals in [0,1] for probability, booleans for reachability. One monad, many interpretations.

The free semimodule monad

A weighted collection assigns a weight from a semiring S to each element. When S = ℕ, you're counting occurrences. When S = [0,1] with ordinary multiplication, you're assigning probabilities. The free semimodule monad over S captures all of these at once.

Semiring	Values	Zero	One	Plus	Times	Meaning
Probability	[0,1]	0	1	+	×	how likely
Counting	ℕ	0	1	+	×	how many ways
Search	Bool	false	true	or	and	is it reachable

Scheme

; A weighted collection: list of (value . weight) pairs
; The semiring determines what weights mean

; S = natural numbers: counting
(define counting-bag
  '((apple . 3) (banana . 1) (apple . 2)))

; S = [0,1]: probability
(define prob-dist
  '((heads . 0.5) (tails . 0.5)))

; S = boolean: reachability (true/false)
(define reachable
  '((state-A . #t) (state-B . #t) (state-C . #f)))

(display "counting: ") (display counting-bag) (newline)
(display "probability: ") (display prob-dist) (newline)
(display "reachability: ") (display reachable) (newline)
; Same structure, different semiring

Python

# Weighted collections parameterized by semiring
counting = {"apple": 3, "banana": 1}   # S = ℕ
prob = {"heads": 0.5, "tails": 0.5}    # S = [0,1]
reach = {"A": True, "B": True, "C": False}  # S = Bool

print("counting:", counting)
print("probability:", prob)
print("reachability:", reach)

Bind over different semirings

Monadic bind (>>=) for weighted search: for each element, apply the function and multiply weights. The semiring's multiplication combines the weights. Its addition collects duplicates.

Scheme

; Bind: apply f to each element, multiply weights
; Then collect duplicates with semiring addition

(define (weighted-bind bag f s-times s-plus s-zero)
  ; f returns a weighted collection for each value
  (let ((raw (apply append
    (map (lambda (pair)
      (let ((v (car pair)) (w (cdr pair)))
        (map (lambda (fp)
          (cons (car fp) (s-times w (cdr fp))))
        (f v))))
    bag))))
    ; Collect duplicates
    (let ((result '()))
      (for-each (lambda (p)
        (let ((existing (assoc (car p) result)))
          (if existing
            (set-cdr! existing (s-plus (cdr existing) (cdr p)))
            (set! result (cons (cons (car p) (cdr p)) result)))))
      raw)
      result)))

; S = ℕ: counting paths
(define (count-paths x)
  (list (cons (+ x 1) 1) (cons (+ x 2) 1)))

(define start '((0 . 1)))
(define step1 (weighted-bind start count-paths * + 0))
(define step2 (weighted-bind step1 count-paths * + 0))

(display "paths from 0:") (newline)
(display "  step1: ") (display step1) (newline)
(display "  step2: ") (display step2) (newline)
; Weights count how many paths reach each state

; Bind: apply f to each element, multiply weights
; Then collect duplicates with semiring addition

(define (weighted-bind bag f s-times s-plus s-zero)
  ; f returns a weighted collection for each value
  (let ((raw (apply append
    (map (lambda (pair)
      (let ((v (car pair)) (w (cdr pair)))
        (map (lambda (fp)
          (cons (car fp) (s-times w (cdr fp))))
        (f v))))
    bag))))
    ; Collect duplicates
    (let ((result '()))
      (for-each (lambda (p)
        (let ((existing (assoc (car p) result)))
          (if existing
            (set-cdr! existing (s-plus (cdr existing) (cdr p)))
            (set! result (cons (cons (car p) (cdr p)) result)))))
      raw)
      result)))

; S = ℕ: counting paths
(define (count-paths x)
  (list (cons (+ x 1) 1) (cons (+ x 2) 1)))

(define start '((0 . 1)))
(define step1 (weighted-bind start count-paths * + 0))
(define step2 (weighted-bind step1 count-paths * + 0))

(display "paths from 0:") (newline)
(display "  step1: ") (display step1) (newline)
(display "  step2: ") (display step2) (newline)
; Weights count how many paths reach each state

Python

# Bind with different semirings
from collections import defaultdict

def weighted_bind(bag, f, times, plus):
    result = defaultdict(lambda: 0)
    for v, w in bag.items():
        for v2, w2 in f(v).items():
            result[v2] = plus(result[v2], times(w, w2))
    return dict(result)

# Counting paths (S = ℕ)
f = lambda x: {x+1: 1, x+2: 1}
bag = {0: 1}
step1 = weighted_bind(bag, f, int.__mul__, int.__add__)
step2 = weighted_bind(step1, f, int.__mul__, int.__add__)
print(f"counting paths: {bag} -> {step1} -> {step2}")

# Probability (S = [0,1])
g = lambda x: {x+1: 0.6, x+2: 0.4}
prob = {0: 1.0}
p1 = weighted_bind(prob, g, float.__mul__, float.__add__)
print(f"probability: {prob} -> {p1}")

Semiring = ℕ gives counting

When S = ℕ (natural numbers with +, ×), weights count multiplicity. Bind sums the number of paths reaching each state. This is nondeterministic search with counting.

Scheme

; S = ℕ: how many ways to reach each value?
; Fibonacci-like: from n, go to n+1 or n+2

(define (step x)
  (list (cons (+ x 1) 1) (cons (+ x 2) 1)))

(define (bind-nat bag f)
  (let ((raw (apply append
    (map (lambda (p)
      (map (lambda (fp) (cons (car fp) (* (cdr p) (cdr fp))))
           (f (car p))))
    bag))))
    (let ((result '()))
      (for-each (lambda (p)
        (let ((e (assoc (car p) result)))
          (if e (set-cdr! e (+ (cdr e) (cdr p)))
                (set! result (cons (cons (car p) (cdr p)) result)))))
      raw) result)))

(define s0 '((0 . 1)))
(define s1 (bind-nat s0 step))
(define s2 (bind-nat s1 step))
(define s3 (bind-nat s2 step))

(display "step 0: ") (display s0) (newline)
(display "step 1: ") (display s1) (newline)
(display "step 2: ") (display s2) (newline)
(display "step 3: ") (display s3) (newline)
; Weights are path counts — Fibonacci numbers appear

Python

# S = ℕ: counting paths — Fibonacci numbers appear
from collections import defaultdict

def bind_nat(bag, f):
    result = defaultdict(int)
    for v, w in bag.items():
        for v2, w2 in f(v).items():
            result[v2] += w * w2
    return dict(result)

step = lambda x: {x+1: 1, x+2: 1}

s0 = {0: 1}
s1 = bind_nat(s0, step)
s2 = bind_nat(s1, step)
s3 = bind_nat(s2, step)

for i, s in enumerate([s0, s1, s2, s3]):
    print(f"step {i}: {dict(sorted(s.items()))}")
# Weights are path counts — Fibonacci numbers appear

Semiring = [0,1] gives probability

When S = [0,1] with ordinary multiplication and addition (capped at 1 for subdistributions), weights are probabilities. Bind marginalizes over intermediate states. This recovers 🐱 Kleisli composition from 🍞 Fritz 2020.

Scheme

; S = [0,1]: weights are probabilities
; Bind = Kleisli composition = marginalization

(define (coin x)
  (list (cons (+ x 1) 0.6) (cons (+ x 2) 0.4)))

(define (bind-prob bag f)
  (let ((raw (apply append
    (map (lambda (p)
      (map (lambda (fp) (cons (car fp) (* (cdr p) (cdr fp))))
           (f (car p))))
    bag))))
    (let ((result '()))
      (for-each (lambda (p)
        (let ((e (assoc (car p) result)))
          (if e (set-cdr! e (+ (cdr e) (cdr p)))
                (set! result (cons (cons (car p) (cdr p)) result)))))
      raw) result)))

(define start '((0 . 1.0)))
(define after1 (bind-prob start coin))
(define after2 (bind-prob after1 coin))

(display "start: ") (display start) (newline)
(display "after 1 coin: ") (display after1) (newline)
(display "after 2 coins: ") (display after2) (newline)
; This IS Kleisli composition — same as Fritz's setup

Python

# S = [0,1]: weights are probabilities — Kleisli composition

from collections import defaultdict

def bind_prob(bag, f):
    result = defaultdict(float)
    for v, w in bag.items():
        for v2, w2 in f(v).items():
            result[v2] += w * w2
    return dict(result)

coin = lambda x: {x + 1: 0.6, x + 2: 0.4}

start = {0: 1.0}
after1 = bind_prob(start, coin)
after2 = bind_prob(after1, coin)

fmt = lambda d: {k: round(v, 4) for k, v in sorted(d.items())}
print(f"start:   {fmt(start)}")
print(f"after 1: {fmt(after1)}")
print(f"after 2: {fmt(after2)}")
print(f"sum = {sum(after2.values()):.3f} (probability sums to 1)")

Notation reference

Paper	Scheme	Meaning
S	; semiring (ℕ, [0,1], Bool)	Weight semiring
S⟨X⟩	'((val . weight) ...)	Free semimodule (weighted bag)
>>=	(weighted-bind bag f ...)	Monadic bind (multiply then collect)
η(x)	(list (cons x 1))	Return (singleton with unit weight)
⊕, ⊗	+, *	Semiring addition and multiplication

Neighbors

Other paper pages

🍞 Fritz 2020 — S=[0,1] recovers FinStoch and Kleisli composition
🍞 Baez, Fritz, Leinster 2011 — entropy as information loss under S=[0,1]
🍞 Leinster 2021 — diversity as magnitude, related semiring structures

Foundations (Wikipedia)

Translation notes

The examples use association lists with explicit semiring operations. Kidney and Wu work with free semimodule monads in Haskell, using type classes to abstract over the semiring. For example: the counting example above uses an explicit loop with set-cdr! to merge duplicates. In the paper, this is the free semimodule's universal property — the unique algebra morphism that folds a formal sum into a concrete semiring value. The computation is the same; the universality guarantee is not.

Every example is Simplified.

Ready for the real thing? Read the paper (ICFP 2021). Start at §3 for the free semimodule monad, §5 for the semiring-parameterized search.

← Jacobs 2014 · 12 of 21 by june.kim Leinster 2021 · 14 of 21 →