Почему этот код на Haskell такой медленный?

Я новичок в Haskell и пытался создать решатель Scrabble.

Вы можете существенно улучшить ситуацию, используя лучший алгоритм.

Вместо того, чтобы проверять каждую перестановку входных букв, если вы сначала отсортируете их, вы можете сделать только один поиск в словаре и получить все возможные слова (анаграммы), которые могут быть образованы из них (используя их все).

Вот код, который создает этот словарь как Data.Map. Создание карты связано с начальными затратами, но после первого запроса последующие поиски выполняются очень быстро.

import Data.List
import qualified Data.Map.Strict as Map
import Control.Monad
import System.IO

main = do
  contents <- readFile "words"
  let pairs = [ (sort w, [w]) | w <- words contents ]
      dict = foldl' (\m (k,v) -> Map.insertWith (++) k v m) Map.empty pairs
      -- dict = foldr (\(k,v) m -> Map.insertWith (++) k v m) Map.empty pairs
  forever $ do
    putStr "Enter letters: " >> hFlush stdout
    letters <- getLine
    case Map.lookup (sort letters) dict of
      Nothing -> putStrLn "No words."
      Just ws -> putStrLn $ "Words: " ++ show ws

Время создания карты для ворд-файла размером 236К слов (2,5 МБ) составляет около 4-5 секунд. Более высокая производительность, вероятно, возможна при использовании ByteStrings или Text вместо Strings.

Несколько хороших комбинаций букв, которые стоит попробовать:

steer rat tuna lapse groan neat

Примечание. Используя GHC 7.10.2, я обнаружил, что этот код работает лучше без компиляции с параметром -O2.

Проверка, является ли x элементом dictWords, вероятно, будет очень медленной. Я бы предположил, что ваша аналогичная реализация Python хранит dictWords в наборе или отсортированном векторе (в последнем случае с использованием двоичного поиска)? Похоже, вы, вероятно, хотите сделать то же самое здесь.

Используя этот список слов и приведенный ниже код, версия Python запускается примерно за 30 секунд. , а версия на Haskell — 1,5 минуты. Таким образом, Haskell медленнее (возможно, потому, что он использует связанный список, который при прочих равных условиях медленнее перебирает), но я бы не назвал его «невероятно медленным» по сравнению с Python. Переключение на использование набора в любой версии сокращает время до менее 1 секунды.

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]

А вот код на Haskell, основанный на наборах:

import Data.Set
import Data.List

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