I was playing around with `codeworld-api`

recently, and found myself with a pair of interesting problems:

- Place (move and scale) a grid (represented as a CodeWorld
`Picture`

) onto the canvas; and - When responding to mouse clicks on the grid, reverse the transformation that placed the grid, so that I can determine which grid cell was clicked.

Placing the picture is easy — `codeworld-api`

provides two functions that do exactly what I want:

`translated :: Double -> Double -> Picture -> Picture`

`scaled :: Double -> Double -> Picture -> Picture`

Going the other way is more difficult. After noodling around on paper trying to compute the inverse transform, I remembered that these transformations could be represented as 3x3 matrices (Wikipedia has some examples), and that inverting a 3x3 matrix is easy (provided that the affine transformation it represents hasn’t collapsed the space).

This means I have to compute the transformation twice: once as `codeworld-api`

calls, and once as matrices. Or do I?

Let’s invent a simple DSL instead. We’ll start by defining a type for our transformations:

We’ll also define the fold for `Transform`

, as this will make it much easier to implement one of our interpreters. These functions are often really handy as a compact way to do `case`

-analysis on a value:

```
-- Note: transform Scale Translate = id (over Transform)
-- , just as foldr (:) [] = id (over lists)
-- , and maybe Nothing Just = id (over Maybe a)
transform
:: (Double -> Double -> a) -- ^ Handle 'Scale'
-> (Double -> Double -> a) -- ^ Handle 'Translate'
-> Transform
-> a
transform f _ (Scale x y) = f x y
transform _ g (Translate x y) = g x y
```

Now, we need to interpret some `Transform`

s into either a matrix or a `codeworld-api`

function. In Haskell, DSLs are often associated with free monads and effect systems, but all we want is a linear sequence of commands, so a list will do fine.

Both interpretations are essentially `foldMap`

over different monoids:

- To construct a matrix, map each
`Transform`

into a matrix, then multiply them all together. - To construct a function
`Picture -> Picture`

, map each`Transform`

into such a function, then compose them all together.

Unfortunately, the `Monoid`

instances don’t give us what we want:

We’ll be using the matrix types and functions from Ed Kmett’s

`linear`

package, which considers matrices as vectors of vectors. The`Monoid`

instance for vectors is elementwise append; andThe

`Monoid`

instance for functions is`instance Monoid b => Monoid (a -> b)`

, which combines results. That’s not what we want either — we want the instance associated with the`Endo a`

newtype.

We could stand up a `newtype`

for matrix multiplication, but it’s a lot of syntactic noise for a single use. Having noted that these are both `foldMap`

, let’s move along and implement them manually.

Let’s start with `toMatrix :: [Transform] -> M33 Double`

. `M33 Double`

is the type of a 3x3 matrix of `Double`

(a 3-vector of (3-vectors of `Double`

)):

```
-- (!*!) is matrix multiplication
toMatrix :: [Transform] -> M33 Double
toMatrix list = foldr (!*!) identity $ map toMatrix' list
where
toMatrix' (Translate x y) = V3
(V3 1 0 x)
(V3 0 1 y)
(V3 0 0 1)
toMatrix' (Scale x y) = V3
(V3 x 0 0)
(V3 0 y 0)
(V3 0 0 1)
```

My friend Tony taught me (and many others) that `foldr`

performs *constructor replacement*. If we write the `(:)`

calls in prefix position, we can see that `map`

is expressible in terms of `foldr`

:

```
map f (x1 : x2 : [])
= f x1 : f x2 : [] -- Effect of `map`
= (:) (f x1) ((:) (f x2) []) -- Rewrite in prefix position
= ((:) . f) x1 (((:) . f) x2 []) -- Observing that g (f x) = (g . f) x
= foldr ((:) . f) [] (x1 : x2 : []) -- Noting that we replaced (:) with (:) . f
-- and we replaced [] with []
```

In our `toMatrix`

case, we’re using `map`

to:

- replace
`(:)`

with`(:) . toMatrix'`

; and - replace
`[]`

with`[]`

We then immediately replace `(:)`

with `(!*!)`

and `[]`

with `identity`

. This suggests that we can avoid folding twice, by:

- replacing
`(:)`

with`(!*!) . toMatrix'`

; and - replacing
`[]`

with`identity`

.

This works, and we can avoid explicitly naming and applying the `list`

argument while we’re at it (a process called *eta-reduction*):

```
toMatrix :: [Transform] -> M33 Double
toMatrix = foldr ((!*!) . toMatrix') identity
where
toMatrix' (Translate x y) = V3
(V3 1 0 x)
(V3 0 1 y)
(V3 0 0 1)
toMatrix' (Scale x y) = V3
(V3 x 0 0)
(V3 0 y 0)
(V3 0 0 1)
```

The interpreter for `codeworld-api`

functions only needs a couple of changes:

- We use
`transform`

to apply the arguments from`Transform`

’s construtors to the appropriate`codeworld-api`

functions (giving us functions`Picture -> Picture`

instead of matrices); and `(.)`

composes all the functions into one, like how we previously used`(!*!)`

to multiply all the matrices together.

```
toCodeWorld :: [Transform] -> Picture -> Picture
toCodeWorld = foldr ((.) . transform CodeWorld.translated CodeWorld.scaled) id
```

The rest is fairly mechanical. We can now write a canonical way to compute the `[Transform]`

that places the grid on the screen:

```
gridTransforms :: Grid -> [Transform]
gridTransforms g =
[ Scale (scaleFactor g) (scaleFactor g) -- Shrink to fit viewport
, toCenter g -- Centre it around the origin
]
```

Rendering the grid is done by interpreting the `[Transform]`

into a `Picture -> Picture`

and applying it to the drawn grid:

Finally, we convert screen coordinates to grid coordinates by interpreting the transforms into a matrix, inverting it, multiplying the inverse matrix with the screen coordinate (as a vector) and rounding the results:

```
fromPoint :: Grid -> Point -> Maybe (Int, Int)
fromPoint g (x, y)
| x' >= 0 && x' < w && y' >= 0 && y' < h = Just (x', y')
| otherwise = Nothing
where
(w, h) = (fromIntegral $ width g, fromIntegral $ height g)
(x', y') = (round invX, round invY)
-- inv33 inverts a 3x3 matrix, and (!*) is matrix-vector multiplication
V3 invX invY _ = inv33 (toMatrix (gridTransforms g)) !* V3 x y 1
```

Even in this relatively simple example, a small DSL saved us a lot of repeated work. It’s a useful technique to keep in your back pocket.

In hindsight, we used `[Transform]`

as an approximation to the free monoid over `Transform`

, which we then interpreted into the two types we cared about. (Reminder: lists are not free monoids, though they’re close enough for most purposes.) If this sort of thinking interests you, Justin Le has some great blog posts about free structures and the cool payoffs you can get when using them:

Solving a 2018 Advent of Code puzzle using free groups, and accidentally optimising the solution

Pulling a regular expression library almost out of thin air, using the free alternative

I would like to thank the Canberra Functional Programming (CanFP) meetup group, who reviewed drafts of this post.

I really like using Nix to build and manage my computers. Declarative machine definitions are incredibly powerful, and NixOS actually achieves what tools like Ansible and Chef have tried to reach for.

This web site is served from a NixOS machine, and is a collection of static files which get copied across by `nix copy`

when it sends the built NixOS expression to the server. Until recently, my built website lived in a single derivation, which meant that any time I changed anything, a full rebuild of the site would get sent up my terrible internet connection.

I have written a tool to split up the big derivation called `nix-freeze-tree`

(Hackage). It lets me split the website derivation down to individual files, and symlink them together back into the tree I want. The individual derivations are fixed-output derivations, which means that Nix knows the hash of the files before it builds the derivation, and can check the hash of the files to copy and skip files that haven’t changed.

If you’re reading this, then I’ve successfully wired `nix-freeze-tree`

into my site build pipeline and deployed it.

A few years back, I bought an Infinity Ergodox. I’ve been very happy with it, especially once I customised the firmware to add keybindings for my Haskell work.

Unfortunately, the kiibohd repos have broken Infinity Ergodox support for some time, and nobody seems to care. Getting a working build involves jumping through some hoops, and even then modern GCC has slightly different semantics for `inline`

functions, so it needs another patch on top of that.

Pulling all this together is the sort of thing that Nix excels at, so I threw together some Nix expressions to build the firmware, and to give me a shell with `dfu-util`

for flashing. I’ve uploaded them to SourceHut for reference.

Posted on October 31, 2019
by Jack Kelly

Android: Netrunner (A:NR) was one of Fantasy Flight’s “Living Card Games” (LCGs). These are a line of card games where you buy some base or “core” set of cards, and the publisher releases smaller additional packs each with a fixed set of cards.

In the early years of A:NR’s run, the single most controversial card was Account Siphon (“Siphon”), pictured below alongside other cards that synergised with it. A lot of words were written about Siphon, arguing that it was “overpowered”, or “balanced”, or “unfair”. In this article, I’m not going to argue those questions. I’m instead going to talk about how Siphon warped the rest of A:NR around itself, and that it is good to have cards like because they give a game something I call “texture”.

Read more...I am often annoyed by technical documentation that uses words like “just” and “simply” to prefix procedures that users are expected to perform. Such words are almost always waffle, and cutting them is almost always an improvement. When you see “just” or “simply”, you can be almost certain the action that follows is anything but. Instead of fixing the root problem, the documentation unconvincingly tries to paper over it.

“Just” and “simply” also insult the reader’s intelligence: the author is afraid that readers will run screaming if not constantly reassured that It Really Isn’t That Bad. If the instructions are deficient *in any way*, the reader will blame him or herself instead of the responsible party - the author. Again, there are better fixes: make the procedures *acutally* simple, and make the documentation *actually* clear and concise. Strunk and White may have gone out of fashion, but I believe that “omit needless words” is timeless. If you disagree, take it up with Orwell. (“If it is possible to cut a word out, always cut it out.”)

Just use the delete key and simply remove the offending words from documentation you write.