<div class="gmail_quote">On Mon, Jun 22, 2009 at 10:10 AM, Ketil Malde <span dir="ltr">&lt;<a href="mailto:ketil@malde.org">ketil@malde.org</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

<div class="im">Kamil Dworakowski &lt;<a href="mailto:kamil@dworakowski.name">kamil@dworakowski.name</a>&gt; writes:<br>
<br>
&gt; Right... Python uses hashtables while here I have a tree with log n<br>
&gt; access time. I did not want to use the Data.HashTable, it would<br>
&gt; pervade my program with IO. The alternative is an ideal hashmap that never<br>
&gt; gets changed. This program creates a dictionary at start which then is only<br>
&gt; being used to read from: an ideal application for the Data.PerfectHash<br>
&gt; by Mark Wotton available on Hackage [3].<br>
<br>
</div>If you are considering alternative data structures, you might want to<br>
look at tries or Bloom filters, both have O(n) lookup, both have<br>
Haskell implementations.  The latter is probably faster but<br>
probabilistic (i.e. it will occasionally fail to detect a<br>
misspelling - which you can of course check against a &quot;real&quot;<br>
dictionary).</blockquote><div> <br>Typo? Bloom filters have O(1) lookup and tries O(m) lookup where m is the number of characters in the string. <br></div></div><br>Cheers,<br><br>Johan<br><br>