Python’s defaultdict is an incredibly useful tool to specify default values for missing keys (RealPython has a great primer on them).

I found I was taking up so much memory to store the value 0 for an algorithm which counted rather infrequent elements in a huge sequence split into many chunks. Using a defaultdict(int) for each distinct element to store which indices had a non-zero count of the respective element greatly optimised it, but I yearned for a defaultlist equivalent to standardise this approach and generally make my code more expressive.

Humble beginnings

There are some opinionated decisions of what constitutes a “defaultlist”, so whilst an excellent implementation already exists by c0fec0de, I disagreed with some behaviours that led me to implement my own. My idea of a defaultlist is to be a glorified wrapper of the defaultdict. We can use the MutableSequence abstract base class to mirror the interface one would expect from a builtin list.

class defaultlist(MutableSequence):
def __getitem__(self, i):
...

def __setitem__(self, i, value):
...

def __delitem__(self, i):
...

def __len__(self):
...

def insert(self):
...


Firstly we can initialise an internal defaultdict in self._ddict, taking a default_facotry argument. Each key of self._ddict will represent an index of a list.

Note that defaultdict does not require a default_factory and will raise a KeyError when you try to access a missing key in such scenarios. For a list variant this behaviour would be nonsensical as missing elements between existing ones really aren’t erroneous, so we can just make default_factory return None if not specified.

    def __init__(self, default_factory=None):
self._ddict = defaultdict(default_factory or defaultlist._none_factory)

@staticmethod
def _none_factory():
return None


The get and set item methods, which determine the behaviour of square brackets notation (e.g. my_dlist[i]), can also directly interface with the internal defaultdict we initialised. This means that all elements of our defaultlist will default just like its dictionary counter-part.

    def __getitem__(self, i):
return self._ddict[i]

def __setitem__(self, i, v):
self._ddict[i] = v


A delete item method (called like del my_dlist[i]) requires a bit more work. The list builtin will reindex elements above the deleted index, and so we can emulate that behaviour by decrementing the keys of our internal defaultdict. Conversely an insert method can increment the keys of self._ddict before safely assigning the value at i.

    def __delitem__(self, i):
# I decided to be agnostic if the element exists or not
try:
del self._ddict[i]
except KeyError:
pass

larger_keys = [k for k in self._ddict.keys() if k > i]
reindexed_subdict = {k - 1: self._ddict[k] for k in larger_keys}
for k in larger_keys:
del self._ddict[k]
self._ddict.update(reindexed_subdict)

def insert(self, i, value):
larger_keys = [k for k in self._ddict.keys() if k >= i]
reindexed_subdict = {k + 1: self._ddict[k] for k in larger_keys}
for k in larger_keys:
del self._ddict[k]
self._ddict.update(reindexed_subdict)

self._ddict[i] = value


As we’re treating keys in the self._ddict as indexes, we can treat the highest existing index as the deciding factor for what constitutes the length (e.g. result of len(my_dlist)) of our defaultlist.

    def __len__(self):
try:
return max(self._ddict.keys()) + 1
except ValueError:
return 0


We are currently assuming positive indices are being passed, but list does take in negative indices that translate to the length of the list n minus (or rather plus) the negative index. We can support this behaviour by inspecting and modifying the passed index before we actually use it on our internal defaultdict.

    def _actualise_index(self, i):
if i >= 0:
return i
else:
n = len(self)
if i >= -n:
return n + i
else:
raise IndexError("negative list index larger than list length, unresolvable")

def __getitem__(self, i):
i = self._actualise_index(i)
return self._ddict[i]

def __setitem__(self, i, v):
i = self._actualise_index(i)
self._ddict[i] = v

def __delitem__(self, key: Union[int, slice]):
i = self._actualise_index(key)
try:
del self._ddict[i]
except KeyError:
pass
...


As we’ve successfully overridden the MutableSequence interface, it will conveniently deal with second-order features of a list such as iteration (for x in my_dlist) and appending (my_dlist.append(x)).

Bounding infinity

Currently, iterating over a defaultlist will go on forever. Iteration of an object is determined by it’s __iter__() method, and inheriting MutableSequence comes with such a method which will __getitem__(i) from 0 until an IndexError is raised. As defaultlist is an infinite field of elements, no such error is ever raised.

I decided its iteration capabilities should be bounded to the length property (defined earlier).

    def __iter__(self):
for k in range(len(self)):
yield self._ddict[k]


This provides an easy way for user to specify iteration bounds using slice notation. Say you were implementing an algorithm that divvied-up a sequence into 100 chunks and counted in each chunk using counts = defaultlist(int) (i.e. default the count to 0), then you can specify the first 100 elements of counts when it’s time for a for loop.

for count in counts[:100]:
...


…that is, if slicing is supported.

We can actually detect the stop:start:step notation—which is infact a builtin slice object—in our __getitem__() method by inspecting the passed key with an instance check (i.e. isinstance()).

A builtin list handles slices as a range bounded by the list’s length—for the most part, check out my list reference implementation for a complete specification of how list handles slicing. We however don’t need to worry about going out-of-bounds as the defaultlist is essentially an infinite field of elements. All we need to do then is handle None values before making a 1-to-1 translation from slice to the range builtin.

    def __getitem__(self, key):
if isinstance(key, int):
i = self._actualise_index(key)
return self._ddict[i]

elif isinstance(key, slice):
start = key.start or 0
stop = key.start or 0
step = key.step or 1

if key.start is None:
start = 0 if step > 0 else len(self)
else:
start = self._actualise_index(key.start)

if key.stop is None:
stop = len(self) if step > 0 else 0
else:
stop = self._actualise_index(key.stop)

srange = range(start, stop, step)

dlist = defaultlist(self._ddict.default_factory)
dlist.extend(self._ddict[i] for i in srange)

return dlist


At this point, we’ve got ourselves a pretty functional defaultlist!

Filling in the gaps

Complete slicing support

We can also support slices for setting and deleting elements. Like with the insert method, it’s simply a matter of reindexing the internal defaultdict to accommodate for the addition and/or removal of existing elements … but as you can see, it’s a bit of a headache to keep track of things.

    def _determine_srange(self, slice_):
step = slice_.step or 1

if slice_.start is None:
start = 0 if step > 0 else len(self)
else:
start = self._actualise_index(slice_.start)

if slice_.stop is None:
stop = len(self) if step > 0 else 0
else:
stop = self._actualise_index(slice_.stop)

return range(start, stop, step)

def __getitem__(self, key):
if isinstance(key, int):
i = self._actualise_index(key)

return self._ddict[i]

elif isinstance(key, slice):
srange = self._determine_srange(key)
dlist = defaultlist(self._ddict.default_factory)
dlist.extend(self._ddict[i] for i in srange)

return dlist

def __setitem__(self, key, value):
if isinstance(key, int):
i = self._actualise_index(key)
self._ddict[i] = value

elif isinstance(key, slice):
values = list(value) if isinstance(value, Iterable) else [value]
nvalues = len(values)

srange = self._determine_srange(key)
if srange:
srange_min = min(srange[0], srange[-1])
srange_max = max(srange[0], srange[-1])
else:
srange_min = srange_max = srange.start

for i in srange:
try:
del self._ddict[i]
except KeyError:
pass

diff = nvalues - len(srange)
if diff:
keys = list(self._ddict.keys())

threshold = srange_min + nvalues
reindexed_subdict = {}

mid_keys = [k for k in keys if srange_min <= k < srange_max]
for i, k in enumerate(sorted(mid_keys), start=threshold):
reindexed_subdict[i] = self._ddict[k]

larger_keys = [k for k in self._ddict.keys() if k > srange_max]
for k in larger_keys:
i = k + diff
reindexed_subdict[i] = self._ddict[k]

self._ddict.update(reindexed_subdict)

for i, v in enumerate(values, start=srange_min):
self[i] = v

def __delitem__(self, key):
if isinstance(key, int):
i = self._actualise_index(key)
try:
del self._ddict[i]
except KeyError:
pass

larger_keys = [k for k in self._ddict.keys() if k > i]
reindexed_subdict = {k - 1: self._ddict[k] for k in larger_keys}
for k in larger_keys:
del self._ddict[k]
self._ddict.update(reindexed_subdict)

elif isinstance(key, slice):
srange = self._determine_srange(key)
if srange:
for i in srange:
try:
del self._ddict[i]
except KeyError:
pass

srange_min = min(srange[0], srange[-1])
srange_max = max(srange[0], srange[-1])

reindexed_subdict = {}

mid_keys = [k for k in self._ddict.keys() if srange_min <= k < srange_max]
for i, k in enumerate(values, start=srange_min):
reindexed_subdict[i] = self._ddict[k]

larger_keys = [k for k in self._ddict.keys() if k > srange_max]
for k in larger_keys:
i = k - len(srange)
reindexed_subdict[i] = self._ddict[k]

for k in chain(mid_keys, larger_keys):
del self._ddict[k]
self._ddict.update(reindexed_subdict)


Equality checks

We might also want to emulate how list can be equality checked (i.e. a == b notation) with other list objects. Equality check behaviour is specified in the __eq__(self, other) dunder method of the first instance (i.e. a in a == b). Rather than caring if a defaultlist is being checked with another defaultlist however, I found broadly check against all Sequence-like types to make it much more versatile.

    def __eq__(self, other):
if isinstance(other, Sequence):
if len(self) != len(other):
return False
else:
return all(a == b for a, b in zip(self, other))
else:
return False


Note that zip(self, other) is using the __iter__() methods of both the defaultlist instance and other. This means you can check if an iteration of a defaultlist would actually match up with your expectations using the nice brackets notation that Python uses for its list.

>>> my_dlist = defaultlist(int)
>>> my_dlist[2] = 2
>>> my_dlist == [0, 0, 2]
True


Finding first instances

MutableSequence also adds the index() method to our defaultlist() automatically, but like with __iter__() it expects an IndexError from our get method—as this never comes to fruition, index() can go on forever.

All this means is we need to override index() to bound the iteration to it’s pseudo-length. Like with our __eq__() method above, note that enumerate(self) is calling __iter__().

    def index(self, x):
for i, v in enumerate(self):
if v == x:
return i
else:
raise ValueError(f"'{x}' is not in defaultlist")


This also fixes the automatic remove() method too, as that relies upon index() to find the i to then delete.

Fin

A hopefully production-ready defaultlist is available in my coinflip library, available in the coinflip.collections.defaultlist namespace. Its source code is available on GitHub (and don’t forget tests).

Huge thanks to c0fec0de for their defaultlist implementation, which really helped me think deeply about what I wanted the API to be for my own take. Also I suppose a shout out to Guido, who I think implemented the much beloved defaultdict. Maybe it was Raymond Hettinger…? I couldn’t work this one out—git blame and all—so if anyone knows this then please let me know!