Re: [Haskell-cafe] why these two are not equivalent?

On Sat, Sep 12, 2009 at 9:52 PM, Diego Souza wrote:

I assumed Data.Map was a tree internally and keep elements ordered, so the following would sort the input and print duplicates in O(n log n), as the C++ version does:

sbank :: [B.ByteString] -> [(B.ByteString,Int)] sbank = toAscList . fromListWith (+) . flip zip (repeat 1)

Is it wrong to assume this? It worked for all tests cases I could think of though.

That is part of the contract of toAscList (the "Asc" stands for "ascending order"), but because of the way Map is implemented, the result of toList is also sorted. --Max