Idiomdrottning’s homepage

A mnemonic for caddar, cadadr and similar

In years past I’ve been using the real underlying semantics (i.e. compositions of car and cdr) to keep these straight which works fine, it’s just a bit of thought every time. But the last few weeks I’ve switched to the following fake semantics which give isomorphic results but are way faster and easier to do in my head.

In the following text, a “thing” is a subtree or an atom. '(a b c) has three things, as does '(a (1 2 3 4) c).

AD* operators

The A means taking the thing and the number of Ds is a zero-index count. so car is thing 0, cadr is thing 1, caddr is thing 2 etc.

Concatenating these AD* operators is still composition (just as the real semantics).

The mental shortcut is splitting them in A-initialized sub-operators. (That asterisk is a Kleene star.)

So (caddaddr) is the third thing of the third thing.

No A? No A!

The D means just taking the tail and the number of Ds, including the initial D, is a zero-index count.

So identity is tail 0, cdr is tail 1, cddr is tail 2 etc.

Only mentally do this for the left-most sub-operator after splitting out all the AD* sub-operators.

So cddaddadr is the second tail of the third thing of the second thing.

Closing Words

In the past I would have to go right to left, slowly and maybe with the aid of paper and pencil “uh… so we have the first tail and then the first sub-list and then the first, no the second tail of that, and then the first sub list of that, and then finally we have… humm… the second tail of that?” but with these AD* operators — which only exist in my mind, they’re not really implemented as code [the code still uses straight compositions of car and cdr] I can just see it instantly.

A while ago I realized that that cadr = second, caddr = third etc but I didn’t generalize the thinking to the compositions of these until just now.

On IRC after I posted this, people were like “just use matchable, lol” which can sometimes be a better solution, if you need more than one thing.

I find myself using mnemonic six months later. Sometimes you really do need to grab just one thing, and that’s when a cddar or whatever is gold.