Bitwise procedures are a fast and simple way to perform certain set operations. Purescript uses signed 4 byte integers, which means we can represent a set of up to 32 items by toggling the bits in a single Int value. If there were a set of three animals
{bat, cat, rat}
then it'd be possible to represent their presence by the number 7, which is
1 1 1
in binary form. Likewise, the set
{bat, rat}
could be represented by a value of 5, which has the following binary.
1 0 1
This bitwise representation makes itself useful in non-deterministic problem solving, where a set can be scored based upon how well it conforms to certain constraints. Seeking set permutations with lower scores can ultimately lead the program to a state that satisfies all criteria. Let's use a set of four animals this time.
{gnat, bat, cat, rat}
And assume we want a permutation of this set representing the animals in our house. There are two constraints.
That means that any of the following permutations are acceptable. The only two animals we're concerned with are the cat and the rat.
{cat}
{bat, cat}
{gnat, cat}
{gnat, bat, cat}
The bitwise AND operation can be used to determine the presence of a cat or rat in an arbitrary set.
{cat} = 0 0 1 0 = 2
{rat} = 0 0 0 1 = 1
{gnat, cat} = 1 0 1 0 = 10
{bat, rat} = 0 1 0 1 = 5
{gnat, cat, rat} = 1 0 1 1 = 11
2 AND 10 = 2 (the cat is in the set)
2 AND 5 = 0 (the cat is not in the set)
1 AND 10 = 0 (the rat is not in the set)
1 AND 11 = 1 (the rat is in the set)
Using AND with a mask value like 2 or 1 is not only a quick way to determine if a permutation is wrong, it can also tell you how wrong it is. Let's say we also want to exclude the gnat from our house. We can make a new mask that checks for the rat and the gnat at the same time.
{gnat, rat} = 1 0 0 1 = 9
9 AND 8 = 1 0 0 0 = 8 (the gnat is in the set)
9 AND 13 = 1 0 0 1 = 9 (the gnat and rat are in the set)
Counting the active bits from the results of these AND operations yields values of 1 and 2 respectively. The second state contains two illegal animals as opposed to one; it is less ideal. It is in the problem solver's interest to seek out the first state and its score of 1 over the second permutation's score of 2.
Likewise, if we wanted both a bat and a cat in our house
{bat, cat} = 0 1 1 0 = 6
6 AND 5 = 0 1 0 0 = 4 (the bat is in the set)
6 AND 7 = 0 1 1 0 = 6 (the bat and the cat are in the set)
The second state is also the ideal one here, but lower scores are better, so we can't simply count its active bits. We have to perform a XOR operation after the AND, using the constraint mask again. This will return the number of positive constraints left unsatisfied.
6 AND 5 XOR 6 = 2 (1 bit set)
6 AND 7 XOR 6 = 0 (no bits set; solved)
Using these bitwise tricks means that a set's local constraints can be scored in two checks, regardless of how many individual items are meant to be included or excluded.
Many languages have a built in function for counting the set bits in a number, but Purescript doesn't. I wrote the following procedure population that does so using Brian Kernighan's algorithm.
population :: Int → Int
population 0 = 0
population n = 1 + (population $ bitFlip n)
where bitFlip = and <*> (_ - 1)
This can run against the end of AND and XOR to calculate the final score of a permutation.
Theoretically speaking, counting the score of items that should be excluded from a set is a simple composition.
excluded = population <<< and
This function won't work, of course, because and is a dyadic procedure. Function composition takes place between operations with one parameter.
(<<<) :: ∀ a b c. (b → c) → (a → b) → (a → c)
We need something that can compose a binary operation's result against a unary function. Something with the following signature.
??? :: ∀ a b c d. (c → d) → (a → b → c) → a → b → d
The operation that facilitates this has many names, but most people call it the blackbird combinator, as coined by Raymond Smullyan. The implementation of this combinator is a real trip too.
blackbird :: ∀ a b c d. (c → d) → (a → b → c) → a → b → d
blackbird = (<<<) <<< (<<<)
infixr 8 blackbird as ...
Composing two compositions! It looks crazy, but it serves as a point-free bridge from a binary function. This means that scoring negative constraints against an arbitrary state is as simple as one blackbird composition.
excluded :: Int → Int → Int
excluded = population ... and
Using the earlier exclusionary criteria of no gnat and no rat
> excluded 9 8
1
> excluded 9 13
2
we can see that the set represented by 8 has a lower, more ideal score than the set encoded in 13.
Calculating the scores of inclusive constraints is a bit more demanding. We need to perform a chain of operations
xor x (and x y)
Smullyan unfortunately didn't leave us with a bird for this one, which means I got to crank out my own combinator and give it a name to boot. I chose to call it the magpie. Its signature differs from the blackbird by only one variable.
magpie :: ∀ a b c d. (a → c → d) → (a → b → c) → a → b → d
This composes a dyadic function g against a dyadic function f, using the first parameter x as the first argument to f, and the result of (g x y) as the second argument to f. It can be implemented idiomatically as follows.
magpie f g x y = f x (g x y)
I wanted to stretch my tacit muscles, however, and came up with this definition.
magpie :: ∀ a b c d. (a → c → d) → (a → b → c) → a → b → d
magpie = flip (lift2 <<< lift2) const
infixr 8 magpie as .*.
As always, I have the J language to thank for this. I knew that composing the monadic fork procedure lift2 against itself results in a dyadic fork of the form
f (g x y) (h x y)
Substituting the two bitwise functions, I almost had the logic I wanted.
xor (g x y) (and x y)
All I needed was for g to be a function that returns x and drops y. This is the K combinator, which is const in Haskell.
xor (const x y) (and x y)
A flip of the parameters allowed the definition to be entirely point-free.
It was now possible to write an elegant function that checks the score of positive constraints against sets.
included :: Int → Int → Int
included = population ... xor .*. and
Using the earlier criteria of needing a cat and bat in our house
> included 6 5
1
> included 6 7
0
We can see that the set 7 satisfies both constraints.
I love how expressive function definitions become once all the variables are removed. Using these two combinators has allowed me to leverage the advantages of normal composition for binary procedures. I'm looking forward to writing an actual problem solver using these examples as a foundation.
Why a magpie?
The contrived reason: the persistence of x in a chain of compositions resembles an Australian magpie swooping after a cyclist.
The real reason: I like magpies.