Why is this Haskell code so slow?
<p>I'm kind of new to Haskell and tried making a scrabble solver. It takes in the letters you currently have, finds all permutations of them and filters out those that are dictionary words. The code's pretty simple: </p>

<pre><code>import Data.List

main = do
    dict    &lt;- readFile "words"
    letters &lt;- getLine
    let dictWords = words dict
    let perms = permutations letters
    print [x | x &lt;- perms, x `elem` dictWords]
</code></pre>

<p>However it's incredibly slow, compared to a very similar implementation I have with Python. Is there something fundamental I'm doing wrong?</p>

<p>*edit: Here's my Python code:</p>

<pre><code>from itertools import permutations

letters = raw_input("please enter your letters (without spaces): ")

d = open('words')
dictionary = [line.rstrip('\n') for line in d.readlines()]
d.close()

perms = ["".join(p) for p in permutations(letters)]

validWords = []

for p in perms:
    if p in dictionary: validWords.append(p)


for validWord in validWords:
    print validWord
</code></pre>

<p>I didn't time them precisely, but roughly it feels like the Python implementation is about 2x as fast as the Haskell one. Perhaps I should't have said the Haskell code was "incredibly slow" in comparison, but since Haskell is statically typed I guess I just thought that it should've been much faster, and not slower than Python at all.</p>

<p>Checking if <code>x</code> is an element of <code>dictWords</code> is likely to be very slow.  I would assume that your similar python implementation stores <code>dictWords</code> in a set or sorted vector (using binary search in the latter case)?  Seems like you probably want to do the same here.</p>

<p>Using <a href="https://www.wordgamedictionary.com/twl06/download/twl06.txt" rel="nofollow">this word list</a> and the code below, the Python version runs in about 30 seconds, and the Haskell version takes 1.5 minutes.  So Haskell is slower (perhaps because it's using a linked list, which all things being equal, is slower to iterate over), but I wouldn't call it "incredibly slow" compared to Python.  Switching to use a set in either version reduces the time to under 1 second.</p>

<pre class="lang-py prettyprint-override"><code>from itertools import permutations
f = open('twl06.txt')
words = f.read().split()

print [''.join(p) for p in permutations('apricot') if ''.join(p) in words]
</code></pre>

<p>And here's the set-based Haskell code:</p>

<pre><code>import Data.Set
import Data.List

main = do
    dict    &lt;- readFile "twl06.txt"
    let letters = "apricot"
    let dictWords = Data.Set.fromList $ words dict
    let perms = permutations letters
    print [x | x &lt;- perms, member x dictWords]
</code></pre>

python haskell optimization language-comparisons