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:

1. What am I missing about None vs. [], and how do I get this code to work?
2. 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!

Answer 1

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.

Answer 2

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, [])

Answer 3

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.

Answer 4

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.