Functional Flocks
Eddie Jones;

Flocking Behaviour

Nature's ability to organise itself is not just impressive but often beautiful too. When a group of starlings flock together, they create a mesmerising acrobatic performance. Apparently, we're not the only species that like to dance!

A murmuration of starlings at Gretna, by Walter Baxter
A murmuration of starlings at Gretna, Walter Baxter

Available for reuse under the Creative Commons licence

It's not just biologists that find the sight fascinating. There is a whole field of computer science dedicated to abstracting and replicating these emergent behaviours with a variety of applications.

Boids was one of the first algorithms designed to mimic flocking behaviour. Each boid is governed by three simple forces:

While these forces affect individual boids, they are inherently dependent on the position of neighbouring boids — the context.

Context-aware Pogramming

Monads have been widely adopted in the functional programming community, but their dual, co-monads, are sadly not so popular 😞 Although monads play a broad and important role in category theory, for a programmer they are essentially a convention for adding structure to the output of a function. In particular, they allows us to clearly delineate its result and side-effects:

f :: a -> m b

Of course, this convention is meaningless without laws. For monads, the laws concern the composition of effectful functions and the ability to lift pure functions into this richer context. Monadic functions must behave somewhat like pure functions in that composition is associative and has an identity.

(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a

Similarly, comonads add structure to the input of the function. They tell us what's the context and what's the focus. The focus can be thought of as the data being acted on, e.g. a boid. Whereas the context carries other resources that influence this action but are not influenced by it, e.g. the rest of the flock. Ultimately, the distinction will depend on the application as with monads.

f :: w a -> b

As you might expect, comonads must also satisfy analogous laws. In order to understand the dual notion of composition, we can think of a comonad as a container. Within this container, there are many objects of type a that have some relation to each other such as occupying neighbouring cells of a grid. One of the elements, or positions, is the current focus. However, we could focus on any of them, and they will all have a different view of their context, e.g. a different set of neighbours. Comonads must come equipped with a function for extracting the current focus while disregarding the context. And one for extending a context-aware operation on elements to the entire container.

extend :: (w a -> b) -> w a -> w b
extract :: w a -> a

Under this intuition, the laws roughly translate as:

The Flock Comonad

Our three boid update functions have a natural focus and context: the current boid we're updating, and the rest of the flock. We can think of a flock as a container full of boids. The position of each boid is its coordinate, in say 2-dimensional space. Interestingly though, as all space is relative, no boid is aware of its own location. Instead, boids are only aware of their position relative to one another. The context, therefore, contains vectors from the focus to the other boids. At the origin, i.e. the zero vector (0, 0), the boid in focus may be found.

type Flock a = Map (Int, Int) a

extract :: Flock a -> a
extract flock = flock ! (0, 0)

-- duplicate = extend id
duplicate :: Flock a -> Flock (Flock a)
duplicate flock = mapWithKey (\v _ -> mapKeys (- v) flock) flock

It's in the extension of context-aware operation the real magic happens. For simplicity, let's consider extending the identity function, this will replace each boid with its view of the flock. However, our boids are rather egotistic and see themselves as the centre of the flock. Hence, their view of the flock will be inversely shifted by their own displacement vector so they occupy the origin.

A murmuration of starlings at Gretna, by Walter Baxter

Extending more intresting operations corresponds to applying a context-aware operation to each of the inner flocks of this visualisation. That is:

extend f = fmap f . duplicate

Comonadic Boids

What is the payoff from all this book-keeping? We can now define the forces that act upon boids, in a natural manner - one boid at a time, without worrying about how this affects the flock overall. This separation of concerns highlights the fact that self-organisation is an emergent property. Consider the implementation of the cohesion force for example:

-- NOT: Flock Boid -> Flock Boid
cohesion :: Flock Boid -> Boid
cohesion flock =
  let boid = extract flock
      sum = foldrWithKey (\v _ k -> v + k) 0 flock
      centre = scale (recip (size flock)) sum
    in seek boid centre

Even the type of this function hints that it is a force applied to boids rather than an arbitrary operation on flocks. It is not possible, for example, to add a boid to the flock with this type. Although type-driven development is somewhat of an aesthetic concern, I do believe that a sprinkling of abstraction can lead to more lucid code that is consequently easier to maintain. Ultimately the right representation of data should take into consideration the relevant operations and obscure dangerous or unintended ones; this is often achievable in an elegant manner by appealing to mathematical structures.

Check out the full code here!