Category Archives: thinking

Stroll: an experimental build system

algorithms, coding, thinking

I’d like to share an experiment in developing a language-agnostic build system that does not require the user to specify dependencies between individual build tasks. By “language-agnostic” I mean the user does not need to learn a new language or a special file format for describing build tasks — existing scripts or executable files can be used as build tasks directly without modification.

I call this build system Stroll because its build algorithm reminds me of strolling through a park where you’ve never been before, trying to figure out an optimal path to your target destination, and likely going in circles occasionally until you’ve built up a complete mental map of the park.

Continue reading Stroll: an experimental build system →

United Monoids

coding, math, thinking,

In this blog post we will explore the consequences of postulating 0 = 1 in an algebraic structure with two binary operations (S, +, 0) and (S, ⋅, 1). Such united monoids have a few interesting properties, which are not immediately obvious. For example, we will see that the axiom 0 = 1 is equivalent to a seemingly less extravagant axiom ab = ab + a, which will send us tumbling down the rabbit hole of algebraic graphs and topology.

Continue reading United Monoids →

Selective applicative functors

coding, thinking

Update: I have written a paper about selective applicative functors, and it completely supersedes this blog post (it also uses a slightly different notation). You should read the paper instead.

I often need a Haskell abstraction that supports conditions (like Monad) yet can still be statically analysed (like Applicative). In such cases people typically point to the Arrow class, more specifically ArrowChoice, but when I look it up, I find several type classes and a dozen of methods. Impressive, categorical but also quite heavy. Is there a more lightweight approach? In this blog post I’ll explore what I call selective applicative functors, which extend the Applicative type class with a single method that makes it possible to be selective about effects.

Please meet Selective:

class Applicative f => Selective f where
    handle :: f (Either a b) -> f (a -> b) -> f b

Think of handle as a selective function application: you apply a handler function of type a → b when given a value of type Left a, but can skip the handler (along with its effects) in the case of Right b. Intuitively, handle allows you to efficiently handle errors, i.e. perform the error-handling effects only when needed.

Continue reading Selective applicative functors →

Inverting the universe with two inverters

thinking,

Recently I came across an interesting puzzle from MIT Tech Review March/April 2013:

Howard Cohen has plenty of AND and OR gates but just two inverters. How can he invert three signals a, b, and c?

More generally, he wonders if the ratio I/S can ever be less than 2/3, where I is the number of inverters and S is the number of signals to invert (once again, unlimited AND and OR gates are available).

I couldn’t quickly solve the first part of the puzzle with a pen and paper, so I decided to write a brute force solver. And to make it a bit more fun I did it in Haskell (any suggestions for improving the code are welcome, by the way!).

Continue reading Inverting the universe with two inverters →