Haskell evolved a lot since the last time I seriously wrote any
Haskell code, so much so that all my old programs broke. My Monad
instances don't compile any more because I'm no longer allowed to
have a monad which isn't also an instance of Applicative. Last time I used
Haskell, Applicative wasn't even a thing. I had read the McBride and
Paterson paper that introduced applicative functors, but that was
years ago, and I didn't remember any of the details. (In fact, while
writing this article, I realized that the paper I read was a preprint,
and I probably read it before it was published, in 2008.) So to
resuscitate my old code I had to implement a bunch of <*> functions
and since I didn't really understand what it was supposed to be doing
I couldn't do that. It was a very annoying experience.
Anyway I got that more or less under control (maybe I'll publish a
writeup of that later) and moved on to Traversable which, I hadn't realized
before, was also introduced in that same paper. (In the
prepublication version, Traversable was been given the unmemorable name
IFunctor.) I had casually looked into this several times in the
last few years but I never found anything enlightening. A Traversable is a
functor (which must also implement Foldable, but let's pass over that
for now, no pun intended) that implements a traverse method with the
following signature:
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
The traversable functor itself here is t. The f thing is an
appurtenance. Often one looks at the type of some function and says “Oh, that's what
that does”, but I did not get any understanding from this signature.
The first thing to try here is to make it less abstract. I was
thinking about Traversable this time because I thought I might want
it for a certain type of tree structure I was working with. So I
defined an even simpler tree structure:
data Tree a = Con a | Add (Tree a) (Tree a)
deriving (Eq, Show)
Defining a bunch of other cases wouldn't add anything to my
understanding, and it would make it take longer to try stuff, so I
really want to use the simplest possible example here. And this is
it: one base case, one recursive case.
Then I tried to make this type it into a Traversable instance. First we need
it to be a Functor, which is totally straightforward:
instance Functor Tree where
fmap f (Con a) = Con (f a)
fmap f (Add x y) = Add (fmap f x) (fmap f y)
Then we need it to be a Foldable, which means it needs to provide a
version of foldr. The old-fashioned foldr was
foldr :: (a -> b -> b) -> b -> [a] -> b
but these days the list functor in the third place has been generalized:
foldr :: Foldable f => (a -> b -> b) -> b -> f a -> b
The idea is that foldr fn collapses a list of as into a single b
value by feeding in the as one at a time. Each time, foldr takes
the previous b and the current a and constructs a new b. The
second argument is the initial value of b.
Another way to think about it is that every list has the form
e1 : e2 : .... : []
and foldr fn b applied to this list replaces the (:) calls with fn
and the trailing [] with b, giving me
e1 `f` e2 `f` .... `f` b
The canonical examples
for lists are:
sum = foldr (+) 0
(add up the elements, starting with zero) and
length = foldr (\_ -> (+ 1)) 0
(ignore the elements, adding 1 to the total each time, starting with
zero). Also foldr (:) [] is the identity function for lists because
it replaces the (:) calls with (:) and the trailing [] with [].
Anyway for Tree it looks like this:
instance Foldable Tree where
foldr f b (Con a) = f a b
foldr f b (Add x y) = (foldr f) (foldr f b x) y
The Con clause says to take the constant value and combine it with
the default total. The Add clause says to first fold up the
left-side subtree x to a single value, then use that as the initial
value for folding up the right-side subtree y, so everything gets
all folded up together. (We could of course do the right subtree
before the left; the results would be different but just as good.)
I didn't write this off the top of my head, I got it by following the
types, like this:
In the first clause
foldr f b (Con a) = ???
we have a function f that wants an a value and
a b value, and we have both an a and a b, so put the tabs in the
slots.
In the second clause
foldr f b (Add x y) = ???
f needs an a value and none is available, so we can't use f
by itself. We can only use it recursively via foldr. So forget
f, we will only be dealing only with foldr f, which has type
b -> Tree a -> b. We need to apply this to a b value and the
only one we have is b, and then we need to apply that to one of
the subtrees, say x, and thus we have synthesized the
foldr f b x subexpression. Then pretty much the same process
gets us the rest of it: we need a b and the only one we have now
is foldr f b x, and then we need another tree and the only one we
haven't used is y.
It turns out it is easier and more straightforward to write foldMap
instead, but I didn't know that at the time. I won't go into it
further because I have already digressed enough. The preliminaries
are done, we can finally get on to the thing I wanted, the Traversable:
instance Traversable Tree where
traverse = ....
and here I was stumped. What is this supposed to actually do?
For our Tree functor it has this signature:
traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
Okay, a function a -> f b I understand, it turns each tree leaf
value into a list or something, so at each point of the tree it gets
out a list of bs, and it potentially has one of those for each item
in the input tree. But how the hell do I turn a tree of lists into
a single list of Tree b? (The answer is that the secret sauce is
in the Applicative, but I didn't understand that yet.)
I scratched my head and read a bunch of different explanations and
none of them helped. All the descriptions I found were in either
prose or mathematics and I still couldn't figure out what it was for.
Finally I just wrote a bunch of examples and at last the light came
on. I'm going to show you the examples and maybe the light will come
on for you too.
We need two Traversable functors to use as examples. We don't have a Traversable
implementation for Tree yet so we can't use that. When I think of
functors, the first two I always think of are List and Maybe, so
we'll use those.
> traverse (\n -> [1..n]) Nothing
[Nothing]
> traverse (\n -> [1..n]) (Just 3)
[Just 1,Just 2,Just 3]
Okay, I think I could have guessed that just from the types. And
going the other way is not very interesting because the output, being
a Maybe, does not have that much information in it.
> let f x = if even x then Just (x `div` 2) else Nothing
If the 
is even then the result is just half of , and
otherwise the division by 2 “fails” and the result is nothing.
Now:
> traverse f [ 1, 2, 3, 4 ]
Nothing
> traverse f [ 10, 4, 18 ]
Just [5,2,9]
It took me a few examples to figure out what was going on here: When
all the list elements are even, the result is Just a list of half of
each. But if any of the elements is odd, that spoils the whole result
and we get Nothing. (traverse f [] is Just [] as one would
expect.)
That pretty much exhausts what can be done with lists and maybes. Now
I have two choices about where to go next: I could try making both
functors List, or I could use a different functor entirely. (Making
both Maybe seemed like a nonstarter.) Using List twice seemed
confusing, and when I tried it I could kinda see what it was doing but
I didn't understand why. So I took a third choice: I worked up a Traversable
instance for Tree just by following the types even though I didn't
understand what it ought to be doing. I thought I'd at least see if I
could get the easy clause:
traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
instance Traversable Tree where
traverse fn (Con a) = ...
In the ... I have fn :: a -> f b and I have at hand a single a. I need to
construct a Tree b. The only way to get a b is to apply fn to
it, but this gets me an f b and I need f (Tree b). How do I get the
Tree in there? Well, that's what Con is for, getting Tree in
there, it turns a t into Tree t. But how do I do that inside of
f? I tinkered around a little bit and eventually found
traverse fn (Con a) = Con <$> (fn a)
which not only type checks but looks like it could even be correct.
So now I have a motto for what <$> is about: if I have some
function, but I want to use it inside of some applicative functor
f, I can apply it with <$> instead of with $.
Which, now that I have said it myself, I realize it is exactly what
everyone else was trying to tell me all along: normal function
application takes an a -> b and applies to to an a giving a b.
Applicative application takes an f (a -> b) and applies it to an f a
giving an f b. That's what applicative functors are all about,
doing stuff inside of f.
Okay, I can listen all day to an explanation of what an electric
drill does, but until I hold it in my hand and drill some holes I
don't really understand.
Encouraged, I tried the hard clause:
traverse fn (Add x y) = ...
and this time I had a roadmap to follow:
traverse fn (Add x y) = Add <$> ...
The Con clause had fn a at that point to produce an f b but that won't
work here because we don't have an a, we have a whole Tree a, and we
don't need an f b, we need an f (Tree b). Oh, no problem,
traverse fn supposedly turns a Tree a into an f (Tree b), which
is just what we want.
And it makes sense to have a recursive call to traverse because this is the
recursive part of the recursive data structure:
traverse fn (Add x y) = Add <$> (traverse fn x) ...
Clearly traverse fn y is going to have to get in there somehow, and
since the pattern for all the applicative functor stuff is
f <$> ... <*> ... <*> ...
let's try that:
traverse fn (Add x y) = Add <$> (traverse fn x) <*> (traverse fn y)
This looks plausible. It compiles, so it must be doing something.
Partial victory! But what is it doing? We can run it and see, which
was the whole point of an exercise: work up a Traversable instance for Tree
so that I can figure out what Traversable is about.
Here are some example trees:
t1 = Con 3 -- 3
t2 = Add (Con 3) (Con 4) -- 3 + 4
t3 = Add (Add (Con 3) (Con 4)) (Con 2) -- (3 + 4) + 2
(I also tried Add (Con 3) (Add (Con 4) (Con 2)) but it did not
contribute any new insights so I will leave it out of this article.)
First we'll try Maybe. We still have that f function from before:
f x = if even x then Just (x `div` 2) else Nothing
but traverse f t1, traverse f t2, and traverse f t3 only produce
Nothing, presumably because of the odd numbers in the trees. One
odd number spoils the whole thing, just like in a list.
So try:
traverse f (Add (Add (Con 10) (Con 4)) (Con 18))
which yields:
Just (Add (Add (Con 5) (Con 2)) (Con 9))
It keeps the existing structure, and applies f at each value
point, just like fmap, except that if f ever returns Nothing
the whole computation is spoiled and we get Nothing. This is
just like what traverse f was doing on lists.
But where does that spoilage behavior come from exactly? It comes
from the overloaded behavior of <*> in the Applicative instance of Maybe:
(Just f) <*> (Just x) = Just (f x)
Nothing <*> _ = Nothing
_ <*> Nothing = Nothing
Once we get a Nothing in there at any point, the Nothing takes
over and we can't get rid of it again.
I think that's one way to think of traverse: it transforms each
value in some container, just like fmap, except that where fmap
makes all its transformations independently, and reassembles the exact
same structure, with traverse the reassembly is done with the
special Applicative semantics. For Maybe that means “oh, and if at any
point you get Nothing, just give up”.
Now let's try the next-simplest Applicative, which is List. Say,
g n = [ 1 .. n ]
Now traverse g (Con 3) is [Con 1,Con 2,Con 3] which is not exactly
a surprise but traverse g (Add (Con 3) (Con 4)) is something that
required thinking about:
[Add (Con 1) (Con 1),
Add (Con 1) (Con 2),
Add (Con 1) (Con 3),
Add (Con 1) (Con 4),
Add (Con 2) (Con 1),
Add (Con 2) (Con 2),
Add (Con 2) (Con 3),
Add (Con 2) (Con 4),
Add (Con 3) (Con 1),
Add (Con 3) (Con 2),
Add (Con 3) (Con 3),
Add (Con 3) (Con 4)]
This is where the light finally went on for me. Instead of thinking
of lists as lists, I should be thinking of them as choices. A list
like [ "soup", "salad" ] means that I can choose soup or salad, but
not both. A function g :: a -> [b] says, in restaurant a, what
bs are on the menu.
The g function says what is on the menu at each node. If a node has
the number 4, I am allowed to choose any of [1,2,3,4], but if it has
the number 3 then the choice 4 is off the menu and I can choose only
from [1,2,3].
Traversing g over a Tree means, at each leaf, I am handed a menu,
and I make a choice for what goes at that leaf. Then the result of
traverse g is a complete menu of all the possible complete trees I
could construct.
Now I finally understand how the t and the f switch places in
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
I asked “how the hell do I turn a tree of lists into a single list
of Tree b”? And that's the answer: each list is a local menu of
dishes available at one leaf, and the result list is the global menu
of the complete dinners available over the entire tree.
Okay! And indeed traverse g (Add (Add (Con 3) (Con 4)) (Con 2)) has
24 items, starting
Add (Add (Con 1) (Con 1)) (Con 1)
Add (Add (Con 1) (Con 1)) (Con 2)
Add (Add (Con 1) (Con 2)) (Con 1)
...
and ending
Add (Add (Con 3) (Con 4)) (Con 1)
Add (Add (Con 3) (Con 4)) (Con 2)
That was traversing a list function over a Tree. What if I go the
other way? I would need an Applicative instance for Tree and I didn't
really understand Applicative yet so that wasn't going to happen for a
while. I know I can't really understand Traversable without understanding
Applicative first but I wanted to postpone the day of reckoning as long as
possible.
What other functors do I know? One easy one is the functor that takes
type a and turns it into type (String, a). Haskell even has a
built-in Applicative instance for this, so I tried it:
> traverse (\x -> ("foo", x)) [1..3]
("foofoofoo",[1,2,3])
> traverse (\x -> ("foo", x*x)) [1,5,2,3]
("foofoofoofoo",[1,25,4,9])
Huh, I don't know what I was expecting but I think that wouldn't have
been it. But I figured out what was going on: the built-in Applicative
instance for the a -> (String, a) functor just concatenates the
strings. In general it is defined on a -> (m, b) whenever m is a
monoid, and it does fmap on the right component and uses monoid
concatenation on the left component. So I can use integers instead of
strings, and it will add the integers instead of concatenating the
strings. Except no, it won't, because there are several ways to make
integers into a monoid, but each type can only have one kind of
Monoid operations, and if one was wired in it might not be the one I
want. So instead they define a bunch of types that are all integers
in obvious disguises, just labels stuck on them that say “I am not an
integer, I am a duck”; “I am not an integer, I am a potato”. Then
they define different overloadings for “ducks” and “potatoes”. Then
if I want the integers to get added up I can put duck labels on my
integers and if I want them to be multiplied I can stick potato labels
on instead. It looks like this:
import Data.Monoid
h n = (Sum 1, n*10)
Sum is the duck label. When it needs to combine two
ducks, it will add the integers:
> traverse h [5,29,83]
(Sum {getSum = 3},[50,290,830])
But if we wanted it to multiply instead we could use the potato label,
which is called Data.Monoid.Product:
> traverse (\n -> (Data.Monoid.Product 7, 10*n)) [5,29,83]
(Product {getProduct = 343}, [50,290,830])
There are three leaves, so we multiply three sevens and get 343.
Or we could do the same sort of thing on a Tree:
> traverse (\n -> (Data.Monoid.Product n, 10*n)) (Add (Con 2) (Add (Con 3) (Con 4)))
(Product {getProduct = 24}, Add (Con 20) (Add (Con 30) (Con 40)))
Here instead of multiplying together a bunch of sevens we multiply
together the leaf values themselves.
The McBride and Paterson paper spends a couple of pages talking about
traversals over monoids, and when I saw the example above it started
to make more sense to me. And their ZipList example became clearer
too. Remember when we had a function that gave us a menu at every
leaf of a tree, and traverse-ing that function over a tree gave us a
menu of possible trees?
> traverse (\n -> [1,n,n*n]) (Add (Con 2) (Con 3))
[Add (Con 1) (Con 1),
Add (Con 1) (Con 3),
Add (Con 1) (Con 9),
Add (Con 2) (Con 1),
Add (Con 2) (Con 3),
Add (Con 2) (Con 9),
Add (Con 4) (Con 1),
Add (Con 4) (Con 3),
Add (Con 4) (Con 9)]
There's another useful way to traverse a list
function. Instead of taking each choice at each leaf we make a
single choice ahead of time about whether we'll take the first,
second, or third menu item, and then we take that item every time:
> traverse (\n -> Control.Applicative.ZipList [1,n,n*n]) (Add (Con 2) (Con 3))
ZipList {getZipList = [Add (Con 1) (Con 1),
Add (Con 2) (Con 3),
Add (Con 4) (Con 9)]}
There's a built-in instance for Either a b also. It's a lot like
Maybe. Right is like Just and Left is like Nothing. If all
the sub-results are Right y then it rebuilds the structure with all
the ys and gives back Right (structure). But if any of the
sub-results is Left x then the computation is spoiled and it gives
back the first Left x. For example:
> traverse (\x -> if even x then Left (x `div` 2) else Right (x * 10)) [3,17,23,9]
Right [30,170,230,90]
> traverse (\x -> if even x then Left (x `div` 2) else Right (x * 10)) [3,17,22,9]
Left 11
Okay, I think I got it.
Now I just have to drill some more holes.
<figcaption>Fixpoints of a simple function (from Wikimedia Commons)</figcaption></figure>
. (Actually, integers is too specific; any linearly ordered domain will do.) An inversion is a pair of positions in 
which are “out of order”: that is, 
such that 
but 
. So, for example, ![\sigma = [3,5,1,4,2]](https://s0.wp.com/latex.php?latex=%5Csigma+%3D+%5B3%2C5%2C1%2C4%2C2%5D&bg=ffffff&fg=333333&s=0 "\sigma = [3,5,1,4,2]")
has six inversions, namely 
. (Here I’ve written the elements that are out of order rather than their positions, which doesn’t matter much when the elements are all distinct; but it’s important to keep in mind that e.g. ![[2,2,1]](https://s0.wp.com/latex.php?latex=%5B2%2C2%2C1%5D&bg=ffffff&fg=333333&s=0 "[2,2,1]")
has two inversions, not one, because each copy of 
makes an inversion with the 
.) The total number of inversions of 
.
, when 
time. Can it be done any faster?
is the set of sorted lists with merge as the monoid operation; 
is the natural numbers under addition. The spark operation takes two sorted lists and counts the number of inversions between them. So the monoid on pairs 
merges the lists, and adds the inversion counts together with the number of inversions between the two lsits.
be any sorted list, then we need
, that is, 
.
and the spark 
at the same time, so we bake that possibility into the class.
with 
.
and so on. Alternatively, if 
is a monoid, and 
is a commutative monoid. To connect them, we also suppose there is another binary operation 
, which I will pronounce “spark”. The way I like to think of it is that two values of type 
, we have 
is boring and can never produce a nontrivial spark with anything else), and 
(i.e. sparking commutes with the monoid operations). Similar laws should hold if we fix the second argument of 
instead of the first.
, since
. The proof that 
is similar.![\begin{array}{rcl} & & ((a_1,b_1) \otimes (a_2,b_2)) \otimes (a_3,b_3) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math}\}} \\[0.5em] & & (a_1 \diamond a_2, b_1 \oplus b_2 \oplus (a_1 \cdot a_2)) \otimes (a_3,b_3) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math} again\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus b_2 \oplus (a_1 \cdot a_2) \oplus b_3 \oplus ((a_1 \diamond a_2) \cdot a_3)) \\[0.5em] & = & \qquad \text{\{\begin{math}- \cdot a_3\end{math} is a homomorphism, \begin{math}\oplus\end{math} is commutative\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus b_2 \oplus b_3 \oplus (a_1 \cdot a_2) \oplus (a_1 \cdot a_3) \oplus (a_2 \cdot a_3)) \end{array}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Barray%7D%7Brcl%7D+%26+%26+%28%28a_1%2Cb_1%29+%5Cotimes+%28a_2%2Cb_2%29%29+%5Cotimes+%28a_3%2Cb_3%29+%5C%5C%5B0.5em%5D+%26+%3D+%26+%5Cqquad+%5Ctext%7B%5C%7Bexpand+definition+of+%5Cbegin%7Bmath%7D%5Cotimes%5Cend%7Bmath%7D%5C%7D%7D+%5C%5C%5B0.5em%5D+%26+%26+%28a_1+%5Cdiamond+a_2%2C+b_1+%5Coplus+b_2+%5Coplus+%28a_1+%5Ccdot+a_2%29%29+%5Cotimes+%28a_3%2Cb_3%29+%5C%5C%5B0.5em%5D+%26+%3D+%26+%5Cqquad+%5Ctext%7B%5C%7Bexpand+definition+of+%5Cbegin%7Bmath%7D%5Cotimes%5Cend%7Bmath%7D+again%5C%7D%7D+%5C%5C%5B0.5em%5D+%26+%26+%28a_1+%5Cdiamond+a_2+%5Cdiamond+a_3%2C+b_1+%5Coplus+b_2+%5Coplus+%28a_1+%5Ccdot+a_2%29+%5Coplus+b_3+%5Coplus+%28%28a_1+%5Cdiamond+a_2%29+%5Ccdot+a_3%29%29+%5C%5C%5B0.5em%5D+%26+%3D+%26+%5Cqquad+%5Ctext%7B%5C%7B%5Cbegin%7Bmath%7D-+%5Ccdot+a_3%5Cend%7Bmath%7D+is+a+homomorphism%2C+%5Cbegin%7Bmath%7D%5Coplus%5Cend%7Bmath%7D+is+commutative%5C%7D%7D+%5C%5C%5B0.5em%5D+%26+%26+%28a_1+%5Cdiamond+a_2+%5Cdiamond+a_3%2C+b_1+%5Coplus+b_2+%5Coplus+b_3+%5Coplus+%28a_1+%5Ccdot+a_2%29+%5Coplus+%28a_1+%5Ccdot+a_3%29+%5Coplus+%28a_2+%5Ccdot+a_3%29%29+%5Cend%7Barray%7D&bg=ffffff&fg=333333&s=0 "\begin{array}{rcl} & & ((a_1,b_1) \otimes (a_2,b_2)) \otimes (a_3,b_3) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math}\}} \\[0.5em] & & (a_1 \diamond a_2, b_1 \oplus b_2 \oplus (a_1 \cdot a_2)) \otimes (a_3,b_3) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math} again\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus b_2 \oplus (a_1 \cdot a_2) \oplus b_3 \oplus ((a_1 \diamond a_2) \cdot a_3)) \\[0.5em] & = & \qquad \text{\{\begin{math}- \cdot a_3\end{math} is a homomorphism, \begin{math}\oplus\end{math} is commutative\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus b_2 \oplus b_3 \oplus (a_1 \cdot a_2) \oplus (a_1 \cdot a_3) \oplus (a_2 \cdot a_3)) \end{array}")
![\begin{array}{rcl} & & (a_1,b_1) \otimes ((a_2,b_2) \otimes (a_3,b_3)) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math}\}} \\[0.5em] & & (a_1,b_1) \otimes (a_2 \diamond a_3, b_2 \oplus b_3 \oplus (a_2 \cdot a_3)) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math} again\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus (b_2 \oplus b_3 \oplus (a_2 \cdot a_3)) \oplus (a_1 \cdot (a_2 \diamond a_3))) \\[0.5em] & = & \qquad \text{\{\begin{math}a_1 \cdot -\end{math} is a homomorphism, \begin{math}\oplus\end{math} is commutative\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus b_2 \oplus b_3 \oplus (a_1 \cdot a_2) \oplus (a_1 \cdot a_3) \oplus (a_2 \cdot a_3)) \end{array}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Barray%7D%7Brcl%7D+%26+%26+%28a_1%2Cb_1%29+%5Cotimes+%28%28a_2%2Cb_2%29+%5Cotimes+%28a_3%2Cb_3%29%29+%5C%5C%5B0.5em%5D+%26+%3D+%26+%5Cqquad+%5Ctext%7B%5C%7Bexpand+definition+of+%5Cbegin%7Bmath%7D%5Cotimes%5Cend%7Bmath%7D%5C%7D%7D+%5C%5C%5B0.5em%5D+%26+%26+%28a_1%2Cb_1%29+%5Cotimes+%28a_2+%5Cdiamond+a_3%2C+b_2+%5Coplus+b_3+%5Coplus+%28a_2+%5Ccdot+a_3%29%29+%5C%5C%5B0.5em%5D+%26+%3D+%26+%5Cqquad+%5Ctext%7B%5C%7Bexpand+definition+of+%5Cbegin%7Bmath%7D%5Cotimes%5Cend%7Bmath%7D+again%5C%7D%7D+%5C%5C%5B0.5em%5D+%26+%26+%28a_1+%5Cdiamond+a_2+%5Cdiamond+a_3%2C+b_1+%5Coplus+%28b_2+%5Coplus+b_3+%5Coplus+%28a_2+%5Ccdot+a_3%29%29+%5Coplus+%28a_1+%5Ccdot+%28a_2+%5Cdiamond+a_3%29%29%29+%5C%5C%5B0.5em%5D+%26+%3D+%26+%5Cqquad+%5Ctext%7B%5C%7B%5Cbegin%7Bmath%7Da_1+%5Ccdot+-%5Cend%7Bmath%7D+is+a+homomorphism%2C+%5Cbegin%7Bmath%7D%5Coplus%5Cend%7Bmath%7D+is+commutative%5C%7D%7D+%5C%5C%5B0.5em%5D+%26+%26+%28a_1+%5Cdiamond+a_2+%5Cdiamond+a_3%2C+b_1+%5Coplus+b_2+%5Coplus+b_3+%5Coplus+%28a_1+%5Ccdot+a_2%29+%5Coplus+%28a_1+%5Ccdot+a_3%29+%5Coplus+%28a_2+%5Ccdot+a_3%29%29+%5Cend%7Barray%7D&bg=ffffff&fg=333333&s=0 "\begin{array}{rcl} & & (a_1,b_1) \otimes ((a_2,b_2) \otimes (a_3,b_3)) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math}\}} \\[0.5em] & & (a_1,b_1) \otimes (a_2 \diamond a_3, b_2 \oplus b_3 \oplus (a_2 \cdot a_3)) \\[0.5em] & = & \qquad \text{\{expand definition of \begin{math}\otimes\end{math} again\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus (b_2 \oplus b_3 \oplus (a_2 \cdot a_3)) \oplus (a_1 \cdot (a_2 \diamond a_3))) \\[0.5em] & = & \qquad \text{\{\begin{math}a_1 \cdot -\end{math} is a homomorphism, \begin{math}\oplus\end{math} is commutative\}} \\[0.5em] & & (a_1 \diamond a_2 \diamond a_3, b_1 \oplus b_2 \oplus b_3 \oplus (a_1 \cdot a_2) \oplus (a_1 \cdot a_3) \oplus (a_2 \cdot a_3)) \end{array}")
and 
but I didn’t want to be that pedantic here.
will be commutative as well.
, we end up with all possible sparks between pairs of 
, and one can prove that this holds more generally. In particular, if we start with a list of ![[a_1, a_2, \dots, a_n]](https://s0.wp.com/latex.php?latex=%5Ba_1%2C+a_2%2C+%5Cdots%2C+a_n%5D&bg=ffffff&fg=333333&s=0 "[a_1, a_2, \dots, a_n]")
,
:![[(a_1, \varepsilon_B), (a_2, \varepsilon_B), \dots, (a_n, \varepsilon_B)]](https://s0.wp.com/latex.php?latex=%5B%28a_1%2C+%5Cvarepsilon_B%29%2C+%28a_2%2C+%5Cvarepsilon_B%29%2C+%5Cdots%2C+%28a_n%2C+%5Cvarepsilon_B%29%5D&bg=ffffff&fg=333333&s=0 "[(a_1, \varepsilon_B), (a_2, \varepsilon_B), \dots, (a_n, \varepsilon_B)]")
,
,
. Of course there are 
<figcaption>Girls learning computer science using Scratch (
<figcaption>The first computer, only 70 years ago</figcaption></figure>
<figcaption>Scratch, a language designed for early computer science</figcaption></figure>
</figure>
</figure>
<figcaption>The wrong way to start strength training.</figcaption></figure>
<figcaption>Middle school students learning Haskell with CodeWorld</figcaption></figure>
