Walrus Operator Doesn't Assign Variable?

Question

Playing with the walrus operator, I have this implementation of merge sort:

def mergesort(array):
    if len(array) == 1:
        output = array
    else:
        pivot = len(array) // 2
        left = mergesort(array[pivot:])
        right = mergesort(array[:pivot])
        output = []
        while (l := len(left)) or (r := len(right)):
            if l and r and left[0] < right[0]:
                output.append(left.pop(0))
            elif r:
                output.append(right.pop(0))
            else:
                output.append(left.pop(0))
        
    return output

mergesort([66, 93, 85, 46, 56, 88, 56, 75, 55, 99, 87])

But this returns the error UnboundLocalError: local variable 'r' referenced before assignment:

---------------------------------------------------------------------------
UnboundLocalError                         Traceback (most recent call last)
/tmp/ipykernel_134/1678992391.py in <module>
----> 1 mergesort(array)

/tmp/ipykernel_134/4030760045.py in mergesort(array)
      5     else:
      6         pivot = len(array) // 2
----> 7         left = mergesort(array[pivot:])
      8         right = mergesort(array[:pivot])
      9         

...

/tmp/ipykernel_134/4030760045.py in mergesort(array)
     10         output = []
     11         while (l := len(left)) or (r := len(right)):
---> 12             if l and r and left[0] < right[0]:
     13                 output.append(left.pop(0))
     14             elif r:

UnboundLocalError: local variable 'r' referenced before assignment

Why isn't r included in my for loop, while l is?

Answer 1

Boolean OR or is lazy, so when l turns out to be true, (r := len(right)) doesn't even get executed.

You could use the non-lazy bitwise OR | in this case, although it's a bit of an abuse.

Or just use the truth value of the lists instead of their lengths:

while left or right:
    if left and right and left[0] < right[0]:
        output.append(left.pop(0))
    elif right:
        output.append(right.pop(0))
    else:
        output.append(left.pop(0))

Btw better use <= instead of <, so that it's a stable sort as mergesort ought to be.

Addendum: Having fun with laziness:

while left or right:
    which = (left or right)[0] <= (right or left)[0] and left or right
    output.append(which.pop(0))

Another, note I switched to while ... and ... and append the remaining non-empty one after the loop:

while left and right:
    which = left if left[0] <= right[0] else right
    output.append(which.pop(0))
output += left or right

Or back to your style:

while left and right:
    if left[0] <= right[0]:
        output.append(left.pop(0))
    else:
        output.append(right.pop(0))
output.extend(left or right)

Answer 2

1. Python gets to the len(left) expression and evaluates it as True
2. This means it can instantly drop into the while loop without having to check the second statement, len(right), since Python is lazy
3. But, this means that r is left uninstantiated, since it wasn't evaluated

Unfortunately, putting extra parentheses around the expression does nothing.

E.g. while ( (l:=len(left)) or (r:=len(right)) ): doesn't work.

---

An option for getting around this could be to use + instead of or since they have the same logical meaning, but + requires evaluating the right hand side of the expression.

E.g.

def mergesort(array):
    if len(array) == 1:
        output = array
    else:
        pivot = len(array) // 2
        left = mergesort(array[pivot:])
        right = mergesort(array[:pivot])
        output = []
        while (l:=len(left)) + (r:=len(right)):
            if l and r and left[0] < right[0]:
                output.append(left.pop(0))
            elif r:
                output.append(right.pop(0))
            else:
                output.append(left.pop(0))
        
    return output

By the way, if ever you had the same problem with while X and Y, where X=0, you could use a similar trick as above, but rather than replace or with + you replace and with * since 0 * n == 0. I.e. while X * Y