Making Bad Lists Impossible

Making Bad Lists Impossible

David Beazley (https://www.dabeaz.com)
April 2, 2023

One idea in the creation of reliable software is the practice of making invalid states impossible. This post isn’t so much about that, but about a similar problem involving data. It’s motivated by an issue that arises in my Rafting Trip course, but I’ve tried to simplify it a bit.

A Weird List Append

Suppose that when appending to a list, you had to specify the last item in addition to the new one that you were appending. Basically, a function like this:

def append_entry(items, last_item, item):
    if items[-1] == last_item:
        items.append(item)
        return True
    else:
        return False

The purpose of providing last_item is a consistency check. Unless it exactly matches, the append operation fails. It looks weird, but here’s an example of how it works:

>>> items = ['guido', 'barry', 'carol']
>>> append_entry(items, 'carol', 'alice')   # Works (last item is 'carol')
True
>>> items
['guido', 'barry', 'carol', 'alice']
>>> append_entry(items, 'bob', 'larry')     # Fails (last item is not 'bob')
False
>>> items
['guido', 'barry', 'carol', 'alice']
>>>

Admittedly, it’s not the most intuitive way to append to a list, but there must be some underlying reason for it. That reason is not so important here.

An Annoying Edge Case

One problem with this code is what to do for the case of an empty list? In that case, what do you specify for the last item?

On approach is to make a special input value FIRST and to check for it like this:

FIRST = object()

def append_entry(items, last_item, item):
    if last_item is FIRST or items[-1] == last_item:
        items.append(item)
        return True
    else:
        return False

To use this new version, users now have to write code like this:

>>> items = []
>>> append_entry(items, FIRST, 'guido')
True
>>> items
['guido']
>>>

Of course, this works fine until you realize that FIRST can be used to override the consistency check:

>>> append_entry(items, FIRST, 'carol')
True
>>> items
['guido', 'carol']
>>>

Going back to the drawing board, you modify append_entry() once again to only allow FIRST if the list is empty:

FIRST = object()

def append_entry(items, last_item, item):
    if (not items and last_item is FIRST) or items[-1] == last_item:
        items.append(item)
        return True
    else:
        return False

Frankly, the code is starting to get real “fiddly.” Fiddly code also tends to be prone to logic bugs. What’s worse, every place that ever calls append_entry() has to be aware of this weird edge case too. For example:

def some_function():
    ...
    last_item = items[-1] if items else FIRST
    success = append_entry(items, last_item, newitem)
    ...

That’s super annoying and error prone–especially if you forget about it.

Make Empty Lists Illegal

Maybe a better approach to this problem is to simply disallow empty lists with an assert:

def append_entry(items, last_item, item):
    assert items, "Can't append_entry to empty list"
    if items[-1] == last_item:
        items.append(item)
        return item
    else:
        return False

Aside from the extra assertion, the internal logic of append_entry() is greatly simplified. Moreover, all code that ever calls append_entry() is simplified as well. There is no edge case–lists are always required to be non-empty.

def some_function():
    ... 
    success = append_entry(items, items[-1], newitem)
    ...

Of course, there is still the problem of creating the initial list. What do you use as the first item? Maybe you write a helper function like this:

def create_items(initial):
    return [ initial ]

In some sense, the problem has been fixed by moving it somewhere else. Yes, there’s still an edge case, but it’s now addressed at the time of list creation–not at a time where the list is being used.

The use of a helper function here suggests that further abstraction might be used later. For example, perhaps create_items() is later modified to return an instance of some class instead. For now, we’ll leave that as a further exercise.

Classes For Late Spring

Just a note, I have space in the following course scheduled for spring:

• Write a Compiler, May 1-5
• SICP, May 15-19
• Advanced Programming with Python, June 5-9
• Rafting Trip, June 19-23

With the implosion of Twitter, it’s a bit hard to get the word out. However, if you or someone you know might be interested, send them to my courses page.

Also, be on the lookout for more short courses in the spirit of the recent Elevated course. More details soon!

Cheers,
Dave