Where to Start
This blog probably makes most sense read in forwards chronological order rather than backwards, especially if you're new to the material; in that case, you might want to start at the beginning.
Category Archives: Uncategorized
Richard Bird, 1943-2022
My mentor, colleague, and friend Richard Bird died in April 2022 after a long battle with cancer. I wrote an obituary of him for The Guardian, his favoured newspaper; this post is a hybrid of that obituary and a eulogy … Continue reading
Posted in Uncategorized
Leave a comment
The Genuine Sieve of Eratosthenes
The “Sieve of Eratosthenes” is often used as a nice example of the expressive power of streams (infinite lazy lists) and list comprehensions: That is, takes a stream of candidate primes; the head of this stream is a prime, and … Continue reading
Posted in Uncategorized
2 Comments
How to design co-programs
I recently attended the Matthias Felleisen Half-Time Show, a symposium held in Boston on 3rd November in celebration of Matthias’s 60th birthday. I was honoured to be able to give a talk there; this post is a record of what … Continue reading
Posted in Uncategorized
17 Comments
Folds on lists
The previous post turned out to be rather complicated. In this one, I return to much simpler matters: and on lists, and list homomorphisms with an associative binary operator. For simplicity, I’m only going to be discussing finite lists. Fold … Continue reading
Posted in Uncategorized
5 Comments
Asymmetric Numeral Systems
The previous two posts discussed arithmetic coding (AC). In this post I’ll discuss a related but more recent entropy encoding technique called asymmetric numeral systems (ANS), introduced by Jarek Duda and explored in some detail in a series of 12 … Continue reading
Posted in Uncategorized
3 Comments
Streaming Arithmetic Coding
In the previous post we saw the basic definitions of arithmetic encoding and decoding, and a proof that decoding does indeed successfully retrieve the input. In this post we go on to show how both encoding and decoding can be … Continue reading
Posted in Uncategorized
5 Comments
Arithmetic Coding
This post is about the data compression method called arithmetic coding, by which a text is encoded as a subinterval of the unit interval, which is then represented as a bit sequence. It can often encode more effectively than Huffman … Continue reading
Posted in Uncategorized
4 Comments
The Digits of Pi
In the previous post we were introduced to metamorphisms, which consist of an unfold after a fold—typically on lists, and the fold part typically a . A canonical example is the conversion of a fraction from one base to another. … Continue reading
Posted in Uncategorized
4 Comments
Metamorphisms
It appears that I have insufficient time, or at least insufficient discipline, to contribute to this blog, except when I am on sabbatical. Which I now am… so let’s see if I can do better. Hylomorphisms I don’t think I’ve … Continue reading
Posted in Uncategorized
8 Comments
Breadth-First Traversal
Recently Eitan Chatav asked in the Programming Haskell group on Facebook What is the correct way to write breadth first traversal of a ? He’s thinking of “traversal” in the sense of the class, and gave a concrete declaration of … Continue reading
Posted in Uncategorized
9 Comments