Who Knew: Higher-Order Functions Are Useful!

A higher-order function is a function that takes a function as its input, returns a function as its output, or both. I’ve been aware for a while that higher-order functions exist and seen some examples in tutorials of how they work, but it wasn’t until I started exploring number sequences in Python that it became clear how useful higher-order functions could be.

Exploring Happy Number Sequences

Here’s the situation that precipitated my epiphany. I had written a few functions to explore happy numbers, and was starting to think about exploring other similar number sequences. Here’s the code I had:

def digits(n, base=10):
    if n == 0:
        return []
    else:
        quotient, remainder = divmod(n, base)
        return [remainder] + digits(quotient, base)

def happy_step(n, base=10):
    d = digits(n, base)
    return sum([x ** 2 for x in d])

def happy_sequence(n, base=10, max=10_000):
    seq = [n]
    while len(seq) < max:
        n = happy_step(n, base)
        if n in seq:
            return seq
        seq.append(n)
    raise OverflowError('maximum sequence length exceed')

def is_happy(n, base=10):
    seq = happy_sequence(n, base)
    return seq[-1] == 1

def happy_head_cycle(n, base=10):
    seq = happy_sequence(n, base)
    cycle_start_val = happy_step(seq[-1])
    cycle_index = seq.index(cycle_start_val)
    head = seq[:cycle_index]
    cycle = seq[cycle_index:]
    return head, cycle

digits takes a number and a base and returns a list of the digits of the number in that base (in reversed order). For example, digits(n=137, base=10) returns the digits [7, 3, 1], representing the 1s, 10s and 100s digits in decimal; digits(n=35, base=2) returns the digits [1, 1, 0, 0, 1], representing 1x1, 1x2, 0x4, 0x8, and 1x16.

happy_step returns takes a number, splits it up into its component digits in the given base, squares each digit, adds those squares together, and returns that value. happy_sequence repeats happy_step over and over, keeping track of the numbers it’s seen until it comes across a repeated number, and then returns the list of all the numbers it has come across. is_happy returns True if a given number is happy and False if it isn’t (a number is happy if its sequence ends with 1, and it’s not happy if its sequence ends up in a loop that doesn’t involve 1). happy_head_cycle looks at a number’s sequence and splits it into two lists, the second (the “cycle”) representing the loop that the sequence repeats, and the first (the “head”) representing all the numbers in the sequence before the loop was reached.

For example, happy_step(7) returns 49 (7^2 = 49), and happy_step(49) returns 97 (4^2 + 9^2 = 16 + 81 = 97). happy_sequence(7) returns [7, 49, 97, 130, 10, 1], and is_happy(7) returns True because the last number in 7’s happy sequence is a 1. happy_head_cycle(7) returns ([7, 49, 97, 130, 10], [1]): [1] is the cycle (happy_step(1) -> 1), and [7, 49, 97, 130, 10] are all the digits that led to 1.

Exploring Other Number Sequences - The Naïve Approach

This is all well and good. But what if I want to look at a different sequence - cubing all the digits, say, instead of squaring them. One approach is to copy and paste the code I already have, renaming functions as necessary:

def trappy_step(n, base=10):
    d = digits(n, base)
    return sum([x ** 3 for x in d])

def trappy_sequence(n, base=10, max=10_000):
    seq = [n]
    while len(seq) < max:
        n = trappy_step(n, base) # <---
        if n in seq:
            return seq
        seq.append(n)
    raise OverflowError('maximum sequence length exceed')

def is_trappy(n, base=10):
    seq = trappy_sequence(n, base) # <---
    return seq[-1] == 1

…and so on. But compare is_trappy with is_happy: the only difference between the two functions is that I’ve called trappy_sequence instead of happy_sequence (marked with an arrow). This situation of redundancy is even worse for trappy_sequence and happy_sequence: both are eight lines of code, but only difference is in the fourth line, where trappy_step substitutes for happy_step. That’s a lot of repeated code - if I wanted to compare several different ways to generate sequences, it would be tedious to write up all the necessary functions, and heaven help me if I decided I needed to go back and do some refactoring. There must be a better way!

A Better Way: Enter Higher-Order Functions

Any sequence function I want to use (e.g. happy_sequence, trappy_sequence, and so on) will have a similar form: start a list of numbers we’ve seen, use a step function to generate the next number in the sequence, check whether we’ve encountered a loop, and return the sequence if we have. The only detail that differs between these different flavours of sequence function is the way we step from one item in the sequence to the next. The solution, then, is to create a higher-order function that takes in a step function and spits out a new function that generates sequences based on that step function.

For example, I can define a “sequence maker” function that takes a step function as its argument. I define a new function inside the sequence maker, plugging in the appropriate step function (marked with an arrow), and then return the inner function I just created:

def sequence_maker(step_function):
    def sequence_function(n, base=10, max=10_000):
        seq = [n]
        while len(seq) < max:
            n = step_function(n, base) # <---
            if n in seq:
                return seq
            seq.append(n)
        raise OverflowError("maximum sequence length exceeded")
    return sequence_function

Now all I need to do is define my step function, plug it into sequence_maker, and save the returned function to happy_sequence:

def happy_step(n, base=10):
    d = digits(n, base)
    return sum([x ** 2 for x in d])
happy_sequence = sequence_maker(happy_step)

And if I want to create a function for generating a new kind of sequence, all I need to do is provide a new step function:

def trappy_step(n, base=10):
    d = digits(n, base)
    return sum([x ** 3 for x in d])
trappy_sequence = sequence_maker(trappy_step)

Now let’s put the whole thing together, creating higher-order functions to generate sequence functions, is functions, and head-cycle functions, and then use them to create functions to explore happy numbers and trappy numbers:

def digits(n, base=10):
    if n == 0:
        return []
    else:
        quotient, remainder = divmod(n, base)
        return [remainder] + digits(quotient, base)


##############################
# the higher-order functions #
##############################

def sequence_maker(step_function):
    def sequence_function(n, base=10, max=10_000):
        seq = [n]
        while len(seq) < max:
            n = step_function(n, base)
            if n in seq:
                return seq
            seq.append(n)
        raise OverflowError("maximum sequence length exceeded")
    return sequence_function

def is_maker(sequence_function):
    def is_function(n, base=10):
        seq = sequence_function(n, base)
        return seq[-1] == 1
    return is_function

def head_cycle_maker(step_function, sequence_function):
    def head_cycle_function(n, base=10):
        seq = sequence_function(n, base)
        cycle_start_val = step_function(seq[-1])
        cycle_index = seq.index(cycle_start_val)
        head = seq[:cycle_index]
        cycle = seq[cycle_index:]
        return head, cycle
    return head_cycle_function


###################################
# creating happy number functions #
###################################

def happy_step(n, base=10):
    d = digits(n, base)
    return sum([x ** 2 for x in d])

happy_sequence = sequence_maker(happy_step)
is_happy = is_maker(happy_sequence)
happy_head_cycle = head_cycle_maker(happy_step, happy_sequence)


####################################
# creating trappy number functions #
####################################

def trappy_step(n, base=10):
    d = digits(n, base)
    return sum([x ** 3 for x in d])

trappy_sequence = sequence_maker(trappy_step)
is_trappy = is_maker(trappy_sequence)
trappy_head_cycle = head_cycle_maker(trappy_step, trappy_sequence)