I'm in favor of generalizing `map`. At first I was wary of less monomorphic types, but now I've found that it's not that hard to just lie and pretend the type is more specialized when teaching. Plus, `map` is a much nicer name than `fmap`.

Since there's been so many suggestions concerning radically changing the Prelude recently, I'd like to start a poll on a subject.
I know that "map" is limited to lists for the beginners, but then we're already making a lot of unbeginnerish changes to Prelude. Also it's not a monad transformer, but just a functor - how can a person learn Haskell without understanding what a Functor is?