Factory for arbitrarily high-order operations

Grade 0: ++

This is so low that it is boring; the operation of grade 0 is incrementing or counting up, for example:

5++ -> 6
8++ -> 9

Grade 1: +

Addition is repeated incrementing:

4 + 3 -> 4++ ++ ++ -> 7
2 + 2 -> 2++ ++ -> 4

Grade 2: *

Multiplication is repeated addition:

3 * 4 -> 3 + 3 + 3 + 3 -> 12
5 * 2 -> 5 + 5 -> 10

...

I may go on but you understand that each operation of grade n + 1 is just a repetition of the operation of grade n, and that something like:

operation_of_order_100(4, 3)

is going to be unimaginably big, so big that it would be impossible to write it as a tower of exponents (exponentiation is a mere grade 3).

Even if computing an operation of order bigger than 5 is pratically impossible, I have gone through the mental exercise of writing a programme that raises the level of a given function and generates functions of a given grade, and I ask you for suggestions:

def increase_order(op):
    def increased(a, b):
        start_a = a
        for _ in range(b-1):
            a = op(a,start_a)
            #print(a)
        return a
    return increased

def add(a, b):
    return a + b

mul = increase_order(add)

assert mul(3,5) == 15
assert mul(7,3) == 21

exp = increase_order(mul)

assert exp(3,2) == 9
assert exp(7,2) == 49

tetract = increase_order(exp)

assert tetract(7,2) == 823543 # 7**7
assert tetract(4,3) == 4294967296 # 4**4**4

pentation = increase_order(tetract)

# print(pentation(4, 2)) :: Very big already

def op_of_order(order, start=add):
    for _ in range(order-1):
        start = increase_order(start)
    return start

BEAST_OPERATION = op_of_order(10**5)
# BEAST_OPERATION(2, 3) :: unimaginably big

Since this is tagged "functional-programming" I decided to take the functional approach. However, take note that Python isn't necessarily a "functional language," so it's not going to be as efficient as the iterative approach you were using. However, it looks like you're doing this from a theoretical standpoint, so you may find this interesting.

import functools

def iterate(f, x, n):
    """ Applies f n times to x. """
    if n == 0:
        return x
    else:
        return f(iterate(f, x, n - 1))

def iterate_for(f, x, n):
    """ Applies f n times to x, without recursion. """
    for _ in range(n):
        x = f(x)
    return x

def increase_order(f):
    return lambda x, n: iterate(functools.partial(f, x), x, n - 1)

def op_of_order(f, order):
    return iterate(increase_order, f, order)

def test():
    add = lambda x, y: x + y

    mul = increase_order(add)
    assert mul(3,5) == 15
    assert mul(7,3) == 21

    exp = increase_order(mul)
    assert exp(3,2) == 9
    assert exp(7,2) == 49

    tetract = op_of_order(add, 3)
    assert tetract(5,2) == 3125
    #assert tetract(7,2) == 823543
    #assert tetract(4,3) == 4294967296

if __name__ == "__main__":
    test()

The biggest change here was the abstraction of the loop you have in both increase_order and op_of_order into a function called iterate, inspired by Haskell's iterate function. I've provided both a recursive and non-recursive version for understanding and efficiency (Python has a no tail-call optimization) during testing.

In my opinion, both increase_order and op_of_order are much clearer when written this way, making it easier to see just what both functions actually do.

StackExchange Code Review Q#91335, answer score: 2