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

[Benjamin Franksen]

On Thursday 27 October 2005 10:29, Ketil Malde wrote:
> Scherrer, Chad wrote:
> >Sorry to drag this thread out, but here's one more thing you might
> >try...
>
> (This is the café, isn't it? :-)
>
> Another option is perhaps to pack both char and count in one Int and
> use some kind of Set.
> This should save some space, and possibly time as well (presuming
> bitwise ops are less expensive
> than pointer dereferences, which I believe have been a safe
> assumption since the mid-90s), but requires a Set being searchable
> for ranges.  (Do any of the implementations support this, BTW?)

It's interesting that you mention this. I have been working for some 
time now on a library implementation of 2-3 finger search trees (as 
described in a paper by Ralf Hinze, see 
http://www.cs.bonn.edu/~ralf/publications/IAI-TR-98-12.ps.gz). These 
beasts give you quite efficient split (aka partition) operations: 
complexity is amortized O(d,n-d), where d is the distance from the 
split key to the smallest element (or the largest, if you like). You 
can splice out a range using two consecutive single point splits. OTOH, 
I have been considering to implement a specialized range operation 
which could be even more efficient.

You could also use the similar (but *much* easier to implement) 
annotated 2-3 finger /leaf/ trees (see 
http://www.cs.bonn.edu/~ralf/publications/FingerTrees.pdf). As far as I 
understood, these are not quite as good as the above mentioned node 
trees, but they differ only by constant factors.

Ben