Trouble inserting in Python (None vs. empty list)

Question

I'm trying to solve the following exercise from Google's Python class.

E. Given two lists sorted in increasing order, create and return a merged list of all the elements in sorted order. You may modify the passed in lists. Ideally, the solution should work in "linear" time, making a single pass of both lists.

I'm using the following Scheme approach (I wish I had car, cdr and cons!).

def helper(list1, list2, result):
  if list1 == None:
    return result + list2
  elif list2 == None:
    return result + list1
  elif list1[0] < list2[0]:
    return helper(list1[1:], list2, result.insert(0, list1[0]))
  else:
    return helper(list1, list2[1:], result.insert(0, list2[0]))

def linear_merge(list1, list2):
  helper(list1, list2, [])

The error I get is, I can't seem to insert an element into result when result is []:

AttributeError: 'NoneType' object has no attribute 'insert'

But that works fine in the console:

>>> b = []
[]
>>> b.insert(0, 4)
>>> b
[4]

I'm brand new to Python, so I have two questions:

What am I missing about None vs. [], and how do I get this code to work?
If Python wasn't meant for a Scheme/Lisp approach, what's the "Python way" of solving this? This is less important to me, since I can just check the solutions.

Thanks!

As a side note, you almost always want to compare against None with is, not ==. But that's not your problem here. — abarnert
– abarnert, Commented Nov 12, 2013 at 19:54
Hint: list.insert modifies the list in-place, and returns None. So you probably don't want to pass it as a parameter for a function. — Kevin
– Kevin, Commented Nov 12, 2013 at 19:55
Also, note that, while this does make a single pass through the lists, it doesn't work in linear time—deleting and inserting on the left end of a list is O(N) in the list size. — abarnert
– abarnert, Commented Nov 12, 2013 at 20:01
P.S., if you want car, cdr, and cons for Python lists, that's pretty easy: def car(xs): return xs[0], def cdr(xs): return xs[1:], def cons(x, xs): return [x] + xs. But again, cdr and cons will be linear time. If you really want to use Scheme algorithms without thinking about them, build an actual Cons type (which is very easy) and use that. Or, better, rethink your algorithm to work from the right, or to work in terms of passing a list and a slice object instead of slicing the list, or… — abarnert
– abarnert, Commented Nov 12, 2013 at 21:19

chepner · Accepted Answer · 2013-11-12 20:02:50Z

5

list.insert returns None, not the modified list.

This requires helper to be changed to read

def helper(list1, list2, result):
  if not list1:
    return result + list2
  elif not list2:
    return result + list1
  elif list1[0] < list2[0]:
    return helper(list1[1:], list2, result + [list1[0]])
  else:
    return helper(list1, list2[1:], result + [list2[0]])

Note the changes to the two base cases. None and the empty list [] are not the same thing. The pythonic way of testing if a list is empty is to treat the list as a Boolean value: empty lists are False, all others are True.

And as the others have noticed before me, you need to explicitly return the return value of helper in linear_merge.

edited Nov 12, 2013 at 20:02

answered Nov 12, 2013 at 19:56

chepner

538k77 gold badges594 silver badges746 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

DSM Over a year ago

I think you need result + list1[:1] or result + [list1[0]] or something. Right now you're adding a list to an element of a list.

chepner Over a year ago

Thanks; I forgot to make that change when switching from insert to concatenation.

DSM Over a year ago

Now the OP only has to fix the bug in the algorithm. :^)

bluemihai Over a year ago

Got it. The information I was missing was how to turn an element into a list so I can just add them. Just put it into square brackets! Thanks...

abarnert · Accepted Answer · 2013-11-12 20:08:55Z

The first problem is that [] and None are not equal.

This causes two problems for you.

First, your test for the recursive base case isn't working. If you're trying to test for a list being empty, there are a number of ways to do it:

if not list1:

if list1 == []:

if len(list1) == 0:

But comparing it to None is not one of those ways.

The first is generally considered the most Pythonic (and explicitly encouraged by the PEP 8 style guide).

Second, you're apparently explicitly calling this function with None as an argument somewhere in code you haven't shown us. Don't do that. Call it with [] when you mean [].

And the other problem is that mutable methods like list.insert don't return the mutated object, they return None. So, instead of this:

return helper(list1[1:], list2, result.insert(0, list1[0]))

… you need to either do this:

result.insert(0, list1[0])
return helper(list1[1:], list2, result)

… or use a non-mutating expression instead:

return helper(list1[1:], list2, [list1[0]] + result)

And then, your linear_merge doesn't return anything, so its value will be None. Change it to:

return helper(list1, list2, [])

Amber · Accepted Answer · 2013-11-12 19:58:17Z

1

result.insert does not return a new list; it modifies an existing result in place. Thus you wind up passing None as the third argument to your nested helper() calls, because that's what result.insert returns - None.

Also note:

def linear_merge(list1, list2):
    helper(list1, list2, [])

Since you don't return anything from linear_merge, you're always going to get None as the result.

answered Nov 12, 2013 at 19:58

Amber

531k89 gold badges643 silver badges558 bronze badges

Comments

abarnert · Accepted Answer · 2013-11-12 21:14:11Z

Since you asked for a Pythonic solution, as well as how to fix your attempt, I'll write you one as a separate answer.

I'd do this by using iterators. At each step, you yielding the lower value and pulling the next one. The same way you'd do it in Haskell.* This actually is linear time, and it's lazy as well. Using more-itertools:

def itermerge(i1, i2):
    i1, i2 = iter(i1), more_itertools.peekable(iter(i2))
    for v1 in i1:
        while i2 and i2.peek() < v1:
            yield next(i2)
        yield v1
    yield from i2

If you need Python 2.x or 3.2 compatibility, just change the yield from i2 with for v2 in i2: yield v2.

If it's not clear how this works, here's the most explicit version, to show exactly what's happening at each step:

def itermerge(i1, i2):
    i1, i2 = iter(i1), iter(i2)
    sentinel = object()
    v1, v2 = sentinel, sentinel
    while True:
        if v1 is sentinel:
            try:
                v1 = next(i1)
            except StopIteration:
                yield from i2
                return
        if v2 is sentinel:
            try:
                v2 = next(i2)
            except StopIteration:
                yield from i1
                return
        if v1 < v2:
            yield v1
            v1 = sentinel
        else:
            yield v2
            v2 = sentinel

If you need a function that returns a list, that's easy:

def linear_merge(l1, l2):
    return list(itermerge(l1, l2))

* This is a bit of a joke. While you can write pretty much any of the immutable versions of this algorithm in Haskell, the one that's most like this solution is probably not the one you'd write.

Collectives™ on Stack Overflow

Trouble inserting in Python (None vs. empty list)

4 Answers 4

4 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related