Author Archives: alistairjwall

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 muchContinue reading “Countdown 2”

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, andContinue reading “Countdown”

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 areContinue reading “Free Monads”

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”

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”

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”

This was inspired by Tsoder’s video https://www.youtube.com/watch?v=Qf4NyHiy0W8 where he generated all the 3×3 magic squares by brute force, generating all permutations of 1-9 and rejecting the ones which were not magic squares. My first reaction was that that was not brute force; this was brute force: This turned out to be faster than Tsoder’s method,Continue reading “Magic Square by brute force”

FizzBuzz is a cut-down version of Eratosthenes’ sieve, which started as a drinking game and is now often used as an interview question. The rules are that you start counting, and replace numbers by Fizz if they are divisible by three, Buzz if they are divisible by five, and FizzBuzz if divisible by both. TheContinue reading “FizzBuzz”