Saturday, March 08, 2008

No big deal?

Have you ever done something "obvious" and later discovered that it's the topic of a famous paper, or something that gets put in the "advanced" section of the textbooks?

I just read the wikipedia article on tail recursion, and got a surprise when I read the last section.

I've always implemented lists in C along these lines:


void insert(list_t** list, int idx, list_t* item)
{
while(*list && idx--)
list = &(*list)->next;
item->next = *list;
*list = item;
}


Now to me, this is pretty obvious stuff. But it turns out to have a name - "tail recursion modulo cons" - and credit for its invention goes to David H. D. Warren. Go figure.

I have to ask, though - are our standards getting higher so fast that an advanced concept from twenty years ago is now not worth mentioning?