Map.Map против функции

Question

Почему в этой ситуации использование конструкторов данных и функции медленнее, чем использование Строк и Карты?

Редактировать: Обратите внимание на мой второй комментарий к ответу Ротсора, он объясняет, почему я принял ответ nulvinges.

Работает медленно:

module Main where

import qualified Data.List as List

main :: IO ()
main = do
    print $ conspire fabFive fabFive

-- here i actually have 80 constructors
data Eris = Hera | Athene | Aphrodite | Paris | Helene
            deriving (Ord, Eq, Show, Read, Enum, Bounded)

fabFive = [minBound..maxBound] :: [Eris]

conspire :: [Eris] -> [Eris] -> [Eris]
conspire [Hera]   [Hera]   = [Hera, Athene]
...
conspire [Hera]   [Helene] = [Athene, Aphrodite, Paris]
...
conspire [Helene] [Helene] = [Hera]

conspire [a] (b:bs) =
    List.union (conspire [a] [b]) (conspire [a] bs)
conspire (a:as) ls =
    List.union (conspire [a] ls) (conspire as ls)

Работает быстрее:

module Main where

import qualified Data.Map as Map
import qualified Data.Set as Set

main :: IO ()
main = do 
    print $ conspire (Set.fromList fabFive) (Set.fromList fabFive)

fabFive = [ Hera, Athene, Aphrodite, Paris, Helene ]

conspire :: Set.Set String -> Set.Set String -> Set.Set String
conspire set1 set2 = Set.fold Set.union Set.empty $ Set.map
    (\x -> Set.fold Set.union Set.empty $ Set.map
        (\y -> conspiracy Map.! (Set.singleton x, Set.singleton y))
        set2
    )
    set1

conspiracy = Map.fromList
    [ ( (Set.singleton "Hera" , Set.singleton "Hera" )
      , Set.fromList [ "Hera", "Athene" ]
      )
    ...
    , ( (Set.singleton "Hera" , Set.singleton "Helene" )
      , Set.fromList [ "Athene", "Aphrodite", "Paris" ]
      )
    ...
    , ( (Set.singleton "Helene" , Set.singleton "Helene" )
      , Set.fromList [ "Hera" ]
      )
    ]

Answer 1

Ваша первая версия работает медленно из-за функции List.nub, которая очень неэффективна. Он работает в O(N^2) времени, при этом N является размером списка. Во всем остальном будет доминировать nub для больших N.

Answer 2

Карта создает хэш-карту с O (1), но с функцией вы должны проверять каждое условие.

Редактировать: Это на самом деле неправильно. Карта является двоичным деревом со сбалансированным размером, но оно должно дать заговору сложность O (logn), тогда как функция должна проверять каждую комбинацию и, следовательно, имеет сложность O (n).

Помните, как работает сопоставление с образцом:

f 0 = 0
f i = 1+f (i-1)

Является синтаксическим сахаром для:

f i = if i == 0
      then 0
      else 1+f (i-1)

Вы по существу делаете O (n) сравнений, чтобы найти, какую функцию вы хотите выполнить.

В Map он выполняет поиск в двоичном дереве и выполняет только O (logn) сравнений.