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

Max Rabkin max.rabkin at gmail.com
Sun Sep 13 05:34:16 EDT 2009

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.


More information about the Haskell-Cafe mailing list