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"

//+ 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 =>

//+ slayDragon :: User -> Adventurer User
const runFromDragon = user =>

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

//- 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
})
}

// 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
}

List.prototype.toArray = function () {
return this.cata({
]),

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.
f(this), tail.extend(f)
),

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

// [YAY, YAY, YAY, YAY, BOO, BOO, ???]
temperatures
tail.length == 0 ? '???'
? '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(
tail.length == 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
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?