Ketil Malde
I would solve this problem by reducing the Prelude to just a core. List function could go, for example, (mostly) into Data.List.
If this means that you must import Data.List almost everywhere, this won't change anything - only add yet another import to every file.
People often overlook the useful facility of the module system to group multiple common imports into a single re-exporting super-module. With my proposal, you would simply replace the implicit "import Prelude" with an explicit "import Prelude.Standard" (or use a build flag like -fimplicit-prelude, or +98). The idea is that backward compatibility with the old Prelude is preserved as much as possible, but the experimental ability to replace or remove parts of the Prelude is gained. Over time and through experience, a new consensus about what should be included might emerge.
I know most - if not all - of my modules use lists, but just in case, I checked with the darcs sources - 95 of 107 source files appear to use lists. Ignoring the : and ++ operators (looking for null, map, and filter) the count is 76 files.
Some data-structures people (e.g. Chris Okasaki) are of the opinion that lists tend to be over-used (because they are built-in), when other datatypes might be much more appropriate. Regards, Malcolm