Haskell 的懒惰和列表理解。完成条件

Question

foo s1 s2 = null ([x | x <- s2, x == s1])

请说明这个功能什么时候结束？

Haskell会先遍历整个列表，然后检查null，还是当出现一个元素时，他会检查null并完成迭代？如果是第一个选项，那怎么才能更偷懒呢？

Answer 1

Will Haskell first iterate through the entire list and then check for null.

否。 null 检查它是否为空列表，returns True 用于空列表 []，False 用于 (:) 数据构造函数. “老”null is implemented as [src]:

null                    :: [a] -> Bool
null []                 =  True
null (_:_)              =  False

因此它将评估列表理解为 head normal form (HNF)，一旦它知道外部数据构造函数，它就可以 return True或 False：它不会检查第一个元素是什么，所以如果这是一个昂贵的表达式，它也不会在那个上浪费时间。

null :: t a -> Bool
null = foldr (\_ _ -> False) True

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

因此，这也将简单地检查外部数据构造函数是空列表 [] 还是“cons” (:) 因为在这种情况下 k returns True 对参数不感兴趣。

列表理解也是惰性的：它们只会在必要时评估外部数据构造函数，并在必要时构造头部和尾部。您的列表理解被脱糖为：

concatMap (\x -> if x == s1 then [x] else []) s2

如果因此必须评估列表的外部数据构造函数，它将遍历 s2，如果 x == s1 则它将生成外部数据构造函数“cons”，然后 null 因此可以使用它来确定列表是否为空。

这意味着从 s2 中 x == s1 找到元素 x 的那一刻起，它将 return False.

Laziness of Haskell and list comprehension. Completion condition