Nature’s abil­ity to or­gan­ise it­self is not just im­press­ive but of­ten beau­ti­ful too. When a group of starlings flock to­geth­er, they cre­ate a mes­mer­ising ac­ro­batic per­form­ance. Ap­par­ently, we’re not the only spe­cies that like to dance!

It’s not just bio­lo­gists that find the sight fas­cin­at­ing. There is a whole field of com­puter sci­ence ded­ic­ated to ab­stract­ing and rep­lic­at­ing these emer­gent be­ha­viours with a vari­ety of ap­plic­a­tions.

Boids was one of the first al­gorithms de­signed to mimic flock­ing be­ha­viour. Each boid is gov­erned by three simple forces:

• Sep­ar­a­tion: Avoid other boids as to not cause a col­li­sion.
• Co­he­sion: Stick to­geth­er, i.e. move to­wards the av­er­age po­s­i­tion.
• Align­ment: Fol­low the dir­ec­tion of the crowd.

While these forces af­fect in­di­vidual boids, they are in­her­ently de­pend­ent on the po­s­i­tion of neigh­bour­ing boids — the con­text. If we are to im­ple­ment a simple boid sim­u­la­tion in a char­ac­ter­ist­ic­ally func­tional (read over­-en­gin­eered) style, it is nat­ural to ap­ply the frame­work of con­tex­t-aware pro­gram­ming.

Con­tex­t-aware Po­gram­ming

Mon­ads have been widely ad­op­ted in the func­tional pro­gram­ming com­munity, but their du­al, co-­mon­ads, are sadly not so pop­u­lar. Al­though mon­ads play a broad and im­port­ant role in cat­egory the­ory, for a pro­gram­mer they are es­sen­tially a con­ven­tion for adding struc­ture to the out­put of a func­tion. In par­tic­u­lar, they al­lows us to clearly de­lin­eate its “true” res­ult b from any side-ef­fects m:

ef­fec­tul­Func­tion :: Monad m => a -> m b

Of course, this con­ven­tion is mean­ing­less without some laws. For mon­ads, the laws con­cern the com­pos­i­tion of ef­fect­ful func­tions and the abil­ity to lift pure func­tions into this richer con­text. Ef­fect­ful func­tions must be­have some­what like pure func­tions in that com­pos­i­tion is as­so­ci­at­ive and has an iden­tity.

class Monad m where
  re­turn :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b

Sim­il­arly, co­mon­ads add struc­ture to the in­put fo­cus­ing on some sub­sec­tion of the in­put a dis­tin­guished from con­tex­tual in­form­a­tion w. In our case, the fo­cus is an in­di­vidual boid, whereas the con­text con­tains the re­l­at­ive po­s­i­tion of the rest of the flock, i.e. re­sources that in­flu­ence but are not in­flu­enced by the up­dat­ing of an in­di­vidual boid. Ul­ti­mately, the dis­tinc­tion will de­pend on the ap­plic­a­tion as with mon­ads.

coef­fect­ful­Func­tion :: Co­monad w => w a -> b

As you might ex­pect, co­mon­ads must also sat­isfy a set of ana­log­ous laws. In or­der to un­der­stand the dual no­tion of com­pos­i­tion, we can think of a co­monad as a sort of con­tainer. Within this con­tain­er, there are many po­s­i­tions each hold­ing an ob­jects of type a that have some re­la­tion to each other such as oc­cupy­ing neigh­bour­ing cells of a grid. One of the po­s­i­tions is the cur­rent fo­cus. However, we could fo­cus on any of them, and they will all have a dif­fer­ent view of their con­text, e.g. a dif­fer­ent set of neigh­bour­ing cells. Co­mon­ads must come equipped with a func­tion for ex­tract­ing the cur­rent fo­cus while dis­reg­ard­ing the con­text. And one for ex­tend­ing a con­tex­t-aware op­er­a­tion to the ob­ject in each po­s­i­tion in the con­tainer with their loc­al­ised view of the con­text.

class Co­monad w where
  ex­tract :: w a -> w
  ex­tend :: (w a -> b) -> w a -> w b

Un­der this in­tu­ition, the laws gov­ern­ing co­monad in­stances can be roughly trans­lated as:

• Ex­tract­ing the fo­cus from every po­s­i­tion in a con­tainer must equate to the ori­ginal con­tainer

    ex­tend ex­tract = id

• Ex­tend­ing a con­tex­t-aware op­er­a­tion to the whole con­tainer and then ex­tract­ing the fo­cus must be the same as ap­ply­ing the con­tex­t-aware op­er­a­tion to the ori­ginal con­tainer with its ori­ginal fo­cus. In other words, ex­tend does not change which ele­ment is in fo­cus.

    ex­tract . ex­tend f = f

• And fi­nally, the com­pos­i­tion of ex­ten­ded con­tex­t-aware op­er­a­tions should be as­so­ci­at­ive.

    ex­tend f . ex­tend g = ex­tend (f . ex­tend g)

The Flock Co­monad

Our three boid up­date func­tions have a nat­ural fo­cus and con­text: the cur­rent boid we’re up­dat­ing, and the rest of the flock. We can think of a flock as a con­tainer full of boids where the po­s­i­tion of each boid is its co­ordin­ate, in say 2-di­men­sional space. In­ter­est­ingly though, to per­form these op­er­a­tions, we do not need ex­act po­s­i­tions just the re­l­at­ive po­s­i­tions of other boids. The boid in fo­cus is thus po­si­tioned at the ori­gin, i.e. the zero vec­tor (0, 0), and the con­text con­tains vec­tors to the other boids.

type Flock a = Map (Float, Float) a

ex­tract :: Flock a -> a
ex­tract flock = flock ! (0, 0)

ex­tend :: (Flock a -> b) -> Flock a -> Flock b
ex­tend f flock =
  map­WithKey (\­pos _ -> f $ map­Keys (- pos) flock) flock 

It’s in the ex­ten­sion of con­tex­t-aware op­er­a­tion the real ma­gic hap­pens. For sim­pli­city, let’s con­sider ex­tend­ing the iden­tity func­tion, this will re­place each boid with its view of the flock. However, as our boids are rather egot­istic and see them­selves as the centre of the flock, their view of the flock will be in­versely shif­ted by their own po­s­i­tion so that they oc­cupy the ori­gin.

In the dia­gram on the left, the fo­cus of a flock is in­dic­ated by a red circle. After the con­tex­t-ware up­date, each po­s­i­tion in the flock is oc­cu­pied by a copy of the ori­ginal flock ex­cept where the fo­cus has shif­ted to the po­s­i­tion in ques­tion.

Co­mon­adic Boids

What is the pay­off from all this book-­keep­ing? We can now define the forces that act upon boids nat­ur­ally - one boid at a time, without wor­ry­ing about how this af­fects the over­all flock. This sep­ar­a­tion of con­cerns high­lights the fact that self-or­gan­isa­tion is an emer­gent prop­erty. Con­sider the im­ple­ment­a­tion of the co­he­sion force for ex­ample:

-- N.B. the re­turn type is not Flock Boid
co­he­sion :: Flock Boid -> Boid
co­he­sion flock =
  let boid :: Boid -- Boid in fo­cus
      boid = ex­tract flock
      
      pos :: (Float, Float) -- Av­er­age po­s­i­tion
      pos = sum (Map.keys flock / size flock)
    in boid `steer­To­wards` pos

ap­ply­Co­he­sion :: Flock Boid -> Flock Boid
ap­ply­Co­hes­tion = ex­tend co­he­sion

The type of this func­tion hints that it is a force ap­plied to boids rather than an ar­bit­rary op­er­a­tion on flocks. It is not pos­sible, for ex­ample, to in­sert a new boid into the flock with a func­tion of this type. Al­though type-driven de­vel­op­ment is some­what of an aes­thetic con­cern, I do be­lieve that a sprink­ling of ab­strac­tion can lead to more lu­cid code that is con­sequently easier to main­tain. Ul­ti­mately the right rep­res­ent­a­tion of data should take into con­sid­er­a­tion the rel­ev­ant op­er­a­tions and ob­scure dan­ger­ous or un­in­ten­ded ones; this is of­ten achiev­able in an el­eg­ant man­ner by ap­peal­ing to math­em­at­ical struc­tures.