哈斯克尔懒惰的评价

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"

[('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,正确评估函数而不引发异常:没有发生除零.

Answer 2

所有的.

因为StackOverflow不会让我发布这样一个简短的答案:如果你正在寻找的东西不在那里,你就不能完成比查看整个列表更少的工作.

编辑:问题现在要求更有趣的东西.简短的回答是我们将构建列表:

('a',0):('b',1):('c',2):('d',3):('X',4):<thunk>

(实际上,这个答案只是有点微妙.你的类型签名使用单态返回类型Int,基本上所有操作都是严格的,所以上面元组中的所有数字都将被完全评估.Num你肯定会实现它们的实现但是会得到更多的东西.)

Answer 3

您可以通过undefined在这里和那里引入s 来轻松回答这样的问题.在我们的例子中,改变我们的输入就足够了:

find_first_occurrence 'X' ("abcdX" ++ undefined)

你可以看到它产生了结果,这意味着它甚至看不到它找到的'X'(否则它会抛出异常).显然,如果不查看原始列表,就无法构建压缩列表.

另一种(可能不太可靠)分析懒惰的方法是使用以下trace函数Debug.Trace:

> let find_first_occurrence elem list = (snd . head) [x | x <- map (\i -> trace (show i) i) $ zip list [0..], fst x == elem]
> find_first_occurrence 'X' "abcdXkjdkljklfjdlfksjdljjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj"

打印

('a',0)
('b',1)
('c',2)
('d',3)
('X',4)
4