Attribute Grammars with Monads

Attribute grammars evaluate recursive data structures where inherited attributes are passed from the root to the leaves, and synthesised attributes are calculated in the leaves and passed back to the root. In “Beginning Haskell” pp343-4 (Apress ISBN 978-1-4302-6250-3), Alejandro Serrano Mena briefly discusses implementing attribute grammars using the Reader and Writer monads. He does notContinue reading “Attribute Grammars with Monads”

Observations of Kirch’s comet 1680-81

The observations Newton used to calculate the orbit of Kirch’s comet can be found in the tables in page 491. Observations up to 5 February are by Flamsteed; later observations are by Newton. Different versions of these tables exist. This version is sufficient to demonstrate the calculation. I have not found the Newton Project’sContinue reading “Observations of Kirch’s comet 1680-81”

Installing Diagrams

In preparation for my forthcoming series reproducing Newton’s calculation of the orbit of Kirch’s comet, I have been investigating Brent Yorgey’s Diagrams package. After successfully running the tutorial example in once, I had difficulties using it in new projects (and even reproducing the tutorial), for possibly related reasons: I usually use stack for development,Continue reading “Installing Diagrams”


This post is based on chapter 9 of The game of countdown is to combine a list of integers using common operations to make a target. The allowed operations are +, -, * and /, with the restrictions that the result of a subtraction (even as an intermediate value) must not be negative, andContinue reading “Countdown”

Jug Puzzles

Jug problems are a popular puzzle: given a set of jugs with distinct* integral capacities that are otherwise unmarked, measure out a specified integral volume of liquid. For example, you may have jugs with capacities of 5, 8 and 12 litres (Americans may substitute gallons, and Texans may substitute hats for jugs) and be askedContinue reading “Jug Puzzles”

Free Monads

Free monads are monads with the bare minimum of properties. They are useful because they can be chained together and interpreted in different ways. The example below shows a program with two interpreters: one that executes the program and one that prints it out. The best introduction I have found is Free monads areContinue reading “Free Monads”

My first monad tutorial

Most books and web tutorials devote a lot of attention to deriving monads, and only briefly show how they are used in real life. For instance, here is Graham Hutton relabelling a tree with integers: Bear in mind that monads are supposed to make programming easier. Here, without confusing explanations, is how to do itContinue reading “My first monad tutorial”

Permutations with constraints – magic square

Starting from my previous post, I add code to apply constraints as permutations are being generated. This is still faster than Tsoder’s brute force method, but slower than my list comprehension methods. I like the way permutations and constraints are separated I dislike the way the constraints are based on the recursion depth, which keepsContinue reading “Permutations with constraints – magic square”

Permutations with constraints

In order to apply constraints while generating permutations, I needed a new algorithm. Haskell’s library function Data.List.permutations builds permutations using interleave, so each item added could end up anywhere in the list. I needed items to stay in the same place once chosen. Note that this performs much worse than Data.List.permutations, because it has toContinue reading “Permutations with constraints”