Research Agenda

I think the subject of my paper will be "Automatic Selection of List Representation". There are so many different ways to represent a list, and each has its own tradeoffs in terms of memory usage and speed. For example, you have:

• singly-linked lists (the favorite of nearly every functional language)
• arrays (the favorite of nearly every imperative language)
• doubly-linked lists
• singly-linked lists with a tail pointer (if appending is important)
• sorted lists
• vectors (ala std::vector in C++)
• hashtables (if order is unimportant)
• binary trees (if lookup and insertion are more important than memory usage)

I will probably work on this in the context of haskell, since 1) lists are ubiquitous in haskell, and 2) haskell serves as a pretty good specification language, due to the lack of side effects.

The first thing to do, though, is to make sure that this hasn't been done already. Besides, if it has been done, I'd love to read about it. So I'm off to look for prior art.