[Haskell-cafe] Optimizing spelling correction program

[Ketil Malde]

Kamil Dworakowski <kamil at dworakowski.name> writes:

> Right... Python uses hashtables while here I have a tree with log n
> access time. I did not want to use the Data.HashTable, it would
> pervade my program with IO. The alternative is an ideal hashmap that never
> gets changed. This program creates a dictionary at start which then is only
> being used to read from: an ideal application for the Data.PerfectHash
> by Mark Wotton available on Hackage [3].

If you are considering alternative data structures, you might want to
look at tries or Bloom filters, both have O(n) lookup, both have
Haskell implementations.  The latter is probably faster but
probabilistic (i.e. it will occasionally fail to detect a
misspelling - which you can of course check against a "real"
dictionary).

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants