Comonads, Monoids and Trees

31 Dec 2015

Table of Contents

  1. Introduction
  2. Tree Solution
  3. Functor
  4. Comonad
  5. Foldable
  6. Monoid
  7. More Refactoring
  8. Conclusion

Introduction

@lucasfeliciano asked a question on the ramda gitter recently:

I’m struggling trying to do something here: I have a tri dimensional array and I want to change a atribute of a object that is inside the deepest array. But by doing that I need to change the reference to their parents To respect this scenario

1
2
3
4
5
6
7
8
9
10
11
12
initial state
A
|\
B C
| |\
D E F
D changes, all parents are replaced
A*
|\
B* C
|  |\
D* E F

What is the best approach to do that using ramda?

The motivation for this problem is explained:

…if the reference of B change, A needs to change as well

1
2
3
we know something has changed because A changed
we know something in B changed because b changed
we know everything below C hasnt changed because C hasnt changed

see? That is a react concept How it compares the tree state to calculate what need to be re rendered

It is like a difference algorithm, something that might be used in react, virtual-dom or (more generally) any tree library.

Tree Solution

After playing around with a couple of solutions, I think there is an elegant solution using some of the less familiar concepts of comonads and monoids.

The first thing that will make this whole solution much easier is to use a more descriptive data type. A 3-d array is not ideal for this problem. I think the visual representation that @lucasfeliciano gave is a good model. So we should start with a tree. We will keep it simple and have a binary tree. Since we want to know what nodes are affected by their children, we will hold on to some state in each node. We call this state, the

1
annotation
. The leaves hold the values of the tree and an annotation. The branches hold more trees and an annotation. The motivation for adding an annotation to each node is: when a node is changed, its annotation can reflect this change without affecting the actual value of the node.

We can create some constructors that encapsulate this logic.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Leaf : val -> ann -> Tree val ann
function Leaf(val, ann) {
  return {
    ann: ann,
    val: val,
    toString: () => `Leaf(${val}, ${ann})`,
  };
}
// Branch : Tree val ann -> Tree val ann -> ann -> Tree val ann
function Branch(left, right, ann) {
  return {
    ann: ann,
    left: left,
    right: right,
    toString: () => `Branch(${left}, ${right}, ${ann})`,
  };
}

Note that we are just returning a plain old javascript object (POJO). There’s no need for

1
new
or a
1
class
or anything like that.

Functor

Given that we have this

1
Tree val ann
type with at least one type variable, we can make a
1
Functor
from
1
Tree val
. We choose to make the
1
Functor
over the
1
ann
variable, since this is the one we care about in the solution to the problem.

The intuition for wanting a

1
Functor
in the solution comes from recognizing that we are probably going to want to apply some function uniformly across all nodes in the tree. For instance, we might want to adjust every annotation in the tree all at once. Or if we have a subtree, we might want to adjust all those nodes at once. Recognizing that we can apply a function to all the values in the tree uniformly is the main take away here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Leaf : val -> ann -> Tree val ann
function Leaf(val, ann) {
  return {
    ann: ann,
    val: val,
    toString: () => `Leaf(${val}, ${ann})`,
    map: f => Leaf(val, f(ann)),
  };
}
// Branch : Tree val ann -> Tree val ann -> ann -> Tree val ann
function Branch(left, right, ann) {
  return {
    ann: ann,
    left: left,
    right: right,
    toString: () => `Branch(${left}, ${right}, ${ann})`,
    map: f => Branch(left.map(f), right.map(f), f(ann)),
  };
}

Let us see this in action:

1
2
3
4
5
6
7
8
9
10
11
12
13
> const l1 = Leaf(1, 'wat');
> const l2 = Leaf(2, 'yup');
> const b1 = Branch(l1, l2, 'nope');
> l1.toString();
'Leaf(1, wat)'
> l2.toString();
'Leaf(2, yup)'
> b1.toString();
'Branch(Leaf(1, wat), Leaf(2, yup), nope)'
> b1.map(str => str.length).toString();
'Branch(Leaf(1, 3), Leaf(2, 3), 4)'
> b1.map(_ => false).toString();
'Branch(Leaf(1, false), Leaf(2, false), false)'

Notice that we can only change the annotation. The value stays the same throughout the tree.

This can be used to “reset” the tree annotations. For instance, after we have found the nodes that need to change, we can map everything to

1
false
so any new changes that are made can be tracked.

Comonad

We need a way to propagate annotations through the branches of a tree.

Say we make our annotation a boolean where

1
false
implies unchanged, and
1
true
implies changed. In the real world, we would want to use a more descriptive data type than boolean, but for the sake of brevity, we stick with boolean. When a child has been annotated
1
true
, the parent should also be annotated
1
true
. Or thinking about it another way, to determine a parent’s annotation, we must know the annotation of the children.

If we modify some leaf or branch in a tree and want to propagate the change upwards, what can we do? We could write some specific algorithm that works only for booleans. While this would solve the problem, it would have to be rewritten somehow if we change the type of annotation.

A slightly more interesting solution is to look towards comonads. In this solution we can stop before we get the full power of a comonad. We only need the power that

1
extend
provides. The intuition for wanting a comonadic interface comes from realizing that in order to update the annotations of a tree, the rest of the values in the tree are needed. Put another way, the value of a single annotation depends on the value of the annotations around it. Put yet another way, the context in which an annotation is in determines the value of that annotation.

We can implement

1
extend
fairly simply:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Leaf : val -> ann -> Tree val ann
function Leaf(val, ann) {
  return {
    ann: ann,
    val: val,
    toString: () => `Leaf(${val}, ${ann})`,
    map: f => Leaf(val, f(ann)),
    extend: f => Leaf(val, f(Leaf(val, ann))),
  };
}
// Branch : Tree val ann -> Tree val ann -> ann -> Tree val ann
function Branch(left, right, ann) {
  return {
    ann: ann,
    left: left,
    right: right,
    toString: () => `Branch(${left}, ${right}, ${ann})`,
    map: f => Branch(left.map(f), right.map(f), f(ann)),
    extend: f =>
      Branch(left.extend(f), right.extend(f), f(Branch(left, right, ann))),
  };
}

Notice that we always pass an entire

1
Tree val ann
to the given function. It takes the
1
Tree val ann
and produces a single value. I am willing to bet that it is not immediately clear how this is helpful. We will come back to that later, so bear with me for a bit.

What if we had some function that took a

1
Tree
and returned a boolean that said whether or not any of the nodes had been updated? If we had this function, we could pass it to
1
extend
, and it would change all the annotations to reflect that.

So let us think about that function.

How do you know if a

1
Leaf
is changed? The
1
ann
tells you directly.

How do you know if a

1
Branch
is changed? Either the
1
ann
or the
1
left
side has been changed or the
1
right
side has been changed. If either side is a
1
Leaf
, we know directly. If either side is a
1
Branch
, we have to continue recursing.

We can implement this function fairly simply as well.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Leaf : val -> ann -> Tree val ann
function Leaf(val, ann) {
  return {
    ann: ann,
    val: val,
    toString: () => `Leaf(${val}, ${ann})`,
    map: f => Leaf(val, f(ann)),
    extend: f => Leaf(val, f(Leaf(val, ann))),
    changed: ann,
  };
}
// Branch : Tree val ann -> Tree val ann -> ann -> Tree val ann
function Branch(left, right, ann) {
  return {
    ann: ann,
    left: left,
    right: right,
    toString: () => `Branch(${left}, ${right}, ${ann})`,
    map: f => Branch(left.map(f), right.map(f), f(ann)),
    extend: f =>
      Branch(left.extend(f), right.extend(f), f(Branch(left, right, ann))),
    changed: ann || left.changed || right.changed,
  };
}

Before we see if this works, we should recognize there is a big problem with

1
changed
. The types of
1
Leaf
and
1
Branch
are said to take any annotation, but here we are assuming that the given annotation is a boolean. While it is fine to have a boolean specific version, it breaks the
1
Functor
and
1
Extend
implementations we just wrote if we force the annotation to be a boolean. A
1
Functor
cannot work over a specific data type, it must work with every data type–similarly for
1
Extend
.

Foldable

All is not lost though. Look long enough at

1
changed
and you might recognize that it is taking our tree structure and breaking it down to a single value. In this case, we are breaking the tree down to a single boolean value. This idea has an abstraction:
1
Foldable
. So we should be able to implement
1
reduce
and then rewrite
1
changed
in terms of
1
reduce
.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Leaf : val -> ann -> Tree val ann
function Leaf(val, ann) {
  return {
    ann: ann,
    val: val,
    toString: () => `Leaf(${val}, ${ann})`,
    map: f => Leaf(val, f(ann)),
    extend: f => Leaf(val, f(Leaf(val, ann))),
    reduce: (f, acc) => f(acc, ann),
  };
}
// Branch : Tree val ann -> Tree val ann -> ann -> Tree val ann
function Branch(left, right, ann) {
  return {
    ann: ann,
    left: left,
    right: right,
    toString: () => `Branch(${left}, ${right}, ${ann})`,
    map: f => Branch(left.map(f), right.map(f), f(ann)),
    extend: f =>
      Branch(left.extend(f), right.extend(f), f(Branch(left, right, ann))),
    reduce: (f, acc) => right.reduce(f, left.reduce(f, f(acc, ann))),
  };
}
// changed : Tree val Bool -> Bool
const changed = tree => tree.reduce((acc, x) => acc || x, false);

Notice that we have made

1
changed
a plain function rather than being a method on the
1
Tree
. This makes things a bit easier to work with.

Now, let us see if it works:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> const l1 = Leaf(1, false);
> const l2 = Leaf(2, false);
> const l3 = Leaf(3, true);
> const b1 = Branch(l1, l2, false);
> const b2 = Branch(b1, l3, false);
> changed(l1);
false
> changed(l2);
false
> changed(l3);
true
> changed(b1);
false
> changed(b2);
true

Seems like it works.

1
l3
is changed, and it affects only
1
l3
and its ancestors (
1
b2
in this case).

Now we can use this in our implementation.

Remember the implementation of

1
extend
, it takes the entire tree and passes it to the given function. The given function takes this tree and returns a single value. This is exactly what
1
reduce
does. So we can pass our
1
changed
function to
1
extend
and it will annotate the tree with its own changes.

1
2
3
4
5
6
7
8
9
> const l1 = Leaf(1, false);
> const l2 = Leaf(2, false);
> const l3 = Leaf(3, true);
> const b1 = Branch(l1, l2, false);
> const b2 = Branch(b1, l3, false);
> b2.toString();
'Branch(Branch(Leaf(1, false), Leaf(2, false), false), Leaf(3, true), false)'
> b2.extend(changed).toString();
'Branch(Branch(Leaf(1, false), Leaf(2, false), false), Leaf(3, true), true)'

Excellent! We have arrived at a solution!

Monoid

Now that we have an actual solution, we should think about ways to improve it.

There is one thing that stands out immediately to me. The changed function is implemented directly in terms of

1
reduce
. Lately, I have been noticing that whenever there is a
1
reduce
around, it is indicative of an abstraction somewhere. Many people call this a code smell.

What is the underlying abstraction we are missing? We are reducing with

1
||
and the initial value of
1
false
. This binary function and value form a
1
Monoid
.

How would we actually abstract it away? Make a

1
Monoid
implementation for booleans. But since we do not want to monkey patch a built-in, we will create a new data type specifically for this.

1
2
3
4
5
6
7
8
// Any : Bool -> Any
function Any(bool) {
  return {
    bool: bool,
    concat: a => Any(bool || a.bool),
  };
}
Any.empty = () => Any(false);

So if we had all of the annotations in the tree as

1
Any
s, we could reduce over the tree using the
1
Monoid
interface. This function has a name,
1
fold
in Haskell.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Leaf : val -> ann -> Tree val ann
function Leaf(val, ann) {
  return {
    ann: ann,
    val: val,
    toString: () => `Leaf(${val}, ${ann})`,
    map: f => Leaf(val, f(ann)),
    extend: f => Leaf(val, f(Leaf(val, ann))),
    reduce: (f, acc) => f(acc, ann),
  };
}
// Branch : Tree val ann -> Tree val ann -> ann -> Tree val ann
function Branch(left, right, ann) {
  return {
    ann: ann,
    left: left,
    right: right,
    toString: () => `Branch(${left}, ${right}, ${ann})`,
    map: f => Branch(left.map(f), right.map(f), f(ann)),
    extend: f =>
      Branch(left.extend(f), right.extend(f), f(Branch(left, right, ann))),
    reduce: (f, acc) => right.reduce(f, left.reduce(f, f(acc, ann))),
  };
}
// fold : (Monoid m, Foldable f) => m -> f m -> m
const fold = (Monoid, Foldable) =>
  Foldable.reduce((acc, x) => acc.concat(x), Monoid.empty())

Note that since there is no type system for js, we have to explicitly state which

1
Monoid
we want to use. Whereas a halfway decent type system would be able to infer this from the
1
Foldable
argument or the return type.

We can put these together to make our

1
changed
function clearer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// Leaf : val -> ann -> Tree val ann
function Leaf(val, ann) {
  return {
    ann: ann,
    val: val,
    toString: () => `Leaf(${val}, ${ann})`,
    map: f => Leaf(val, f(ann)),
    extend: f => Leaf(val, f(Leaf(val, ann))),
    reduce: (f, acc) => f(acc, ann),
  };
}
// Branch : Tree val ann -> Tree val ann -> ann -> Tree val ann
function Branch(left, right, ann) {
  return {
    ann: ann,
    left: left,
    right: right,
    toString: () => `Branch(${left}, ${right}, ${ann})`,
    map: f => Branch(left.map(f), right.map(f), f(ann)),
    extend: f =>
      Branch(left.extend(f), right.extend(f), f(Branch(left, right, ann))),
    reduce: (f, acc) => right.reduce(f, left.reduce(f, f(acc, ann))),
  };
}
// Any : Bool -> Any
function Any(bool) {
  return {
    bool: bool,
    concat: a => Any(bool || a.bool),
  };
}
Any.empty = () => Any(false);
// fold : (Monoid m, Foldable f) => m -> f m -> m
const fold = (Monoid, Foldable) =>
  Foldable.reduce((acc, x) => acc.concat(x), Monoid.empty())
// changed : Tree val Bool -> Bool
const changed = tree => fold(Any, tree.map(Any)).bool;

And we can see it in action:

1
2
3
4
5
6
7
8
9
> const l1 = Leaf(1, false);
> const l2 = Leaf(2, false);
> const l3 = Leaf(3, true);
> const b1 = Branch(l1, l2, false);
> const b2 = Branch(b1, l3, false);
> b2.toString();
'Branch(Branch(Leaf(1, false), Leaf(2, false), false), Leaf(3, true), false)'
> b2.extend(changed).toString();
'Branch(Branch(Leaf(1, false), Leaf(2, false), false), Leaf(3, true), true)'

Great! The refactoring worked!

More Refactoring

Notice now however, we have gotten less efficient. First we

1
map
over the entire tree, then we
1
fold
it. We are iterating the tree twice, when before we iterated it once.

We can make this have the same efficiency as before if we look for more help from Haskell. There is a function

1
foldMap
that does exactly these two iterations in one go.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Leaf : val -> ann -> Tree val ann
function Leaf(val, ann) {
  return {
    ann: ann,
    val: val,
    toString: () => `Leaf(${val}, ${ann})`,
    map: f => Leaf(val, f(ann)),
    extend: f => Leaf(val, f(Leaf(val, ann))),
    reduce: (f, acc) => f(acc, ann),
  };
}
// Branch : Tree val ann -> Tree val ann -> ann -> Tree val ann
function Branch(left, right, ann) {
  return {
    ann: ann,
    left: left,
    right: right,
    toString: () => `Branch(${left}, ${right}, ${ann})`,
    map: f => Branch(left.map(f), right.map(f), f(ann)),
    extend: f =>
      Branch(left.extend(f), right.extend(f), f(Branch(left, right, ann))),
    reduce: (f, acc) => right.reduce(f, left.reduce(f, f(acc, ann))),
  };
}
// Any : Bool -> Any
function Any(bool) {
  return {
    bool: bool,
    concat: a => Any(bool || a.bool),
  };
}
Any.empty = () => Any(false);
// fold : (Monoid m, Foldable f) => m -> f m -> m
const fold = (Monoid, Foldable) =>
  Foldable.reduce((acc, x) => acc.concat(x), Monoid.empty())
// foldMap : (Monoid m, Foldable f) => m -> (a -> m) -> f a -> m
const foldMap = (Monoid, f, Foldable) =>
  Foldable.reduce((acc, x) => acc.concat(f(x)), Monoid.empty())
// changed : Tree val Bool -> Bool
const changed = tree => foldMap(Any, Any, tree).bool;

The fact that we pass

1
Any
twice is a coincidence that we are using the
1
Any
function as the
1
Monoid
and also to create our value. We are not forced to pass the exact same value to both parameters.

1
fold
and
1
foldMap
look almost identical. We can actually write
1
fold
in terms of
1
foldMap
by passing the identity function to
1
foldMap
.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Leaf : val -> ann -> Tree val ann
function Leaf(val, ann) {
  return {
    ann: ann,
    val: val,
    toString: () => `Leaf(${val}, ${ann})`,
    map: f => Leaf(val, f(ann)),
    extend: f => Leaf(val, f(Leaf(val, ann))),
    reduce: (f, acc) => f(acc, ann),
  };
}
// Branch : Tree val ann -> Tree val ann -> ann -> Tree val ann
function Branch(left, right, ann) {
  return {
    ann: ann,
    left: left,
    right: right,
    toString: () => `Branch(${left}, ${right}, ${ann})`,
    map: f => Branch(left.map(f), right.map(f), f(ann)),
    extend: f =>
      Branch(left.extend(f), right.extend(f), f(Branch(left, right, ann))),
    reduce: (f, acc) => right.reduce(f, left.reduce(f, f(acc, ann))),
  };
}
// Any : Bool -> Any
function Any(bool) {
  return {
    bool: bool,
    concat: a => Any(bool || a.bool),
  };
}
Any.empty = () => Any(false);
// foldMap : (Monoid m, Foldable f) => m -> (a -> m) -> f a -> m
const foldMap = (Monoid, f, Foldable) =>
  Foldable.reduce((acc, x) => acc.concat(f(x)), Monoid.empty())
// fold : (Monoid m, Foldable f) => m -> f m -> m
const fold = (Monoid, Foldable) => foldMap(Monoid, x => x, Foldable));
// changed : Tree val Bool -> Bool
const changed = tree => foldMap(Any, Any, tree).bool;

Once again, we can see it in action:

1
2
3
4
5
6
7
8
9
> const l1 = Leaf(1, false);
> const l2 = Leaf(2, false);
> const l3 = Leaf(3, true);
> const b1 = Branch(l1, l2, false);
> const b2 = Branch(b1, l3, false);
> b2.toString();
'Branch(Branch(Leaf(1, false), Leaf(2, false), false), Leaf(3, true), false)'
> b2.extend(changed).toString();
'Branch(Branch(Leaf(1, false), Leaf(2, false), false), Leaf(3, true), true)'

And once again, we see that the refactoring worked!

Conclusion

Was it worth it to implement the

1
Any
data type? From the perspective of having to pass around what should be implicit arguments, I would say no. However, I can give a very real example of when this comes in handy.

While writing this post, I was testing the

1
reduce
version, and not getting the correct result. After fumbling about for a while, I realized that I had given the wrong initial value to
1
reduce
:
1
true
. This kind of mistake cannot happen when using
1
Any
, because the initial value is encoded in the data type itself. Of course, someone has to write that implementation first, so it is still prone to failure at some point. But if
1
Any
were in a library somewhere, it would be much less likely to have an error since that library could guarantee a correct implementation. Rather then each person writing their own implementation and forgetting if the initial value should be
1
true
or whatever.

More importantly, was it beneficial to implement the

1
extend
function? I would say wholeheartedly, yes! Using this abstraction, we made the rest of the code simpler. We could concentrate on each aspect of the problem in isolation, rather than conflating concerns. Since it required a
1
Functor
implementation, we also got a way to modify all values in the tree at once. This led to us being able to implement
1
foldMap
to regain efficiency after we lost a bit with abstraction. Plus, we got to see the beginnings of a
1
Comonad
in action. The only thing missing is the
1
extract
function. That seems like a nice function to let people figure out on their own though…