[Haskell-cafe] Associative array updating
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.
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) =
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