Advent of Code 2021 Day 16
https://adventofcode.com/2021/day/16 This is the hardest of the problems I have managed to solve. Some of the issues were: On the good side, Attoparsec can handle the non-context-free aspects (eg the functions packets0 and packets1). Almost every line of the solution can be linked back to the puzzle’s requirements – there is very little visible plumbing.…
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 not…
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 http://www.newtonproject.ox.ac.uk/view/texts/diplomatic/NATP00301 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’s…
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 https://diagrams.github.io/doc/quickstart.html#your-first-diagram once, I had difficulties using it in new projects (and even reproducing the tutorial), for possibly related reasons: I usually use stack for development,…
Countdown 2
In my previous post, I bodged a function to aggregate additions and multiplications into a program based on individual binary operations. This is what it looks like if it is designed to use Sum’ (the prime disambiguates it from the built-in monoid) and Prod from the beginning. It is only a little shorter, and much…
Countdown
This post is based on chapter 9 of https://www.cambridge.org/gb/academic/subjects/computer-science/programming-languages-and-applied-logic/programming-haskell-2nd-edition?format=PB. 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, and…
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 asked…
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 https://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html. Free monads are…
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 it…
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 keeps…
Loading…
Something went wrong. Please refresh the page and/or try again.
Follow My Blog
Get new content delivered directly to your inbox.
Great Wall 