Haskell 惰性求值

Question

如果我调用以下 Haskell 代码

find_first_occurrence :: (Eq a) => a -> [a] -> Int
find_first_occurrence elem list = (snd . head) [x | x <- zip list [0..], fst x == elem]

与论点

'X' "abcdXkjdkljklfjdlfksjdljjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj"

压缩 list 有多少 [('a',0), ('b',1), ]即将建成？

更新:

我试着跑

find_first_occurrence 10 [1..]

并返回 9几乎立即，所以我想它至少在简单的情况下确实使用了惰性求值？当我运行时，答案也会“立即”计算

let f n = 100 - n
find_first_occurrence 10 (map f [1..])

Answer 1

简短回答:它将仅根据您正在搜索的元素构建。这意味着只有在最坏的情况下，您才需要构建整个列表，即没有元素满足条件。

长答案:让我用一对例子来解释原因:

ghci> head [a | (a,b) <- zip [1..] [1..], a > 10]
11

在这种情况下， zip 应该生成一个无限列表，但是惰性使 Haskell 最多只能构建到 (11,11)。 :如您所见，执行并没有发散，但实际上给了我们正确的答案。

现在，让我考虑另一个问题:

ghci> find_first_occurrence 1 [0, 0, 1 `div` 0, 1]
*** Exception: divide by zero
ghci> find_first_occurrence 1 [0, 1, 1 `div` 0, 0]
1
it :: Int
(0.02 secs, 1577136 bytes)

由于没有构建整个压缩列表，haskell 显然甚至不会评估列表中出现的每个表达式，因此当元素在 div 1 0 之前时，该函数被正确评估而不会引发异常:没有发生被零除。