Fantas, Eel, and Specification 11: Foldable

Welcome back, Fantasists! This week has been hectic, so I haven’t caught up the companion repository as I’d hoped to. However, I should have some time to devote to it this week, so watch this space! Anyway, why don’t we have some down time before we get onto the really grizzly parts of the spec? Let’s take a look at Foldable.

Wouldn’t you know it, this one comes with a new function to add to our repertoire, and it’s one that might look a bit familiar to some readers:

reduce :: Foldable f =>
  f a ~> ((b, a) -> b, b) -> b

Do we already know of any Foldable types? I’ll suggest one:

Array.prototype.reduce ::
  [a] ~> ((b, a) -> b, b) -> b

Straight away, Array is a valid Foldable type. In fact, Fantasy Land’s Foldable was deliberately modelled after Array. Why? Because this structure generalises Array.reduce. Bam. With that in mind, let’s look at its law:

const toArray xs => xs.reduce(
  (acc, x) => acc.concat([x]), []
)

u.reduce(f) === toArray(u).reduce(f)

This is a really weird law because it’s not very… rigorous. You’re unlikely to write a Foldable and get this wrong, because the reduce in toArray probably works in the exact same way as the reduce outside. In fact, it’s probably best to look at this more as a behaviour than a law. You still have to obey it, though!

There’s a lot of space for interpretation here, which isn’t necessarily a good thing. On the other hand, it makes it really easy to give some examples!

// reduce :: Maybe a
//        ~> ((b, a) -> b, b) -> b
Maybe.prototype.reduce =
  function (f, acc) {
    return this.cata({
      // Call the function...
      Just: x => f(acc, x),

      // ... or don't!
      Nothing: () => acc
    })
  }

// reduce :: Either e a
//        ~> ((b, a) -> b, b) -> b
Either.prototype.reduce =
  function (f, acc) {
    return this.cata({
      // Call the function...
      Right: x => f(acc, x),

      // Or don't!
      Left: _ => acc
    })
  }

Because Nothing and Left represent failure, we just return the accumulator. Otherwise, we can use our f function once. These examples really just highlight that you don’t need a structure with (potentially) multiple values in order to write a Foldable instance. However, it’s definitely most useful when that’s the case. For example, let’s build a binary tree:

// BTree a
const BTree = daggy.taggedSum('BTree', {
  // Recursion!
  // Node (BTree a) a (BTree a)
  Node: ['left', 'x', 'right'],

  // Leaf
  Leaf: []
})

So, Nodes represent “branch points” of the tree with values, and Leafs represent the ends of branches. Because left and right are also BTree instances, this gives us a recursive tree construction:

const { Node, Leaf } = BTree

//      3
//     / \
//    1   5
//   /|   |\
//  X 2   4 X
//   /|   |\
//  X X   X X
const MyTree =
  Node(
    Node(
      Leaf,
      1,
      Node(
        Leaf,
        2,
        Leaf ) ),
    3,
    Node(
      Node(
        Leaf,
        4,
        Leaf ),
      5,
      Leaf ) )

I’m too ashamed to say how long I spent drawing that tree. Now, Array.reduce combines all our values together (if your Semigroup or Monoid klaxon just sounded, then I’m super proud ♥) from left to right, so that’s probably what we want to imitate with this tree. How do we do that? With magical recursion:

BTree.prototype.reduce =
  function (f, acc) {
    return this.cata({
      Node: (l, x, r) => {
        // Reduce the tree on the left...
        const left = l.reduce(f, acc)

        // Plus the middle element...
        const leftAndMiddle = f(left, x)

        // And then the right tree...
        return r.reduce(f, leftAndMiddle)
      },

      // Return what we started with!
      Leaf: () => acc
    })
  }

MyTree.reduce((x, y) => x + y, 0) // 15

Woo! We reduce the tree starting from the left-most element and work across. Whenever we hit a Node, we just recurse and do the same thing!

We saw at the end of the last snippet that we can find the sum of all the elements, and we could just as easily write min, max, product, or whatever. In fact, you can do anything with Array.reduce and generalise it to all Foldable types immediately! Whether we then have a Maybe, an Array, or even a BTree, our functions will Just Work™!

Product? Min? Max? This really does sound like Monoid again, doesn’t it? Well, there are no coincidences in Fantasy Land. Back in the Monoid post, we wrote the fold function:

// A friendly neighbourhood monoid fold.
// fold :: Monoid m => (a -> m) -> [a] -> m
const fold = M => xs => xs.reduce(
  (acc, x) => acc.concat(M(x)),
  M.empty())

With our new-found Foldable knowledge, we now know that this type signature is too specific. Let’s fix it:

fold :: (Foldable f, Monoid m)
     => (a -> m) -> f a -> m

Yes, this function will in fact work with any Foldable structure and any Monoid - you’ll never need to write reduce again! Get comfortable with using Monoid for reductions; it’s definitely a good way to make your code more declarative, and hence more readable. I know you’re probably sick of hearing about monoids, but they really are everywhere!

It turns out that many of your favourite Functor types have sensible implementations for reduce. However, there are exceptions:

We can’t reduce the Task type because we don’t know what the inner values are going to be! It’s the same with Function: we don’t know what the return value is going to be until we give it an argument. Remember: functors’ inner values aren’t always reachable.

Incidentally, if a Functor does have an always-reachable inner value, we can call it a Copointed functor. Remember how Applicative’s of is a function of Pointed functors? Think about the relationship between Pointed and Copointed. There are no coincidences in Fantasy Land!

This week, why not make a Foldable Rose Tree? Or Set? There are plenty of opportunities to practise here. Before we go, some of you may have noticed that you can reduce most things by just returning the initial value given to you:

MyType.prototype.reduce = (f, acc) => acc

It satisfies the “law”, right? This is what I mean: this law is not a good’un, and leaves too much room for interpretation. Still, there’s no point in moaning: we’ll see next time that Traversable (my all-time favourite part of the Fantasy Land spec!) saves the day! From now on, Fantasists, the excitement is non-stop.

♥