# Recursive higher-order function

I have implemented a through function for myself in a project. Since I am still quite new in python and want to learn it correctly, I would be happy about any feedback including style, variable naming...

A first question is how to name the function. Because of Mathematica's documentation I called it through. Is there a more intuitive name?

def through(list_of_functions, value, recurse_level=np.infty):
"""Calls each function in a list

This function is passing the value as argument to each function
in a list.
For a one dimensional list consisting of
only functions it is equivalent to::

[f(value) for f in list]

If an element is not callable and not iterable, it is not called.
An iterable is either directly appended or will be recursed through
depending on recurse_level.

Args:
list_of_functions (list):
value (any type):
recurse_level (int):

Returns:
list:
"""
new_list = []
for possible_function in list_of_functions:
try:
new_list.append(possible_function(value))
except TypeError: # item not callable; could be iterable
# If it is iterable and recurse_level is not negative
# recurse through elements
if recurse_level >= 0:
try:
new_list.append(through(possible_function,
value,
recurse_level))
recurse_level = recurse_level - 1
except TypeError: # not an iterable; append without calling
new_list.append(possible_function)
else:
new_list.append(possible_function)
return new_list


An example:

In: test = [[1, 2], [3, (lambda x : x ** 2)], (lambda x : x ** 3)]
In: through(test, 4, recurse_level=1)
Out: [[1, 2], [3, 16], 64]
In: through(test, 4, recurse_level=0)
Out: [[1, 2], [3, <function __main__.<lambda>>], 64]


You have some bugs.

• Mutation of recurse_level: Since you reassign recurse_level = recurse_level - 1, you get this weird behaviour:

>>> through([[id], [id], [id], [id]], 'blah', recurse_level=2)
[, , , [<built-in function id>]]

• Catching TypeError: You catch TypeError here:

try:
new_list.append(possible_function(value))
except TypeError: # item not callable; could be iterable
…


You are expecting that type TypeError might be thrown if possible_function is not callable. But the exception handler could also be triggered by an exception within possible_function when it is being executed. To be more precise, you should check for callable(possible_function) instead of catching TypeError.

Similarly, your other except TypeError should be a check for the existence of possible_function.__iter__.

## Suggested solution

In the spirit of functional programming, you should write the code without .append() or other mutations.

Also note that using NumPy just for its infinity is overkill.

def through(functions, value, recurse_level=float('inf')):
if callable(functions):
return functions(value)
elif recurse_level < 0 or not hasattr(functions, '__iter__'):
return functions
else:
return [through(f, value, recurse_level - 1) for f in functions]

• Thank you for the great answer! Is it even overkill, If I import it anyway? I like np.infty a bit more to read than float('inf'). Nov 21 '16 at 11:58
• If you are already using NumPy then it's fine. Nov 21 '16 at 15:53
• Perhaps you could add or isinstance(functions, str)  in your answer/code. I forgot about it in my function definition, which was a bug in my case and I think that most people intuitively would treat strings not as iterables in this context. Nov 23 '16 at 15:10

# Naming

• In Clojure, there's a similar function named juxt. Not saying that's a better name by any means, just mentioning what it happens to be called in one other place. Upon further reflection, what you are doing is really just a recursive form of function application. So a suitable name might reflect that. Perhaps apply_rec?
• Use the shortest name that conveys sufficient meaning. For example, list_of_functions could be shortened to functions (or even just fs). possible_function could be shortened to f. (Single-character names are not good names in general, but for generic entities that have a well-known mathematical notation, they are a good fit.)

# Use Better Checks for Callable / Iterable

You check if something's callable by trying to call it and catching a TypeError exception. However, if you call a function, and that function happens to through a TypeError, then your code will incorrectly assume it's not a function. You can use the callable function instead, to determine whether or not something is callable.

A similar situation exists in the way you check for iterables. In this case, you can use the iter function as a fail-fast way to check if something's iterable.

# Consider Using a List Comprehension

Reading your code, I thought it was a bit ironic that you used a list comprehension in the docstring to describe the functions behavior, but not in the code itself. Granted, due to the recursive nature, it's not quite as straight-forward. But with just a little refactoring, it should be possible. Here's how I would do it:

def apply_rec(f, x):
"""
If f is a function, applies f to x and returns the result.
Otherwise, if f is iterable, applies every element in f to x,
returning a list of the results.
If f is neither callable nor iterable, returns f.
"""

if callable(f):
return f(x)
else:
try:
fs = iter(f)
except:
# Not iterable => return f
return f

return [apply_rec(f, x) for f in fs]


I've omitted the recursion limit, but that should be trivial to add.

• Thank you for the great answer! If I could I would accept both Nov 21 '16 at 12:00