Michal, As Daan Leijen has suggested, `accumArray` is probably the best solution to your simple histogramming problem. However, you might also be interested to learn about "finite maps", which are often the appropriate functional analogue to "hash maps". Finite maps are typically implemented with balanced trees and exhibit O(log n) time cost for insertion and lookup. (The extra cost over imperative languages' O(1) cost is the price paid for persistence.) The following version of your program runs on Hugs 98 and GHC. (For GHC you must specify "-package data" to access the `FiniteMap` module.)
import Char (isAlpha, toLower) import FiniteMap
main :: IO () main = interact (report . histogram)
type Histo = FiniteMap Char Int
histogram :: String -> Histo histogram = foldl tally emptyFM
tally :: Histo -> Char -> Histo tally histo ch = if isAlpha ch then addToFM_C (+) histo (toLower ch) 1 else histo
report :: Histo -> String report histo = unlines [ line ch | ch <- ['a'..'z'] ] where line ch = ch : " " ++ replicate (count ch) '*' count ch = lookupWithDefaultFM histo 0 ch
Dean Herington