<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/on-indexing-operators-and-composition/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://www.win-vector.com/blog/2017/05/on-indexing-operators-and-composition/"> R – Win-Vector Blog</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>In this article I will discuss array indexing, operators, and composition in depth. If you work through this article you should end up with a very deep understanding of array indexing and the deep interpretation available when we realize indexing is an instance of function composition (or an example of <a rel="nofollow" href="https://en.wikipedia.org/wiki/Permutation_group" target="_blank">permutation groups</a> or <a rel="nofollow" href="https://en.wikipedia.org/wiki/Semigroup" target="_blank">semigroups</a>: some <em>very deep</em> yet accessible pure mathematics). </p>
<p><center><br>
<a rel="nofollow" href="https://commons.wikimedia.org/wiki/File:Permutation_initiale.svg" target="_blank"><img border="0" src="https://i2.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/02/NewImage-6.png?w=660" alt="NewImage" title="NewImage.png" data-recalc-dims="1">
<p>
A permutation of indices</a><br>
</center></p>
<p>In this article I will be working hard to convince you a very fundamental true statement is in fact true: array indexing is associative; and to simultaneously convince you that you should still consider this amazing (as it is a very strong claim with very many consequences). Array indexing respecting associative transformations should not be a-priori intuitive to the general programmer, as array indexing code is rarely re-factored or transformed, so programmers tend to have little experience with the effect. Consider this article an exercise to build the experience to make this statement a posteriori obvious, and hence something you are more comfortable using and relying on.</p>
<p><a rel="nofollow" href="https://cran.r-project.org/" target="_blank"><code>R</code></a>‘s array indexing notation is really powerful, so we will use it for our examples. This is going to be long (because I am trying to slow the exposition down enough to see all the steps and relations) and hard to follow without working examples (say with <code>R</code>), and working through the logic with pencil and a printout (math is not a spectator sport). I can’t keep all the steps in my head without paper, so I don’t really expect readers to keep all the steps in their heads without paper (though I have tried to organize the flow of this article and signal intent often enough to make this readable).<span></span></p>
<p>
<h2>R’s square-bracket array index operator</h2>
<p>In <code>R</code> array or vector indexing is commonly denoted by the square-bracket “<code>[]</code>“. For example if we have an array of values we can read them off as follows:</p>
<pre>
array &lt;- c('a', 'b', 'x', 'y')
print(array[1])
# [1] &quot;a&quot;

print(array[2])
# [1] &quot;b&quot;

print(array[3])
# [1] &quot;x&quot;

print(array[4])
# [1] &quot;y&quot;
</pre>
<p>A cool thing about <code>R</code>‘s array indexing operator is: you can pass in arrays or vectors of values and get many results back at the same time:</p>
<pre>
print(array)
# [1] &quot;b&quot; &quot;x&quot;
</pre>
<p>You can even use this notation on the left-hand side (LHS) during assignment:</p>
<pre>
array &lt;- 'zzz'
print(array)
# [1] &quot;a&quot;   &quot;zzz&quot; &quot;zzz&quot; &quot;y&quot;  
</pre>
<p>This ability to address any number of elements is the real power of <code>R</code>‘s array operator. However, if you know you only want one value I <em>strongly</em> suggest <em>always</em> using <code>R</code>‘s double-square operator “<code>[[]]</code>” which confirms you are selecting exactly one argument and is also the correct operator when dealing with lists.</p>
<p>Let’s get back to the single-square bracket “<code>[]</code>” and its vectorized behavior.</p>
<h2>Application: computing ranks</h2>
<p>Let’s use the square bracket to work with ranks.</p>
<p>Consider the following <code>data.frame</code>.</p>
<pre>
d &lt;- data.frame(x= c('d', 'a', 'b', 'c'),
                origRow= 1:4,
                stringsAsFactors= FALSE)
print(d)

#   x origRow
# 1 d       1
# 2 a       2
# 3 b       3
# 4 c       4
</pre>
<p>Suppose we want to compute the rank of the <code>x</code>-values. This is easy as <code>R</code> has a built in rank-calculating function:</p>
<pre>
print(rank(d$x))
# [1] 4 1 2 3
</pre>
<p>Roughly (and ignoring controlling treatment of ties) rank calculation can also be accomplished by sorting the data so <code>d$x</code> is ordered, ranking in this trivial configuration (just writing an increasing sequence), and then returning the data to its original order. We are going to use <code>R</code>‘s <code>order()</code> command. This calculates a permutation such that data is in sorted order (in this article all <a rel="nofollow" href="https://en.wikipedia.org/wiki/Permutation" target="_blank">permutations</a> are represented as arrays of length <code>n</code> containing each of the integers from <code>1</code> through <code>n</code> exactly once). <code>order()</code> works as follows:</p>
<pre>
ord &lt;- order(d$x)
print(ord)
# [1] 2 3 4 1

print(d$x[ord])
# [1] &quot;a&quot; &quot;b&quot; &quot;c&quot; &quot;d&quot;
</pre>
<p>The rank calculation written in terms of <code>order()</code> then looks like the following:</p>
<pre>
d2 &lt;- d[ord, ]
d2$rankX &lt;- 1:nrow(d2)
d3 &lt;- d2[order(d2$origRow), ]
print(d3$rankX)
# [1] 4 1 2 3
</pre>
<p>And we again have the rankings.</p>
<h2>Returning to the original order</h2>
<p>Of particular interest are the many ways we can return <code>d2</code> to original <code>d$origRow</code>-order. My absolute favorite way is indexing the left-side as in:</p>
<pre>
d4 &lt;- d2 # scratch frame to ready for indexed assignment
d4[ord, ] &lt;- d2 # invert by assignment
print(d4)

 #   x origRow rankX
 # 2 d       1     4
 # 3 a       2     1
 # 4 b       3     2
 # 1 c       4     3
</pre>
<p>The idea is <code>d2 &lt;- d[ord, ]</code> applies the permutation represented by <code>ord</code> and <code>d4[ord, ] &lt;- d2</code> undoes the permutation represented by <code>ord</code>. The notation is so powerful it almost looks like declarative programing (and a lot like the explicit fixed-point operators we were able to write in <code>R</code> <a rel="nofollow" href="http://www.win-vector.com/blog/2016/01/some-programming-language-theory-in-r/" target="_blank">here</a>). </p>
<p>Let’s see that again:</p>
<pre>
print(ord)
# [1] 2 3 4 1

invOrd &lt;- numeric(length(ord)) # empty vector to ready for indexed assigment
invOrd[ord] &lt;- 1:length(ord)   # invert by assignment

print(invOrd[ord])
# [1] 1 2 3 4

print(invOrd)
# [1] 4 1 2 3
</pre>
<p>We used the assignment <code>invOrd[ord] &lt;- 1:length(ord)</code> to “say” we wanted <code>invOrd[ord]</code> to be “<code>1 2 3 4</code>” and it is “<code>1 2 3 4</code>“. This means <code>invOrd</code> looks like an inverse of <code>ord</code>, which is why it can undo the <code>ord</code> permutation. We can get <code>d2</code> into the correct order by writing <code>d2[invOrd, ]</code>.</p>
<h2>Why did that indexing work?</h2>
<p>To work out why the above transformations are correct we will need a couple of transform rules (both to be established later!):</p>
<ul>
<li>Associativity of indexing: <code>(a[b]) = a[b]</code> (<code>a</code>, <code>b</code>, and <code>c</code> all permutations of <code>1:n</code>).</li>
<li>Equivalence of left and right inverses: <code>a[b] == 1:n</code> if and only if <code>b[a] == 1:n</code> (<code>a</code> and <code>b</code> both permutations of <code>1:n</code>). Note one does not have <code>a[b] == b[a]</code> in general (check with <code>a &lt;- c(2,1,3); b &lt;- c(1,3,2)</code>).
</li>
</ul>
<p>The above follow from the fact that composition of permutations (here seen as composition of indexing) form a <a rel="nofollow" href="https://en.wikipedia.org/wiki/Group_(mathematics)" target="_blank">group</a> similar to function composition, but let’s work up to that. </p>
<p>Here is our reasoning to show <code>d4</code> has its rows back in the original order of those of <code>d1</code>:</p>
<ol>
<li><code>d2$origRow == (1:n)[ord]</code> (as <code>d2 == d[ord, ]</code>), so <code>d2$origRow == ord</code> (as <code>(1:n)[ord] == ord</code>).</li>
<li><code>d4$origRow[ord] == d2$origRow</code> (by the left hand side assignment), so <code>d4$origRow[ord] == ord</code> (by the last step).
<p>If we could just cancel off the pesky “<code>ord</code>” from both sides of this equation we would be done. That is in fact how we continue, bringing in rules that justify the cancellation.
<li><code>(d4$origRow[ord])[invOrd] == d4$origRow[ord[invOrd]]</code> (by associaitivity, which we will prove later!). So we can convert <code>(d4$origRow[ord])[invOrd]  == ord[invOrd]</code> (derivable from the last step) into <code>d4$origRow[ord[invOrd]] == ord[invOrd]</code>.
<li>Substituting in <code>ord[invOrd] == 1:n</code> (the other big thing we will show is: <code>ord[invOrd] == invOrd[ord] == 1:n</code>) yields <code>d4$origRow == 1:n</code>. This demonstrates <code>d4</code>‘s rows must be back in the right order (that which we were trying to show).</li>

<p>So all that remains is to discuss associativity, and also show why <code>invOrd[ord] == 1:n</code> (which was established by the assignment <code>invOrd[ord] &lt;- 1:length(ord)</code>) implies <code>ord[invOrd] == 1:n</code> (what we actually used in our argument).</p>
<h2>Some operator notation</h2>
<p>To make later steps easier, let’s introduce some <code>R</code>-operator notation. Define:</p>
<ul>
<li>
An array indexing operator:
<pre>
 `%[]%` &lt;- function(a,b) { a[b] }
</pre>
</li>
<li>
A function composition operator:
<pre>
 `%.%` &lt;- function(f,g) { function(x) f(g(x)) }
</pre>
<p>(this is pure function composition, allows us to write <code>abs(sin(1:4))</code> as <code>(abs %.% sin)(1:4)</code>).

<li>
A function application operator:
<pre>
  `%+%` &lt;- function(f,g) { f(g) }
</pre>
<p> (which is only right-associative as in <code>abs %+% ( sin %+% 1:4 ) == abs(sin(1:4))</code>). This notation is interesting as it moves us towards <a rel="nofollow" href="https://en.wikipedia.org/wiki/Tacit_programming" target="_blank">“point free notation”</a>, though to move all the way there we would need a point-free function abstraction operator.

<li>
A reverse application operator such as “<code>magrittr::`%>%`</code>” or the following imitation:
<pre>
  `%|>%` &lt;- function(f,g) { g(f) }
</pre>
<p>(which can write <code>abs(sin(1:4))</code> as <code>1:4 %|>% sin %|>% abs</code>, the notation being in reference to <code>F#</code>‘s as mentioned <a rel="nofollow" href="https://www.r-bloggers.com/simpler-r-coding-with-pipes-the-present-and-future-of-the-magrittr-package/" target="_blank">here</a>). Here we left out the parenthesis not because <code>%|>%</code> is fully associative (it is not), but because it is left-associative which is also the order <code>R</code> decides to evaluate user operators (so <code>1:4 %|>% sin %|>% abs</code> is just shorthand for <code>( 1:4 %|>% sin ) %|>% abs</code>).


<p>With <code>%[]%</code> our claim about inverses is written as follows. For permutations on <code>1:n</code>: <code>ord %[]% invOrd == 1:n</code> implies <code>invOrd %[]% ord == 1:n</code>. (Again we do not have <code>a %[]% b == b %[]% a</code> in general as shown by <code>a &lt;- c(2,1,3); b &lt;- c(1,3,2)</code>.)</p>
<h3>Semigroup axioms</h3>
<p>In operator notation we claim sequenced selectionlowing are true (not all of which we will confirm here). Call an element “a permutation” if it is an array of length <code>n</code> containing each integer from <code>1</code> through  exactly once. Call an element “a sequenced selection” if it is an array of length <code>n</code> containing only integers from <code>1</code> through  (possibly with repetitions). <code>n</code> will be held at a single value throughout. All permutations are sequenced selections.</p>
<p>Permutations and sequenced selections can be confirmed to obey the following axioms:</p>
<ol>
<li>For all <code>a, b</code> sequenced selections we have <code>a %[]% b</code> is itself a sequenced selection <code>1:n</code>. If both <code>a, b</code> are permutations then <code>a %[]% b</code> is also a permutation.</li>
<li>(this is the big one) For all <code>a, b, c</code> sequenced selections we have: <code>( a %[]% b ) %[]% c  ==  a %[]% ( b %[]% c )</code>.</li>
<li>For all <code>a</code> that are sequenced selections we have: <code>(1:n) %[]% a == a</code> and <code>a %[]% (1:n) == a</code>. We call <code>1:n</code> the multiplicative identity and it is often denoted as <code>e &lt;- 1:n</code>.</li>
<li>For all “<code>a</code>” a permutation there exists <code>La, Ra</code> permutations of <code>1:n</code> such that <code>La %[]% a == 1:n</code> and <code>a %[]% Ra == 1:n</code>. Also, we can derive <code>La == Ra</code> from the earlier axioms.</li>
</ol>
<p>The above are essentially the axioms defining a mathematical object called a <a rel="nofollow" href="https://en.wikipedia.org/wiki/Semigroup" target="_blank">semigroup</a> (for the sequenced selections) or <a rel="nofollow" href="https://en.wikipedia.org/wiki/Group_(mathematics)#Definition" target="_blank">group</a> (for the permutations). </p>
<p><center><br>
<img border="0" src="https://i0.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/03/NewImage-1.png?resize=400%2C232" alt="NewImage" title="NewImage.png" data-recalc-dims="1">
<p>A famous realization of a permutation group: Rubik’s Cube.<br>
</center></p>
<p>Checking our operator “<code>%[]%</code>” obeys axioms 1 and 3 is fairly mechanical. Confirming axiom 4 roughly follows from the fact you can sort arrays (i.e. that <code>order()</code> works). Axiom 2 (associativity) is the amazing one. A lot of the power of groups comes from the associativity and a lot of the math of things like <a rel="nofollow" href="http://www.win-vector.com/blog/2016/08/the-magrittr-monad/" target="_blank">Monads</a> is just heroic work trying to retain useful semigroup-like properties.</p>
<p><center><br>
<a rel="nofollow" href="https://plus.maths.org/content/play-win-nim" target="_blank"><img border="0" src="https://i0.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/03/NewImage-2.png?w=660" alt="NewImage" title="NewImage.png" data-recalc-dims="1"></a>
<p>
<a rel="nofollow" href="https://en.wikipedia.org/wiki/Nim" target="_blank">Nim</a>: an associative irreversible state space.<br>
</center></p>
<h3>A bit more on inverses</h3>
<p>Suppose we had confirmed all of the above axioms, then our remaining job would be to confirm that <code>invOrd[ord] == 1:n</code> implies <code>ord[invOrd] == 1:n</code>. This is easy in the <code>%[]%</code> notation. </p>
<p>The argument is as follows:</p>
<ul>
<li>By axiom 4 we know there exist <code>L</code> and <code>R</code> such that <code>L ord == 1:n</code> and <code>ord R == 1:n</code>. In fact we have already found <code>L == invOrd</code>. So if we can show <code>L==R</code> we are done.</li>
<li>Expand <code>L %[]% ord %[]% R</code> two ways using axiom 2 (associativity):
<ul>
<li><code>L %[]% ord %[]% R  ==  ( L %[]% ord ) %[]% R  ==  (1:n) %[]% R  == R</code></li>
<li><code>L %[]% ord %[]% R  ==  L ( %[]% ord %[]% R )  ==  L %[]% (1:n) == L</code></li>
</ul>
</li>
<li>So: <code>L == R == invOrd</code> as required.</li>
</ul>
<blockquote><p>Note:</p>
<p>An important property of <code>%[]%</code> and <code>%.%</code> is that they are fully associative over their values (permutations and functions respectively). We can safely re-parenthesize them (causing different execution order and different intermediate results) without changing outcomes. This is in contrast to <code>%+%</code>, <code>%|>%</code>, and <code>%>%</code> which are only <em>partially</em> associative (yet pick up most of their power from properly managing what associativity they do have).</p>
<p><code>%>%</code> works well because it associates in the same direction as <code>R</code>‘s parser. We don’t write parenthesis in “<code>-4 %>% abs %>% sqrt</code>” because in this case it is unambiguous that it <em>must be the case</em> that the parenthesis are implicitly “<code>( -4 %>% abs ) %>% sqrt</code>” (by <code>R</code> left-associative user operator parsing) as “<code>-4 %>% ( abs %>% sqrt)</code>” would throw an exception (so <em>post hoc ergo propter hoc</em> could not be how <code>R</code> interpreted “<code>-4 %>% abs %>% sqrt</code>“, as that did not throw an exception). So it isn’t that both associations are equal (they are not), it is that only one of them is “well formed” and that one happens to be the way <code>R</code>‘s parser works. It isn’t that <code>R</code>‘s parser is magically looking ahead to solve this, it is just the conventions match.</p>
<p><code>%[]%</code> is also neat in that values have an nice interpretation as functions over values. All the other operators are either more about functions (<code>%.%</code>) or more about values (<code>%+%</code>, <code>%|>%</code>, and <code>%>%</code>).
</p>
</blockquote>
<h2>The amazing emergence of full associativity</h2>
<p>Now consider the following two (somewhat complicated) valid <code>R</code> expressions involving permutations <code>a</code>, <code>b</code>, and <code>c</code>:</p>
<ol>
<li><code>a[b]</code>: which means calculate <code>x &lt;-  b[c]</code> and then calculate <code>a[x]</code>.</li>
<li><code>(a[b])</code>: which means calculate <code>y &lt;- a[b]</code> and then calculate <code>y</code>.</li>
</ol>
<blockquote><p>Consider this as a possible a bar bet with programming friends: can they find two vectors that are permutations of <code>1:n</code> (or even just length <code>n</code> vectors consisting of any combination of taken from the integers </blockquote></ul></ol>