haskell - Haskell:Data.Set`notMember`比`notElem`慢吗？

我希望f1是O（i²），而f2是O（i loglogi）。这里发生了什么？

import Data.Set

i = 20000

-- should be slow
f1 = [ x | x <- [1..i] , x `notElem` [2..i-1] ]
-- should be fast
f2 = [ x | x <- [1..i] , x `notMember` fromAscList [2..i-1] ]

ghci输出：

*Main> f1
[1,20000]
(7.12 secs, 16,013,697,360 bytes)
*Main> f2
[1,20000]
(44.27 secs, 86,391,426,456 bytes)

最佳答案

这仅仅是因为尚未进行优化。如果将以下内容放入文件F.hs：

module F (f1,f2) where

import Data.Set

-- should be slow
f1 :: Int -> [Int]
f1 i = [ x | x <- [1..i] , x `notElem` [2..i-1] ]
-- should be fast
f2 :: Int -> [Int]
f2 i = [ x | x <- [1..i] , x `notMember` fromAscList [2..i-1] ]

并首先通过优化对其进行编译，您将获得以下内容：

$ ghc -O2 F.hs       # compile with optimizations
[1 of 1[ Compiling F            ( F.hs, F.o )

$ ghci F.hs          # now load it up in GHCi
GHCi, version 8.0.1: http://www.haskell.org/ghc/  :? for help
Ok, modules loaded: F (F.o)
Prelude F> :set +s
Prelude F> f1 20000
[1,20000]
(2.16 secs, 2,030,440 bytes)
Prelude F> f2 20000
[1,20000]
(0.05 secs, 4,591,312 bytes)

我的猜测是，在您的情况下，您使GHCi多次重新计算fromAscList [2..i-1]或类似的结果。