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

# Author Archives: jeremygibbons

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

## Upwards and downwards accumulations

Continuing my work in regress, this post revisits—with the benefit of much hindsight—what I was working on for my DPhil thesis (which was summarized in a paper at MPC 1992) and in subsequent papers at MPC 1998 and in SCP … Continue reading

Posted in Uncategorized
2 Comments

## Distributivity in Horner’s Rule

This is a continuation of my previous post on Horner’s Rule, and in particular, of the discussion there about distributivity in the datatype-generic version of the Maximum Segment Sum problem: the essential property behind Horner’s Rule is one of distributivity. … Continue reading

Posted in Uncategorized
2 Comments

## Horner’s Rule

This post is about my all-time favourite calculation, of a linear-time algorithm for the maximum segment sum problem, based on Horner’s Rule. The problem was popularized in Jon Bentley’s Programming Pearls series in CACM (and in the subsequent book), but … Continue reading

Posted in Uncategorized
6 Comments

## Morality and temptation

Inspired by Bob Harper’s recent postings, I too have a confession to make. I know what is morally right; but sometimes the temptation is too great, and my resolve is weak, and I lapse. Fast and loose reasoning may excuse … Continue reading

Posted in Uncategorized
5 Comments

## Extreme solutions

Not all problem statements are amenable to translation via Galois connections or adjunctions. A reasonable characterization of those that are suitable is the optimization problems—finding the least or greatest solution satisfying a given collection of constraints, according to some ordering. … Continue reading

Posted in Uncategorized
6 Comments

## Adjunctions

Universal properties are a generalization of the notion of a Galois connection between two orderings. Or perhaps I should say: universal properties arise from adjunctions, and it is adjunctions that are a generalization of Galois connections. Adjunctions capture in an … Continue reading

Posted in Uncategorized
5 Comments

## Universal properties and Galois connections

One recurring theme throughout this series will be that of a universal property—an identity that captures an indirect means of solving a problem, by transforming that problem into a different (and hopefully simpler) domain, while still preserving all its essential … Continue reading

Posted in Uncategorized
3 Comments

## Lenses are the coalgebras for the costate comonad

I took part in the Dagstuhl Seminar on Bidirectional Transformations “BX” earlier this month. It was a meeting of people from four communities—databases, graph transformations, programming languages, and software engineering—discussing their various perspectives—namely the view–update problem in databases, triple graph … Continue reading

Posted in Uncategorized
6 Comments