Comment by Joker_vD

Just use Scott-Mogensen encoding, seriously.

    Zero = z. s. z
    Succ = n. z. s. s n

    isZero = n. n True (_. False)
    pred   = n. n Zero (r. r)

Addition requires explicit recursion, however (since numbers aren't folds), so I guess you'll have to either use Y combinator or closure-convert manually:

    add' = add'. m. n. m n (r. Succ (add' add' r n))
    add = add' add'

In any case, arithmetic operations can't be made fully constant-time for obvious reasons so whether your prefer this to Church numerals is a matter of taste. However, for lists/tuples the ability to execute head/tail/cons in constant time is much more important in practice than being able to do append in constant time.