ハスケル：Data.Set `notMember`は` notElem`より遅いですか？

Question

予想通りf1は,、f2はO（i・log i）です。ここで何が起こっているのですか？

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) 

Answer 1

これは、最適化はまだ起こっていないという理由だけです。あなたはファイル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) 

私の推測では、あなたの状況にあなたがfromAscList [2..i-1]複数回の再計算GHCiのを持っていたということです、または類似のもの。