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

[Max Rabkin]

On Sat, Sep 12, 2009 at 9:52 PM, Diego Souza <dsouza at bitforest.org> 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