Exploiting the relationship between data structure and program structure
So, evidently I failed to fulfill my ambition to blog regularly about the contents of my planned book on Patterns in Functional Programming. But I have been making progress. I had the privilege of another sabbatical 2024-2025, in which I Continue reading
My friend Alan Jeffrey passed away earlier this year. I described his professional life at a Celebration in Oxford on 2nd November 2024. This post is a slightly revised version of what I said. Edinburgh, 1983–1987 I’ve known Alan for Continue reading
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
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
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
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
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
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
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
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