1
\$\begingroup\$

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'.

\$\endgroup\$
4
  • \$\begingroup\$ Could you provide an example of how the function is used? \$\endgroup\$ – 200_success Sep 29 '16 at 19:02
  • \$\begingroup\$ Thanks for the suggestion @200_success, added a couple of examples that should help clarify its behaviour. \$\endgroup\$ – pa7x1 Sep 29 '16 at 19:57
  • \$\begingroup\$ The actual output does not match the expected output, which means that the code is not working correctly as intended, and therefore not ready to be reviewed. \$\endgroup\$ – 200_success Sep 29 '16 at 20:09
  • \$\begingroup\$ The issues is described in the post. It does match using pydev debugger but not Python interpreter, which I find very surprising. But there is a trivial fix to make it work also in Python interpreter (also described in the post), take the tail of the output as [-len(input_list):]. This produces the output described. The fact that it works in some interpreters but not others looks very suspicious to me and I can't explain it but makes it worth reviewing IMHO. \$\endgroup\$ – pa7x1 Sep 29 '16 at 20:14
4
\$\begingroup\$

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))
\$\endgroup\$
7
  • \$\begingroup\$ Thanks a lot. My bad for the lack of clarity, should have provided the use case up front. Was working in understanding your solution and adapting it to the desired output. Will be looking for your update in any case. \$\endgroup\$ – pa7x1 Sep 29 '16 at 20:16
  • \$\begingroup\$ @pa7x1 There you go \$\endgroup\$ – 301_Moved_Permanently Sep 29 '16 at 20:23
  • 1
    \$\begingroup\$ This is perfect! Much more clear and simpler, elegant solution. Much appreciated :) \$\endgroup\$ – pa7x1 Sep 29 '16 at 20:36
  • \$\begingroup\$ The zip looks like an unnecessary complication. I suggest just writing it as iterator = itertools.cycle([(condition1, 'First'), (condition2, 'Second')]). \$\endgroup\$ – 200_success Sep 29 '16 at 21:18
  • \$\begingroup\$ @200_success Yes, that's what I write in the 4th paragraph. Not sure if choosing one over the other is really a matter of better understanding or personnal preference. \$\endgroup\$ – 301_Moved_Permanently Sep 29 '16 at 21:40
1
\$\begingroup\$

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().

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.