[Haskell-cafe] Associative array updating

Dominic Fox dominic.fox1 at ntlworld.com
Sat Jan 1 08:28:41 EST 2005

Another newbie question.

The following is a naive attempt at a word count function, that takes a 
string and returns a list of word/count pairs.

     import Char

    isLetter c = isAlphaNum c || c=='\''

    normalize = map toLower . filter isLetter

    isWord [] = False
    isWord s = True

    nwords = filter isWord . map normalize . words

    update w [] = [(w, 1)]
    update w ((x, n):xs) =
        if x==w
            then (x, n+1) : xs
            else (x, n) : (update w xs)

    wordCount = foldr update [] . nwords

It works fine, but it's obviously very inefficient. I could make it less 
inefficient by implementing the word/count dictionary as a hash table or 
binary tree, but that's what standard libraries are for. So - what is 
there in the standard libraries that I could use in this scenario? I've 
looked at the Array module, but don't think it's quite suitable (we 
don't know the array bounds ahead of time, and the indices are strings). 
Data.HashTable looks better, but involves IO as it mutates the 
dictionary entries in place. Is there an alternative that could be used 
with a fold as in the code above?


More information about the Haskell-Cafe mailing list