Function returning higher order function

Question

For the below given exercise:

Define a function cycle which takes in three functions as arguments: f1, f2, f3. cycle will then return another function. The returned fuction should take in an integer argument n and do the following:

return a function that takes in an argument x and does the following:

if n is 0, just return x

if n is 1, apply the first function that is passed to cycle to x

if n is 2, the first function passed to cycle is applied to x, and then the second function passed to cycle is applied to the result of that (i.e. f2(f1(x))).

If n is 3, apply the first, then the second, then the third function (i.e. f3(f2(f1(x))))

if n is 4, apply the first, then the second, then the third, then the first function (i.e. f1(f3(f2(f1(x)))))

And so forth

Hint: most of the work goes inside the most nested function.

def cycle(f1, f2, f3):
 """ Returns a function that is itself a higher order function 
 >>> add1 = lambda x: x+1 
 >>> times2 = lambda x: 2*x 
 >>> add3 = lambda x: x+3 
 >>> my_cycle = cycle(add1, times2, add3)
 >>> identity = my_cycle(0)
 >>> identity(5)
 5
 >>> add_one_then_double = my_cycle(2)
 >>> add_one_then_double(1) # semanitcally the same as times2(add1(1))
 4
 >>> do_all_functions = my_cycle(3)
 >>> do_all_functions(2) # semantically the same as add3(times2(add1(2)))
 9
 >>> do_more_than_a_cycle = my_cycle(4)
 >>> do_more_than_a_cycle(2) # semantically the same as add1(add3(times2(add1(2))))
 10
 >>> do_two_cycles = my_cycle(6) # semantically the same as add3(times2(add1(add3(times2(add1(1))))))
 >>> do_two_cycles(1)
 19
 """
 " *** YOUR CODE HERE *** "

Here is the solution:

def cycle(f1, f2, f3):
 """ Returns a function that is itself a higher order function 
 >>> add1 = lambda x: x+1 
 >>> times2 = lambda x: 2*x 
 >>> add3 = lambda x: x+3 
 >>> my_cycle = cycle(add1, times2, add3)
 >>> identity = my_cycle(0)
 >>> identity(5)
 5
 >>> add_one_then_double = my_cycle(2)
 >>> add_one_then_double(1) # semanitcally the same as times2(add1(1))
 4
 >>> do_all_functions = my_cycle(3)
 >>> do_all_functions(2) # semantically the same as add3(times2(add1(2)))
 9
 >>> do_more_than_a_cycle = my_cycle(4)
 >>> do_more_than_a_cycle(2) # semantically the same as add1(add3(times2(add1(2))))
 10
 >>> do_two_cycles = my_cycle(6) # semantically the same as add3(times2(add1(add3(times2(add1(1))))))
 >>> do_two_cycles(1)
 19
 """
 def f(n):
 tple = (f1, f2, f3)
 def g(x, count = n):
 if count == 0:
 return x
 else:
 return g(tple[(n-count)%3](x), count-1)
 return g
 return f

My question:

1. The above solution is written in the functional paradigm. Please let me know if the code style breaks the functional paradigm.

2. Can the code be optimized without default valued second parameter of function g and tuple tple?

Note: In python, I do not like lambda and decorators

• jonrsharpe: "let me know if the code style breaks the functional paradigm" - are you still not getting this answer, or the various subsequent discussions? Does that rule of thumb hold?
• overexchange: @yes I did not. Please read the comment.

Answer 1

That's a pretty good solution to a tricky exercise. I recommend two simplifications:

• The definition of tple can be lifted out of f into cycle itself, as it never changes.
• The code would be simpler if you count up instead of down.

def cycle(f1, f2, f3):
 tple = (f1, f2, f3)
 def f(n):
 def g(x, count = 0):
 if count == n:
 return x
 else:
 return g(tple[count % 3](x), count + 1)
 return g
 return f

As you observed, your g function is a leaky abstraction: it is supposed to take just an x argument, but it's possible to interfere with its proper behaviour by also passing it a count. Here is one solution that avoids that problem ("apply f1, then move f1 to the end of the queue").

def cycle(f1, f2, f3):
 def f(n):
 def g(x):
 if n == 0:
 return x
 else:
 return cycle(f2, f3, f1)(n - 1)(f1(x))
 return g
 return f

• overexchange: When you say abstraction, is it functional abstraction or data abstraction?
• 200_success: Don't get hung up on the terminology. The basic idea is, you shouldn't be able to mess things up like that.
• overexchange: Lecture 7 & 8 of cs61A fall 2012 talks about these two types of abstractions.amtrying to understand these concepts with such examples.
• Veedrac: Your fix for the "leaky abstraction", if needed at all, would be nicer by just returning a partially applied g.

Answer 2

tple really irks me as a name. Try tuple_ or tup instead. Better would be to name it by its meaning (eg. functions). You also don't need brackets.

You might rephrase this problem as a reduction on an iterable of functions. This would mean something like

reduce(apply_function, [f1, f2, f3, f1, f2, f3, f1, f2, f3, ...])

apply_function is

def apply_function(value, function):
 return function(value)

and you can get the repeating iterable of functions with

from itertools import cycle as icycle, islice
islice(icycle(functions), n)

This gives just

from functools import reduce
from itertools import cycle as icycle, islice
def apply_function(value, function):
 return function(value)
def cycle(f1, f2, f3):
 functions = f1, f2, f3
 def f(n):
 def g(x):
 return reduce(apply_function, islice(icycle(functions), n), x)
 return g
 return f

We can improve this by replacing functions = f1, f2, f3 with just taking variadic arguments:

def cycle(*functions):
 def f(n):
 def g(x):
 return reduce(apply_function, islice(icycle(functions), n), initial=x)
 return g
 return f

One trick for dealing with heavy nesting is to use lambda. This should only be used when you really can't add meaningful names to the inner functions, but it probably helps here:

def cycle(*functions):
 return (lambda n: lambda x:
 reduce(apply_function, islice(icycle(functions), n), x))

Alternatively, but probably more confusingly, you can use partial

from functools import partial
def cycle(*functions):
 return (lambda n:
 partial(reduce, apply_function, islice(icycle(functions), n)))

However, it does make sense to extract the innermost reduction into a new function for readability:

def apply_functions(functions, n, x):
 return reduce(apply_function, islice(icycle(functions), n), x)
def cycle(*functions):
 return lambda n: lambda x: apply_functions(functions, n, x)

The partial form would be

def cycle(*functions):
 return partial(partial, apply_functions, functions)

Short... but cryptic.

Overall this is

from functools import reduce
from itertools import cycle as icycle, islice
def apply_function(value, function):
 return function(value)
# Use better names than n and x here
def apply_functions(functions, n, x):
 return reduce(apply_function, islice(icycle(functions), n), x)
def cycle(*functions):
 return lambda n: lambda x: apply_functions(functions, n, x)

• Veedrac: flip (flip . flip ((.) . foldl (flip id)) . take) . cycle