[Haskell-cafe] Re: Nice way to calculate character frequency in a string

Scherrer, Chad Chad.Scherrer at pnl.gov
Tue Oct 25 11:58:36 EDT 2005

> Hello, I need to calculate the frequency of each character in a 
> String. And if I can do this really well in C, I don't find a nice
> fast) answer in haskell. I tried several functions, listed below, and 
> even the fastest do a lot of unnecessary things :

A while back, I was trying to build a "table" function similar to what
you describe, and Dean Herrington helped me speed it up and stop the
stack overflows I had been getting. Here it is, in case this is useful
to you...

table :: (Ord a) => [a] -> [(a,Int)]
table xs = Map.assocs $! foldl' f Map.empty xs
    where f m x = let  m' = Map.insertWith (+) x 1 m
                       Just v = Map.lookup x m'
                  in v `seq` m'

I would be interested in whether this is much slower than the other
approaches you've tried. If a faster approach could be made polymorphic,
I'd have a faster way to build tables!

Chad Scherrer
Computational Mathematics Group
Pacific Northwest National Laboratory

"Time flies like an arrow; fruit flies like a banana." -- Groucho Marx

More information about the Haskell-Cafe mailing list