Category Archives: thinking

Selective applicative functors

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

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