defaultdicts all the way down

You may know the Haskell function fix:

fix :: (a -> a) -> a
fix f = let x = f x in x

This function applies its argument to itself. It’s called fix because it finds a (least-defined) fixed point of the function: f (fix f) == fix f. Here are some examples:

> take 10 $ fix (1:)  -- fix (1:) == [1,1..]
[1,1,1,1,1,1,1,1,1,1]
> fix (\f n -> if n == 0 then 1 else n * f (pred n)) 5  -- factorial
120

It’s not a function you need very often, but the other day I needed it in Python! I wanted to have a defaultdict that defaults to defaultdict that defaults to defaultdict that defaults… all the way down. This is a fixed point of defaultdict. Here we go:

def fix(f):
    return lambda *args, **kwargs: f(fix(f), *args, **kwargs)

We have to wrap f inside a lambda so that it’s not evaluated when fix is called. Let’s try it out:

>>> from collections import defaultdict
>>> d = fix(defaultdict)()
>>> d["a"]["b"]["c"]
defaultdict(<function <lambda> at 0x105c4bed8>, {})

You can bet I was feeling clever when I wrote this.