我正在阅读《Learn You a Haskell》(迄今为止非常喜欢),它教我们如何使用lambda和foldl
实现elem
。然而,使用lambda的解决方案对我来说有些丑陋,因此我尝试想出另一种实现方式(全部使用foldl
):
import qualified Data.Set as Set
import qualified Data.List as List
-- LYAH implementation
elem1 :: (Eq a) => a -> [a] -> Bool
y `elem1` ys =
foldl (\acc x -> if x == y then True else acc) False ys
-- When I thought about stripping duplicates from a list
-- the first thing that came to my mind was the mathematical set
elem2 :: (Eq a) => a -> [a] -> Bool
y `elem2` ys =
head $ Set.toList $ Set.fromList $ filter (==True) $ map (==y) ys
-- Then I discovered `nub` which seems to be highly optimized:
elem3 :: (Eq a) => a -> [a] -> Bool
y `elem3` ys =
head $ List.nub $ filter (==True) $ map (==y) ys
我在 GHCi 中加载了这些函数并执行了 :set +s
,然后进行了一个小型基准测试:
3 `elem1` [1..1000000] -- => (0.24 secs, 160,075,192 bytes)
3 `elem2` [1..1000000] -- => (0.51 secs, 168,078,424 bytes)
3 `elem3` [1..1000000] -- => (0.01 secs, 77,272 bytes)
然后我尝试在一个(远远)更大的列表上执行同样的操作:
3 `elem3` [1..10000000000000000000000000000000000000000000000000000000000000000000000000]
elem1
和elem2
花费了很长时间,而elem3
瞬间完成(几乎与第一个基准测试相同)。我认为这是因为GHC知道3
是[1..1000000]
的成员,而我在第二个基准测试中使用的大数字比1000000
还要大,因此3
也是[1..bigNumber]
的成员,GHC根本不需要计算表达式。但是,它如何能够自动缓存(或记忆化,一种Lisp之地教给我的术语)
elem3
而不是另外两个?
y
变得越大时,elem3
变得越来越慢,而ys
保持不变。 - chepner