knuth.py

def up(a, b, n):
    """Calculates a ↑ⁿ b"""
    if a == 1:
        return 1
    elif b == 1:
        return a
    elif n == 1:
        return a**b
    else:
        return up(a, up(a, b - 1, n), n - 1)

up 1 _ _ = 1
up a 1 _ = a
up a b 1 = a^b
up a b n = up a (up a (b-1) n) (n-1)

Memoized version, using the data-memocombinators package

import qualified Data.MemoCombinators as Memo

up = Memo.integral up'
      where up' 1 _ _ = 1
            up' a 1 _ = a
            up' a b 1 = a ^ b
            up' a b n = up a (up a (b-1) n) (n-1)