CODEWITHSUNDEEP
pythonloopsrecursionfunctional-programming
TheRimalaya
TheRimalaya

Reputation: 4592

Functional way to convert a loop that is based on intermediate value that updates on each loop in python

My title might not be very direct, but basically, I want to change the following code written using for loop into a recursive function.

import numpy as np
irrel_pos = range(3, 11)
n_extra_pos = [2, 3]
extra_pos = []
rs = np.random.RandomState(1)
for i in range(len(n_extra_pos)):
    sample_i = rs.choice(list(irrel_pos), n_extra_pos[i], replace=False)
    extra_pos.append(set(sample_i))
    irrel_pos = set(irrel_pos) - set(extra_pos[i])

print(irrel_pos)
print(extra_pos)

Output:

{8, 9, 3}
[{10, 5}, {4, 6, 7}]

Here is the code with two sample items from irrel_pos in the first loop and three items in the second loop, but the items sampled in the first loop need to be removed before going to the second loop.

I am trying to understand functional approach to this problem, how can I convert this to a recursive function?

Upvotes: 2

Views: 109

Answers (1)

JohanL
JohanL

Reputation: 6891

Not dwelling on why you want to do this, there are at least two different approaches to this. It very much depends on whether you want the call to be a tail call (which allows for the compiler to optimize away the function call in many strict functional languages - though not Python) or if you want a more straight forward recursive function.

The straight forward implementation is

import numpy as np

def recursive(rs, n_extra_pos, irrel_pos):
    if n_extra_pos == []:
        return [], irrel_pos
    extra_pos, irrel_pos = recursive(rs, n_extra_pos[:-1], irrel_pos)
    sample = set(rs.choice(list(irrel_pos), n_extra_pos[-1], replace=False))
    return extra_pos + [sample], irrel_pos - sample

irrel_pos = set(range(3, 11))
n_extra_pos = [2, 3]
rs = np.random.RandomState(1)
extra_pos, irrel_pos = recursive(rs, n_extra_pos, irrel_pos)
print(extra_pos, irrel_pos)

In this implementation, first we call ourself recursively until all elements of n_extra_pos have been consumed, then while returning through the call stack, we do the needed calculations and update the result. As can be seen, the recursive call is not the last thing happening here, and therefore TCO (tail call optimization) is not possible.

To make a function that allows TCO, we need to use accumulators and instead of first reaching the bottom of the call stack, we will do the calculations on the way down, so to say, and while doing that, we will add the results to our accumulators (extra_pos and irrel_pos). Then, when reaching the bottom, all we have to do, is to return the accumulators. An implementation of this is

import numpy as np

def tail_recursive(rs, n_extra_pos, extra_pos, irrel_pos):
    if n_extra_pos == []:
        return extra_pos, irrel_pos
    sample = set(rs.choice(list(irrel_pos), n_extra_pos[0], replace=False))
    return tail_recursive(rs, n_extra_pos[1:], 
                          extra_pos + [sample], irrel_pos - sample)

irrel_pos = set(range(3, 11))
n_extra_pos = [2, 3]
rs = np.random.RandomState(1)
extra_pos, irrel_pos = tail_recursive(rs, n_extra_pos, [], irrel_pos)
print(extra_pos, irrel_pos)

But, as stated, TCO is not available in Python, which makes recursive functions less useful and thereby makes Python less of an optimal choice for functional programming, other than using the built-in map, reduce (available in functools) and filter functions, and, of course, list comprehensions.

Upvotes: 4

Related Questions