Fantas, Eel, and Specification 16: Extend

You’re still here? That means you survived Monad! See? Told you it isn’t that scary. It’s nothing we haven’t already seen. Well, today, we’re going to revisit Chain with one slight difference. As we know, Chain takes an m a to an m b with some help from an a -> m b function. It sequences our ideas. However, what if I told you… we could go backwards? Let’s Extend your horizons.

Don’t get too excited; the disappointment of Contravariant will come flooding back! We’re certainly not saying that we have a magical undo for any Chain. What we are saying, though, is that there are some types for which we can get from m a to m b via m a -> b. Instead of finishing in the context, we start in it!

Two questions probably come to mind:

• How is this useful?
• … See question 1?

Well, we’ll be answering at least one of those questions today! Before that, though, let’s go back to our old format and start with the function:

extend :: Extend w => w a ~> (w a -> b) -> w b

Notice we’re using w here. I kid you not, we use w because it looks like an upside-down m, and m was what we used for Chain. It’s literally there to make the whole thing look back-to-front and upside-down. I’m told that mathematicians call this a joke, so do try to laugh!

As we said, it’s Chain going backwards. It even has the same laws backwards! Say hello, once again, to our old friend associativity:

// RHS: Apply to f THEN chain g
m.chain(f).chain(g)
  === m.chain(x => f(x).chain(g))

// RHS: extend f THEN apply to g
w.extend(f).extend(g)
  === x.extend(w_ => g(w_.extend(f)))

Wait, so, if extend has associativity, and if it looks a bit like a Semigroup… (all together now) where’s the Monoid?!

It’s just like chain, but backwards. Everything is backwards. It’s really the only thing you need to remember!

?thgir ,taen ytterP

So, aside from it being backwards, is there anything useful about Extend? Or, are we just getting a bit tired at this point? Both! Hopefully more the former, though…

Let’s start with an old friend, the Pair (or Writer) type. When we chain, we have total control over the output of our function: we say what we append to the left-hand side, and what we want the right-hand value to be. There was, however, one thing we can’t do: see what was already in the left part!

Pair really gave us a wonderful way to achieve write-only state, but we had no way of reading what we’d written! Wouldn’t it be great if we had a map-like function that let us take a sneaky peek at the left-hand side? Something like this, perhaps:

map :: (m, a) ~> (a  -> b) -> (m, b)

-- Just like map, but we get a sneaky peek!
sneakyPeekMap :: (m, a)
              ~> ((m, a) -> b)
              -> (m, b)

It’s really just like map, but we get some context! Now that we can, whenever we like, take a look at how the left-hand side is doing, we can feed our hungry adventurer:

//- Sum represents "hunger"
const Adventurer = Pair(Sum)

//+ type User = { name :: String, isHungry :: Bool }
const exampleUser = {
  name: 'Tom',
  isHungry: false
}

// You get the idea... WorkPair again!

//+ slayDragon :: User -> Adventurer User
const slayDragon = user =>
  Adventurer(Sum(100), user)

//+ slayDragon :: User -> Adventurer User
const runFromDragon = user =>
  Adventurer(Sum(50), user)

//- Eat IF we're hungry
//+ eat :: User -> Adventurer User
const eat = user =>
  user.isHungry
  ? Adventurer(Sum(-100), {
      ... user,
      isHungry: false
    })

  : Adventurer(Sum(0),   user)

//- How could we know when we're hungry?
//- This function goes the other way...
//+ areWeHungry :: Adventurer User -> User
const areWeHungry =
  ({ _1: { value: hunger }, _2: user }) =>
    hunger > 200
      ? { ... user, isHungry: true }
      : user

// Now, we do a thing, check our hunger,
// and eat if we need to!

// WE ARE SELF-AWARE.
// SKYNET

slayDragon(exampleUser)
.sneakyPeekMap(areWeHungry).chain(eat)
// Pair(Sum(100), not hungry)

.chain(slayDragon)
.sneakyPeekMap(areWeHungry).chain(eat)
// Pair(Sum(200), not hungry)

.chain(runFromDragon)
.sneakyPeekMap(areWeHungry).chain(eat)
// Pair(Sum(150), not hungry)!

Just with this sneakyPeekMap, we can now inspect our character stats and feed that back into our actions. This is so neat: any time you want to update one piece of data depending on another, sneakyPeekMap is exactly what you need. Oh, and by the way, it has a much more common name: extend!

So, can I just think of extend as sneakyPeekMap? I mean, you basically can; that intuition will get you a long way. As an homage to Hardy Jones’ functional pearl, let’s build a Rose Tree:

//- A root and a list of children!
//+ type RoseTree a = (a, [RoseTree a])
const RoseTree = daggy.tagged(
  'RoseTree', ['root', 'forest']
)

Maybe, you looked at that type and a little voice in the back of your mind said Functor. If so, kudos:

RoseTree.prototype.map = function (f) {
  return RoseTree(
    f(this.root), // Transform the root...
    this.forest.map( // and other trees.
      rt => rt.map(f)))
}

No problem; transform the root node, and then recursively map over all the child trees. Bam. Now, imagine if we wanted to colour this tree’s nodes depending on how many children they each have. Sounds like we’d need to take… a sneaky peek!

//+ extend :: RoseTree a
//+        ~> (RoseTree a -> b)
//+        -> RoseTree b
RoseTree.prototype.extend =
  function (f) {
    return RoseTree(
      f(this),
      this.forest.map(rt =>
        rt.extend(f))
    )
  }

// Now, it's super easy to do this!
MyTree.extend(({ root, forest }) =>
  forest.length < 1
    ? { ... root, colour: 'RED' }
    : forest.length < 5
      ? { ... root, colour: 'ORANGE' }
      : { ... root, colour: 'GREEN' })

With our new-found superpower, each node gets to pretend to be the one in charge, and can watch over their own forests. The trees in those forests then do the same, and so on, until we map-with-a-sneaky-peek the entire forest! Again, I linked to Hardy’s article above, which contains a much deeper dive into trees specifically; combining RoseTree with Hardy’s ideas is enough to make your own billion-dollar React clone!

Let’s cast our minds waaay back to the Setoid post, when we looked at List. List, it turns out, is a Functor:

//- Usually, if you can write something for
//- Array, you can write it for List!
List.prototype.map = function (f) {
  return this.cata({
    // Do nothing, we're done!
    Nil: () => Nil,

    // Transform head, recurse on tail
    Cons: (head, tail) =>
      Cons(f(head), tail.map(f))
  })
}

// e.g. Cons(1, Cons(2, Nil))
//      .map(x => x + 1)
// === Cons(2, Cons(3, Nil))

Now, for this convoluted example, let’s imagine we have some weather data for the last few days:

const arrayToList = xs => {
  if (!xs.length) return Nil

  const [ head, ... tail ] = this
  return Cons(head, arrayToList(tail))
}

List.prototype.toArray = function () {
  return this.cata({
    Cons: (head, tail) => ([
      head, ... tail.toArray()
    ]),

    Nil: () => []
  })
}

// Starting from today... (in celsius!)
const temperatures = arrayToList(
  [23, 19, 19, 18, 18, 20, 24])

What we want to do is map over this list to determine whether the temperature has been warmer or cooler than the day before! To do that, we’ll probably need to do something sneakily… any ideas?

//+ List a ~> (List a -> b) -> List b
List.prototype.extend = function (f) {
  return this.cata({
    // Extend the list, repeat on tail.
    Cons: (head, tail) => Cons(
      f(this), tail.extend(f)
    ),

    Nil: () => Nil // We're done!
  })
}

// [YAY, YAY, YAY, YAY, BOO, BOO, ???]
temperatures
.extend(({ head, tail }) =>
  tail.length == 0 ? '???'
                   : head < tail.head
                     ? 'BOO' : 'YAY')
.toArray()

We only used the head of the tail this time, but we could use the whole thing if we wanted! We have the entire thing available to peek sneakily.

For example, we could use this technique for lap times to record whether they’re faster or slower than the average so far! Have a go!

As we said, we can mimic the same behaviour for Array to save us all the to-and-fro with List:

Array.prototype.extend = function (f) {
  if (this.length === 0) return []

  const [ _, ... tail ] = this
  return [ f(this), ... tail.extend(f) ]
}

// Now, we can use array-destructuring :)
;[23, 19, 19, 18, 18, 20, 24].extend(
  ([head, ... tail]) =>
    tail.length == 0
    ? '???'
    : head < tail[0]
      ? 'BOO' : 'YAY')

I brought these examples up for a reason, Fantasists. Often, extend isn’t just f => W.of(f(this)) for some W type; that’s what of is for! extend is about being able to map while being aware of the surrounding construct.

Think of it like this: when we used Chain, we had total write access to the output constructor and values. We could turn Just into Nothing, we could fail a Task, and we could even change the length of an Array. Truly, we were powerful.

With Extend, we get full read access to the input constructor and values. It’s the opposite idea.

Whereas Chain lets us inform the future of the computation, Extend lets us be informed by the past. This is the kind of sentence that ends up on a mug, you know!

-- chain: `map` with write-access to output
-- extend: `map` with read-access to input

map    :: f a -> (  a ->   b) -> f b
chain  :: m a -> (  a -> m b) -> m b
extend :: w a -> (w a ->   b) -> w b

There are lots of cool examples of Extend, but they are often overlooked and generally considered a more “advanced” topic. After all, with Monad, we’re free to build anything; why bother continuing? Well, I hope this gives you an idea of how they work and where you can find them! After all, these are all just design patterns: just use them when they’re appropriate!

So, Semigroup is to Monoid as Chain is to Monad as Extend is to…? We’ll find out next time! Before we go, though, here’s a very tricky challenge to keep you busy:

With Writer, we needed a Semigroup on the left to make a Chain instance, but we didn’t for Extend. Reader has an Extend instance; can you think of how we might write that?

Until then, take a look through this article’s code, and take care!

♥