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

Diego Souza dsouza at bitforest.org
Sat Sep 12 15:52:03 EDT 2009

> Looks like the output should be sorted.  The C++ version does this with the
> iterator over map<string, int> implicitly.  I don't spot where your haskell
> version sorts the output.
> There could be other problems, that's just what I can notice in 2 minutes of
> looking.
> Good luck!

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.

yahoo!im: paravinicius
gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B  9ECE F88E 067F E891 651E

More information about the Haskell-Cafe mailing list