Evaluate Conway chained arrow notation Background

Conway chained arrow notation is a notation to express very large numbers. It consists of zero or more positive integers separated by right arrows, e.g. \$2 \to 3 \to 4 \to 5 \to 6 \$.

Assuming \$p, q, a_1, \dots, a_n\$ are positive integers and \$X\$ is an abbreviation for a nonempty chain \$a_1 \to a_2 \to \dots \to a_n\$, the rules for evaluating such a notation are as follows:

$$
\begin{align}
(\text{empty chain}) &amp;= 1 \\
(p) &amp;= p \\
p \to q &amp;= p^q \\
X \to 1 &amp;= X \\
X \to 1 \to p &amp;= X \\
X \to (p+1)\to (q+1) &amp;= X \to (X \to p\to (q+1))\to q
\end{align}
$$

A length-3 chain has an equivalent up-arrow notation: \$ p \to q \to r = p \uparrow^r q\$.

Note that the arrow notation cannot be treated as some kind of binary operator:

$$
\begin{align}
2 \to 3 \to 2 &amp;= 16 \\
2 \to (3 \to 2) &amp;= 512 \\
(2 \to 3) \to 2 &amp;= 64
\end{align}
$$

More examples can be found on the Wikipedia page linked above.

Task

Given a (possibly empty) list of positive integers, interpret it as Conway chained arrow notation and evaluate it into a single number.

It is OK if your program gives wrong answers for large values due to the limits (bounds and/or precision) of your language's number type, as long as the underlying algorithm is correct.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

Input =&gt; Output
[] =&gt; 1
[1] =&gt; 1
[99999999] =&gt; 99999999
[5, 5] =&gt; 3125
[4, 8] =&gt; 65536
[1, 2, 4] =&gt; 1
[2, 2, 4] =&gt; 4
[2, 3, 2] =&gt; 16
[2, 4, 2] =&gt; 65536
[4, 3, 2] =&gt; 4^256 = 1.34e154
[2, 2, 3, 2] =&gt; 4
Haskell, 75 68 63 bytes



f(q:p:x)|p^q&gt;p,x&gt;[]=f$q-1:f(q:p-1:x):x|1&lt;2=f$p^q:x
f[x]=x
f _=1


Try it online!

Takes input as a list in reversed order, since in Haskell it's easier to deal with the beginning of a list than with the end of it.

Now shorter and uglier!

Rules 3,4,5,6 are combined in the first line. The most important trick is realizing that p^q==p iff p==1||q==1 (where ^ is exponentiation and we're dealing with strictly positive numbers). We check the conditions to apply rule 6 (p and q greater than 1, at least three elements in the input) and if they are valid we do so recursively. If these conditions fail we know that either there is a 1 in the first two elements or there are just two elements in total: for both of this cases f(p^q:x) can solve the task.

The last two lines deal with inputs with less than two elements. They could be rewritten as a single line f x=last$1:x but the score would not change.



Below the original solution, no golfing tricks, just beautiful Haskell code:



f[]=1
f[p]=p
f[q,p]=p^q
f(1:x)=f x
f(_:1:x)=f x
f(q:p:x)=f$q-1:f(q:p-1:x):x


Try it online!