List comprehension python

Question

What is the equivalent list comprehension in python of the following Common Lisp code:

(loop for x = input then (if (evenp x)
                             (/ x 2)
                             (+1 (* 3 x)))
      collect x
      until (= x 1))

Answer 1

1

I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

In all seriousness though, I don't believe you can do this with Python list comprehensions. They have basically the same power as map and filter, so you can't break out or look at previous values without resorting to hackery.

Answer 2

I believe you are writing the hailstone sequence, although I could be wrong since I am not fluent in Lisp.

As far as I know, you can't do this in only a list comprehension, since each element depends on the last.

How I would do it would be this

def hailstone(n):
    yield n
    while n!=1
        if n%2 == 0: # even
            n = n / 2
        else: # odd
            n = 3 * n + 1
        yield n

list = [ x for x in hailstone(input) ]

Of course, input would hold whatever your input was.

My hailstone function could probably be more concise. My goal was clarity.

Answer 3

A list comprehension is used to take an existing sequence and perform some function and/or filter to it, resulting in a new list. So, in this case a list comprehension is not appropriate since you don't have a starting sequence. An example with a while loop:

numbers = []
x=input()
while x != 1:
  numbers.append(x)
  if x % 2 == 0: x /= 2
  else: x = 3 * x + 1

Answer 4

As Kiv said, a list comprehension requires a known sequence to iterate over.

Having said that, if you had a sequence and were fixated on using a list comprehension, your solution would probably include something like this:

[not (x % 2) and (x / 2) or (3 * x + 1) for x in sequence]

Mike Cooper's answer is a better solution because it both retains the x != 1 termination, and this line doesn't read cleanly.

Answer 5

Python doesn't have this kind of control structure built in, but you can generalize this into a function like this:

def unfold(evolve, initial, until):
    state = initial
    yield state
    while not until(state):
        state = evolve(state)
        yield state

After this your expression can be written as:

def is_even(n): return not n % 2
unfold(lambda x: x/2 if is_even(x) else 3*x + 1,
       initial=input, until=lambda x: x == 1)

But the Pythonic way to do it is using a generator function:

def produce(x):
    yield x
    while x != 1:
        x = x / 2 if is_even(x) else 3*x + 1
        yield x

Answer 6

The hackery referred to by Laurence:

You can do it in one list comprehension, it just ends up being AWFUL python. Unreadable python. Terrible python. I only present the following as a curiosity, not as an actual answer. Don't do this in code you actually want to use, only if you fancy having a play with the inner workings on python.

So, 3 approaches:

---

Helping List 1

1: Using a helping list, answer ends up in the helping list. This appends values to the list being iterated over until you've reached the value you want to stop at.

A = [10]
print [None if A[-1] == 1
    else A.append(A[-1]/2) if (A[-1]%2==0) 
    else A.append(3*A[-1]+1) 
        for i in A]
print A

result:

[None, None, None, None, None, None, None]
[10, 5, 16, 8, 4, 2, 1]

---

Helping List 2

2: Using a helping list, but with the result being the output of the list comprehension. This mostly relies on list.append(...) returning None, not None evaluating as True and True being considered 1 for the purposes of arithmetic. Sigh.

A=[10]
print [A[0]*(not A.append(A[0])) if len(A) == 1 
    else 1 if A[-1] == 2 else (A[-1]/2)*(not A.append(A[-1]/2)) if (A[-1]%2==0) 
    else (3*A[-1]+1)*(not A.append(3*A[-1]+1)) 
        for i in A]

result:

[10, 5, 16, 8, 4, 2, 1]

---

Referencing the List Comprehension from within

3: Not using a helping list, but referring back to the list comprehension as it's being built. This is a bit fragile, and probably wont work in all environments. If it doesn't work, try running the code on its own:

from itertools import chain, takewhile
initialValue = 10
print [i if len(locals()['_[1]']) == 0
    else (locals()['_[1]'][-1]/2) if (locals()['_[1]'][-1]%2==0)
    else (3*locals()['_[1]'][-1]+1) 
        for i in takewhile(lambda x:x>1, chain([initialValue],locals()['_[1]']))]

result:

[10, 5, 16, 8, 4, 2, 1]

---

So, now forget that you read this. This is dark, dark and dingy python. Evil python. And we all know python isn't evil. Python is lovely and nice. So you can't have read this, because this sort of thing can't exist. Good good.