Evaluate Conway chained arrow notation

Question

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}) &= 1 \\ (p) &= p \\ p \to q &= p^q \\ X \to 1 &= X \\ X \to 1 \to p &= X \\ X \to (p+1)\to (q+1) &= 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 &= 16 \\ 2 \to (3 \to 2) &= 512 \\ (2 \to 3) \to 2 &= 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 => Output
[] => 1
[1] => 1
[99999999] => 99999999
[5, 5] => 3125
[4, 8] => 65536
[1, 2, 4] => 1
[2, 2, 4] => 4
[2, 3, 2] => 16
[2, 4, 2] => 65536
[4, 3, 2] => 4^256 = 1.34e154
[2, 2, 3, 2] => 4

Answer 1

Haskell, 75 68 63 bytes

f(q:p:x)|p^q>p,x>[]=f$q-1:f(q:p-1:x):x|1<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!

Answer 2

dc, 112 107 bytes

?[dz0r^+q]sZ[rd3Rd_3R^q]sE[ilfx1rq]sA[iSplfx1rLprq]sB[z2>Zz2=Ed1=Ard1=B1-rlfx3RSpr1-lfx_3Rri1+Lp1+r3R]dsfxp

Try it online!

Or verify all the test cases.

The input is on stdin (a line with space-separated numbers), and the output is on stdout.

---

How it works:

dc is a stack-based language. The recursive macro f does the Conway chained-arrow calculation, but the stack is treated differently from what you usually see:

1. The input to f is the entire stack when the call is made. (So f essentially takes a variable number of arguments.)

2. If the stack at the time of call is

$$a_1 \; a_2 \; \dots \; a_n$$

(with the top of the stack on the right), f will compute the value of

$$a_1 \to a_2 \to \dots \to a_n$$

and push it on top of the stack, but it leaves the arguments on the stack also.

So f turns the stack

$$a_1 \; a_2 \; \dots \; a_n$$

into

$$a_1 \; a_2 \; \dots \; a_n \; [\text{ArrowValue}(a_1 \; a_2 \; \dots \; a_n)]$$

where I've written \$\;[\text{ArrowValue}(a_1 \; a_2 \; \dots \; a_n)]\;\$ for the value of \$\;a_1 \to a_2 \to \dots \to a_n.\$

There are several auxiliary macros as well. All the usual complex control structures other languages have (loops, conditionals, functions) are implemented in dc using macros.

---

Note that dc produces a few error messages or warnings due to the golfing tricks used, but they don't interrupt program execution, and the messages are just written to stderr. Examples of these: duplicating when there's nothing on the stack, adding when there's only one item on the stack, or setting the input base to an illegal value.

The code also makes use of the fact that we can distinguish positive numbers from \$0\$ by whether the power \$0^x\$ is \$0\$ or \$1.\$

---

Here's a detailed summary of the program's operation, updated for the revised, shorter answer.

?  Read a line of space-separated numbers, written in the usual
   Conway chained-arrow order, pushing them onto the stack in turn.
   (The chained arrow sequence will start at the bottom of the stack,
   since that's pushed first, and will end at the top of the stack, since
   that's pushed last.)


        MACRO Z
Macro Z will only be called when the stack either is empty or
has just one item p on it.  We'll analyze both possibilities.
[   Start macro.
         Stack: Empty   or   p
 d    Duplicate.
         Stack: Empty   or   p p
 z    Push the size of the stack.
         Stack: 0       or   p p 2
 0    Push 0.
         Stack: 0 0     or   p p 2 0
 r
      Swap.
         Stack: 0 0     or   p p 0 2
 ^    Exponentiate.
         Stack: 1       or   p p 0
 +    Add top 2 items if they exist.
         Stack: 1       or   p p
 q    Exit this macro and the macro which called it.
]sZ End macro and name it Z.

Summary of Z:
      Turn: Empty stack
      Into: 1
and
      Turn: p
      into: p p


        MACRO E
[       Start a macro.  Assume the stack is: ... p q (top on right).
 r        Swap.                         Stack: ... q p
 d        Duplicate.                    Stack: ... q p p
 3R       Rotate left the top 3 items.  Stack: ... p p q
 d        Duplicate.                    Stack: ... p p q q
 _3R      Rotate right the top 3 items. Stack: ... p q p q
 ^        Exponentiate.                 Stack: ... p  q p**q
 q        Exit this macro and the macro which called it.
]sE     End the macro and name it E.
Summary of E:
  Turn: ... p q
  into: ... p q p**q


        MACRO A
[       Start a macro.  Assume the stack is:   ... p (top on right).
 i        Discard the top of stack.  (Actually make it the new input radix just because dc wants a place to put it.)
                                        Stack: ...
 lfx      Call f recursively.           Stack: ... ArrowValue(...)
 1        Push 1.                       Stack: ... ArrowValue(...) 1
 r        Swap.                         Stack: ... 1 ArrowValue(...)
 q        Exit this macro and the macro which called it.
]sA     End the macro and name it A.
Summary of A:
  Turn: ... p
  into: ... 1 ArrowValue(...)


        MACRO B
[       Start a macro.  Assume the stack is:    ... p q (top on right).
 i        Discard top of stack (by storing it as the input radix).
                                         Stack: ... p 
 Sp       Pop p off the stack and
          push it onto stack p.          Stack: ...
 lfx      Call f recursively.            Stack: ... ArrowValue(...)
 1        Push 1.                        Stack: ... ArrowValue(...) 1
 r        Swap.                         Stack: ... 1 ArrowValue(...)
 Lp       Pop the old value of p from stack p.
                                        Stack: ... 1 ArrowValue(...) p
 r        Swap                          Stack: ... 1 p ArrowValue(...)
 q        Exit this macro and the macro which called it.
]sB     End the macro and name it B.
Summary of B:
  Turn: ... p q
  into: ... 1 p ArrowValue(...)



        MACRO f
[       Start a macro.
 z      Push the stack size.
 2>     If the stack size was 0 or 1,
 O        then call macro Z and return from f.
          In this case, we've turned ...
                                into ... 1

                     or we've turned ... p 
                                into ... p p

 z2=E   If the stack size was 2,
          then call macro E and return from f.
          In this case, we've turned ... p q
                                into ... p q p**q

        If we get here, the stack size is at least 3.

 d1=A   If the item at the top of the stack == 1,
          then call macro A and return from f.
          In this case, we've turned ... 1
                                into ... 1 ArrowValue(...)

        If we get here, the stack size is at least 3 and the item at the top of the stack isn't 1.
                              Stack: ... p q r
          where r != 1.
 r      Swap.                 Stack: ... p r q      
 d1=B   If the item at the top of the stack == 1,
          then call macro B and return from f.
        In this case, we've turned   ... p 1 r
                              into   ... p 1 r ArrowValue(... p)

        If we get here, the stack size is at least 3, neither of the items at the top of the stack is 1,
        and we've already gone from
                              Stack: ... p q r
                           to Stack: ... p r q               
 1-     Subtract 1.           Stack: ... p r q-1
 r      Swap.                 Stack: ... p q-1 r
 lfx    Call f recursively.   Stack: ... p q-1 r [ArrowValue(... p q-1 r)]
 3R     Rotate left the top 3 items on the stack.
                              Stack: ... p r [ArrowValue(... p q-1 r)] q-1
 Sp     Pop q-1 off the stack and push it onto stack p.
                              Stack: ... p r [ArrowValue(... p q-1 r)] 
 r      Swap.                 Stack: ... p [ArrowValue(... p q-1 r)] r
 1-     Subtract 1.           Stack: ... p [ArrowValue(... p q-1 r)] r-1
 lfx    Call f recursively.   Stack: ... p  [ArrowValue(... p q-1 r)]  r-1  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]
 _3R    Rotate right the top 3 items on the stack.
                              Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  [ArrowValue(... p q-1 r)]  r-1
 r      Swap:                 Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r-1  [ArrowValue(... p q-1 r)]
 i      Discard the top item. Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r-1
 1+     Add 1                 Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r
 Lp     Load the old value of q-1 from stack p.
                              Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r  q-1
 1+     Add 1.                Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r  q
 r      Swap.                 Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  q  r
 3R     Rotate left the top 3 items on the stack.
                              Stack: ... p  q  r  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]
]       End the macro,
dsf       save it on the stack, and name it f.
Summary of f:
  Turn: ...
  into: ... ArrowValue(...)

x       Execute f.
p       Print the desired value, which is now at the top of the stack.

Answer 3

C (gcc) -m32 -lm, 159 150 137 136 bytes

f(a,b,u,t)int*a,*b;{t=a-b?b-a-1?*a-1?b-a-2?a[1]-1?t=a[1]--,a[1]=f(a,b),--*a,u=f(a,b),++*a,a[1]=t,u:f(a+2,b):pow(a[1],*a):f(a+1,b):*a:1;}

Try the test cases online! (except for [4, 3, 2], which overflows).

9 bytes off thanks to ceilingcat!

And saved 1 more byte thanks to ceilingcat too.

---

Input is taken as an array of ints in reverse order, and is passed as a pointer to the beginning and a pointer to (the location immediately after) the end.

---

The following applies to the previous version of the program. The current version uses exponentiation from the C math library. The compilation flag -m32 is now used so that the usual #include <math.h> line can be omitted.

C doesn't have exponentiation built in, so the previous version handled that by changing the 3rd and 4th rules of the recursive definition from

$$ \begin{align} p \to q &= p^q \\ X \to 1 &= X \\ \end{align} $$

to

$$ \begin{align} \quad\quad\quad\quad\quad X \to 1 &= X \\ p \to q &= (p \to q-1)*p \\ \end{align} $$

Answer 4

APL (Dyalog Unicode), 57 49 48 46 bytes

Saved 8 bytes thanks to @Bubbler!

{3>≢w←⍵↓⍨⊃⍸1≠⍵:*/⌽w⋄(∇(⊃w-1),,∘(2↓w))⍣(1⊃w)⊢1}

Try it online!

A monadic function that must be given the input in reverse. Now also requires zero-indexing. This is slightly different from Conway's definition, but I think it's equivalent. If anyone can find a more math-y proof, that'd be great.

This is how Conway described his chained arrow notation:

Our own "chained arrow" notation names some even larger numbers. In this, a^^...^^b (with c arrows) is called a->b->c.

a->b-> ... ->x->y-> 1 is another name for a->b-> ... ->x->y

and a ... x->y->(z+1) is defined to be

a ... x if y = 1,

a ... x->(a...x)->z if y = 2,

a ... x->(a...x->(a...x)->z)->z if y = 3

and so on.

No one likes ones (and \$X\to 1\$ evaluates to \$X\$), so we first remove leading ones using ⍵↓⍨⊃⍸1≠⍵. ⊃⍸1≠⍵ is the first (⊃) index where (⍸) there isn't a 1 (1≠⍵), and we drop (↓) until that index. The result of that is assigned to w to reuse.

We can replace the first rule from here with the first three rules from the question. So if w has 0, 1, or 2 elements (3>≢w), we can fold over it with exponentiation (*/⌽w), because according to APL's rules, */x is x and */⍬ (⍬ is an empty set) is 1. We do have to reverse (⌽) w again, though, because it was reversed in the first place.

The second part of the function takes care of cases when w is in the form \$X \to y \to (z+1)\$. It's essentially \$y\$ applications of the function \$\lambda a. X \to a \to z\$, starting, with 1.

If \$y\$ and \$z\$ are both 1, then this becomes \$X \to 1 \to 1\$. Next iteration, w will be just \$X\$. If only \$y\$ is 1, then it becomes \$X \to 1 \to z\$. After that, it becomes \$X \to 1 \to (z-1)\$, then \$X \to 1 \to (z-2)\$, and so on until it reaches \$X \to 1 \to 1\$, which gives us \$X\$. So this satisfies the fifth rule in the question (\$X \to 1 \to p = X\$).

If \$y\$ is greater than 1, this becomes $$ X \to (X \to (... (X \to (X \to (1) \to z) \to z) ...) \to z) \to z\\ = X \to (X \to (... (X \to (X) \to z) ...) \to z) \text{ (by question's 5th rule)} $$ The second is Conway's definition (there are \$y\$ copies of \$X\$ and \$y-1\$ copies of \$z\$). In the first, there are \$y\$ copies of both \$X\$ and \$z\$.

Answer 5

J, ^{90 79} 75 bytes

(1:`]`(^~/)`(2&}.$:@,~<:@{.,[:$:]-2=#\)@.(3<.#))`($:@}.~1+i.&1)@.(1 e.2&{.)

Try it online!

Takes input in reverse order.

I suspect there's room for more golfing yet. I may return to it tomorrow.

Answer 6

Rust, 161 bytes

fn f(s:&[u32])->u32{match
s{[]=>1,[x]=>*x,[p,q]=>p.pow(*q),[x@..,1]=>f(x),[x@..,1,_]=>f(x),[x@..,p,q]=>f(&[x,&[f(&[x,&[p-1],&[*q]].concat())],&[q-1]].concat())}}

Uses Rusts pattern matching. The last case is a little verbose, because there's no spread operator.

Try it on the rust playground.

Readable version

fn f(s: &[u32]) -> u32 {
    match s {
        []=>1,
        [x]=>*x,
        [p,q]=>p.pow(*q),
        [x@..,1]=>f(x),
        [x@..,1,_]=>f(x),
        [x@..,p,q]=>f(&[x, &[f(&[x,&[p-1,*q]].concat())], &[q-1]].concat())
    }
}

Answer 7

JavaScript (ES7),  78  77 bytes

Takes the list in reverse order.

f=([q,p,...a])=>a+a?f(--q?--p?[q,f([++q,p,...a]),...a]:a:[p,...a]):p**q||q||1

Try it online!

With BigInt support (78 bytes)

This version accepts either a list of Numbers or a list of BigInts and returns a value of the same type.

f=([q,p,...a])=>a+a?f(--q?--p?[q,f([++q,p,...a]),...a]:a:[p,...a]):p?p**q:q||1

Try it online!

Answer 8

Python 2, 117 112 111 bytes

f=lambda x:(len(x)<3)*reduce(lambda a,b:b**a,x,1)or f((1in x[:2])*x[1:]or[x[0]-1,f([x[0],x[1]-1]+x[2:])]+x[2:])

Try it online!

Takes input in reverse order.

A recursive function that takes in a list of positive integers and returns a single number.

In order to save bytes, we combine the 3 base cases into one expression:

(len(x)<3)*reduce(lambda a,b:b**a,x,1)

which returns either \$1\$, \$p\$, or \$p^q\$.

---

The recursive cases are also mashed together via:

f((1in x[:2])*x[1:]or[x[0]-1,f([x[0],x[1]-1]+x[2:])]+x[2:])

which becomes f(x[1:]) when x[0] is \$1\$ or x[1] is \$1\$, and becomes f([x[0]-1,f([x[0],x[1]-1]+x[2:])]+x[2:]) otherwise.

Answer 9

Erlang (escript), 111 bytes

Port of the Haskell answer. The last case seems to time out.

f([])->1;f([P])->P;f([1|X])->f(X);f([Q,P])->math:pow(P,Q);f([_,1|X])->f(X);f([Q,P|X])->f([Q-1,f([Q,P-1|X])|X]).

Try it online!

Answer 10

Factor, 144 bytes

:: g ( x -- y )
x llength 3 < [ x 1 [ swap ^ ] foldl ]
[ x car 1 = [ x cdr g ]
[ 1 x cadr [ x cdr cdr cons x car 1 - swons g ] times ] if
] if ;

Try it online!

Takes a linked list in reverse order. Uses the algorithm described in user's APL answer.

Using linked lists is shorter than using arrays when the code involves a lot of dissection at the start (and you don't need sophisticated sequence operations):

first (5)              > car (3)
rest (4)               > cdr (3)
second (6) > 1 nth (5) > cadr (4)
prefix (6)             > cons (4)
swap prefix (11)       > swons (5)
unclip (6)             = uncons (6)
unclip swap (11)       > unswons (7)

How it works

:: g ( x -- y )         ! Takes a list `x` and returns a number
  x llength 3 < [         ! If x has 2 or fewer numbers...
    x 1 [ swap ^ ] foldl    ! Reduce by ^ on reversed arguments
  ] [                     ! Otherwise `x` is in the form of `X->y->z`
    x car 1 = [           ! If z is 1...
      x cdr g               ! Remove z(=1) and recurse
    ] [                   ! Otherwise...
      1                     ! Setup the initial value of 1
      x cadr                ! Setup the loop count of y
      [ x cdr cdr cons      ! Build y':X
        x car 1 - swons g ] ! Build z-1:y':X
      times                 ! Iterate the above function y times to 1
    ] if
  ] if

Answer 11

05AB1E, 68 66 bytes

"D©g2‹iPë`i)Y.Vëi)Y.Vë)\®`®g<imëX®šUs<s)Y.VXćsUDgÍsŠǝRć<šRY.V"DV.V

This was pretty hard in a stack-based language..

Try it online or verify all test cases.

Explanation:

"                          "# Start a string we can execute as 05AB1E code
                            # to mimic recursive calls:
 D                          # Duplicate the list at the top of the stack
                            # (which will be the (implicit) input at the start)
  ©                         # Store it in variable `®` (without popping)
   g2‹i                     # Pop one, and if its length is smaller than 2:
       P                    #  Take the product
                            #  ([] → 1; [p] → p)
   ë                        # Else (the length is >= 2):
    `                       #  Dump the contents of the list onto the stack
     i                      #  Pop the top value, and if it's a 1:
      )                     #   Wrap the remaining values into a list
       Y.V                  #   And do a recursive call
                            #   (p=1 for [...,q,p] → recursive call to [...,q])
     ë                      #  Else:
      i                     #   Pop the second top value, and if it's a 1:
       )                    #    Wrap the remaining values into a list
        Y.V                 #    And do a recursive call
                            #    (q=1 for [...,q,p] → recursive call to [...])
      ë                     #   Else:
       )\                   #    Discard everything on the stack
         ®`                 #    Dump the contents of `®` onto the stack again
           ®g<i             #    If the length of `®` is 2:
               m            #     Take the power of the two values
                            #     ([p,q] → p^q)
              ë             #    Else (the length is >= 3):
               X®šU         #     Prepend `®` to list `X`
                            #     (`X` is 1 by default, but that doesn't matter;
                            #      it'll become [[...,p,q],1] and the 1 is ignored)
               s<s)         #     Decrease the second value from the top by 1
                   Y.V      #     And do a recursive call
                            #     ([...,p,q] → recursive call to [...,p-1,q],
                            #      let's call its result `R` for the moment)
               Xć           #     Extract the first list from variable `X` again,
                 sU         #     and pop and store the remaining values as new `X`
                 DgÍ        #     Take its length - 2 (without popping by duplicating first)
                            #     (let's call this length-2 `I` for the moment)
                    sŠ      #     Swap & triple-swap ([...,R,[...,p,q],I] → [...,[...,p,q],R,I])
                      ǝ     #     Insert value `R` into the list at (0-based) index `I`
                            #     ([...,[...,p,q]] → [...,[...,R,q]])
                 Rć<šR      #     And decrease the last value in the top list by 1
                            #     ([...,[...,R,q]] → [...,[...,R,q-1]])
                       Y.V  #     And do a recursive call again
"                          "# End the string of 05AB1E code
 DV                         # Store a copy of this string in variable `Y`
   .V                       # Execute it as 05AB1E code (`Y.V` is how we can do recursive calls)
                            # (after which the result is output implicitly)

Answer 12

Pyth, 40 38 bytes

L?tJtby?}1<b2J+,thby+,hbthJtJttb|^F_b1

Try it online!

Takes input in reverse order.

L defines a recursive function named y that takes in a list b of positive integers and returns a single number.

Similarly to my Python answer, the base cases are combined into one expression:

|^F_b1

in which ^F_b folds the exponentiation function ^ over b in reverse. If b has 2 elements \$(q,p)\$ this will return \$p^q\$, if b has 1 element \$(p)\$ it will return \$p\$, and if b is empty it will return 0 (| .. 1 turns the 0 into 1, as needed)

---

The recursive cases are handled by:

y?}1<b2J+,thby+,hbthJtJttb

This part is a pretty straightforward translation of the recursive rules. If either of the first two elements of b are 1 it calls y on tb (equivalent to b[1:] in Python)*. Otherwise, the formula \$X \to (X \to p\to (q+1))\to q\$ is passed recusively to y.

*The rule \$X \to 1 \to p = X\$ thus takes two steps instead of one, but doing it this way saves a few bytes.

Answer 13

Java, 282 chars

interface c{int n[]=new int[99];static void main(String[]a){int i=0,j=a.length;for(;i<j;)n[i]=new Integer(a[i++]);System.out.print(j<1?1:j<2?n[0]:c(j));}static int c(int j){j-=n[j-2]<2?2:n[j-1]<2?1:0;if(j<3)return(int)Math.pow(n[0],n[1]);n[j-2]--;n[j-2]=c(j);n[j-1]--;return c(j);}}

Readable version:

interface c{
    int n[]=new int[99];
    static void main(String[]a){
        int i=0,j=a.length;for(;i<j;)n[i]=new Integer(a[i++]);
        System.out.print(j<1?1:j<2?n[0]:c(j));
    }
    static int c(int j){
        j-=n[j-2]<2?2:n[j-1]<2?1:0;
        if(j<3)return(int)Math.pow(n[0],n[1]);
        n[j-2]--;
        n[j-2]=c(j);
        n[j-1]--;
        return c(j);
    }
}

Answer 14

Clojure, 117 bytes

(defn f([]1)([q]q)([q p](Math/pow p q))([q p & x](if(== p(f q p))(apply f p x)(apply f(dec q)(apply f q(dec p)x)x))))

Try it online!

Handles all test cases, takes input arguments in reverse order.

Answer 15

Wolfram Language (Mathematica), 67 66 bytes

f[x__,1,_:0]=f@x
f[x___,p_:1,q_:1]=If[x<1,p^q,f[x,f[x,p-1,q],q-1]]

Try it online!

Answer 16

Scala, 156 141 bytes

val f:Seq[Int]=>Int={case x if x.size<3=>(x:\1.0)(math.pow(_,_))toInt
case 1::x=>f(x)case p::1::x=>f(x)case q::p::x=>f(q-1::f(q::p-1::x)::x)}

Try it in Scastie

Note: Input must be a reversed List. If it's not reversed, the algorithm won't work correctly, and if it's not a List, there'll be a MatchError.

I hate that math.pow(_,_) works but just math.pow would need the first argument to be a Double.