A double search function that looks in a list for one value and then the other alternatively

Question

I'm writing in Python (3.4) a double search function that looks in a list for one value and then the other alternatively. That is, start searching the second value once you find first the first value (and start searching from where you found the first value) and vice-versa.

My first approach was to write a recursive function to do it, only to find out they don't end up as neat in Python as they do in Haskell. This is a basic sketch of the function:

def double_search(input_list, first_condition, second_condition, condition_to_search, output_list):
    if input_list == []:
        return output_list
    else:
        if condition_to_search == 1:
            if input_list[0] == first_condition:
                return output_list + double_search(input_list[1:], first_condition, second_condition, 2, output_list + ['First'])
            else:
                return output_list + double_search(input_list[1:], first_condition, second_condition, 1, output_list + ['None'])
        if condition_to_search == 2:
            if input_list[0] == second_condition:
                return output_list + double_search(input_list[1:], first_condition, second_condition, 1, output_list + ['Second'])
            else:
                return output_list + double_search(input_list[1:], first_condition, second_condition, 2, output_list + ['None'])

I have several problems with the way it turned out, looks forced and ugly in Python. And produces different outputs in Python interpreter and pydev debugger!

Pydev debugger gives the proper result while in the interpreter I have to take the tail of the result:

result[-len(input_list):]

To get a list of the appropriate length, which I find unacceptable because I have no clue where the garbage in front comes from.

Would appreciate any suggestion to improve this code, make it more pythonic and easier to maintain as well as any performance improvements you can suggest.

EDIT: As per request, the following is an example of the function in use with some sample data.

example_list = [5,4,1,2,0,3,1,3,4,2,5,0]
double_search(example_list, 1, 3, 1, [])

Should result in: ['None', 'None', 'First', 'None', 'None', 'Second', 'First', 'Second', 'None', 'None', 'None', 'None']

While:

double_search(example_list, 1, 5, 1, [])

Results in: ['None', 'None', 'First', 'None', 'None', 'None', 'None', 'None', 'None', 'None', 'Second', 'None']

Notice how in the second case only matches the second to last '5', because it needs to find first a '1'.

Answer 1

Python has this wonderful module called itertools. Whenever you need to iterate over some data in a specific way, check if there isn't a function or recipe that could help you.

For this problem, I’m thinking about itertools.cycle: being an iterator, you can easily call next on it whenever you need to grab the "other" value. e.g.:

input_list = [1, 2, 3, 2, 4, 2, 3]
values = itertools.cycle(('First', 'Second'))
for element input_list:
    if element == 2:
        print(next(values))
    else:
        print('None')

will print:

None
First
None
Second
None
First
None

So you can easily compare elements to the current condition.

The only thing missing, then, is associating the value to store in the output list to the condition to check. You have two choices: either you use zip with a second itertools.cycle, or you use a single itertools.cycle but you define it with a couple of couples like so: itertools.cycle(((cond1, 'First'), (cond2, 'Second'))). I’ll go with the former as I feel it is cleaner, but both are equally valid:

import itertools

def double_search(iterable, condition1, condition2):
    output = []
    conditions = itertools.cycle((condition1, condition2))
    results = itertools.cycle(('First', 'Second'))
    iterator = zip(conditions, results)

    # Initialize the current value to search for
    condition, value = next(iterator)

    for element in iterable:
        if element == condition:
            output.append(value)
            condition, value = next(iterator)
        else:
            output.append('None')
    return output

It is however considered bad practice to use the pattern empty list + append in a loop. But the use of next makes it hard to use a list-comprehension instead.

You can, however, turn your function into a generator instead

import itertools

def double_search(iterable, condition1, condition2):
    conditions = itertools.cycle((condition1, condition2))
    results = itertools.cycle(('First', 'Second'))
    iterator = zip(conditions, results)

    # Initialize the current value to search for
    condition, value = next(iterator)

    for element in iterable:
        if element == condition:
            yield value
            condition, value = next(iterator)
        else:
            yield 'None'

and call it like:

input_list = list(range(5))
result = list(double_search(input_list, 2, 3))

Answer 2

Unlike Haskell, taking heads and tails of lists is neither idiomatic nor efficient in Python. That is one of the reasons why recursion is generally avoided in Python. (Python also lacks tail recursion or laziness, which are two more reasons to avoid recursion.)

That said, a correct recursive solution is possible (as an academic exercise). Your solution was indeed buggy, though. You used output_list as an accumulator for the result. If you do that, then you should not also return output_list + double_search(…).

def double_search(input_list, first_condition, second_condition, condition_to_search, output_list):
    if input_list == []:
        return output_list
    elif condition_to_search == 1:
        if input_list[0] == first_condition:
            return double_search(input_list[1:], first_condition, second_condition, 2, output_list + ['First'])
        else:
            return double_search(input_list[1:], first_condition, second_condition, 1, output_list + ['None'])
    elif condition_to_search == 2:
        if input_list[0] == second_condition:
            return double_search(input_list[1:], first_condition, second_condition, 1, output_list + ['Second'])
        else:
            return double_search(input_list[1:], first_condition, second_condition, 2, output_list + ['None'])

It would be nice not to have to pass 1 and [] as the fourth and fifth parameters.

def double_search(input_list, condition, other_condition, result_name='First'):
    if input_list == []:
        return []
    elif input_list[0] == condition:
        other_result_name = 'Second' if result_name == 'First' else 'First'
        return [result_name] + double_search(input_list[1:], other_condition, condition, other_result_name)
    else:
        return ['None'] + double_search(input_list[1:], condition, other_condition, result_name)

But in any case, iteration is the way to go in Python, and @Mathias has a nice solution using itertools.cycle().