I see the same kind of argument ordering in Data.Map. Why is the data structure last? Usually one would think that the arguments should be ordered from "most constant" to "least constant" so that currying is as useful as possible. But surely the data structure is "more constant" than its elements, even (especially?) if it is persistent.
I would think that the most constant parameter is the ordering function. The second most constant is debatable, but I tend to think that it's more common to insert the same key into a list of priority queues, for example, rather than insert different keys in to the same priority queue (that is, as long as the queue is side-effect free)...
Maybe it's a 'foldr' versus 'foldl' thing, where you and Data.Map have chosen 'foldr'. Personally I prefer 'foldl'. After all, traversing the list in order is more intuitive. Frederik