### 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

## 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

## Comprehensions

Prompted by some recent work I’ve been doing on reasoning about monadic computations, I’ve been looking back at the work from the 1990s by Phil Trinder, Limsoon Wong, Leonidas Fegaras, Torsten Grust, and others, on monad comprehensions as a framework … Continue reading

Posted in Uncategorized
11 Comments