Haskell 和懒惰

Question

我刚开始学习 Haskell，有人告诉我 Haskell 是惰性的，即它在计算表达式时做的工作尽可能少，但我认为那不是真的.

考虑一下：

und :: Bool -> Bool -> Bool
und False y = False
und y False = False

non_term x = non_term (x+1)

und (non_term 1) False 的求值永远不会终止，但很明显结果为 False。

有没有办法实现und（即德语中的and）正确（不仅仅是上面的部分）以便

und (non_term 1) False

和

und False (non_term 1)

return假的？

Answer 1

您可以为 und 编写一个完整的定义，它将适用于非终止表达式...有点像

要完成这项工作，您需要自己定义 Bool 以明确任何计算中的延迟：

import Prelude hiding (Bool(..))
data Bool = True | False | Delay Bool
  deriving (Show, Eq)

然后每当你定义一个Bool类型的值时，你必须限制自己使用共同递归，延迟是使用 Delay 构造函数明确表示，而不是通过递归，您必须在递归中计算子表达式找到顶级 return 值的构造函数。

在这个世界上，非终止值可能如下所示：

nonTerm :: Bool
nonTerm = Delay nonTerm

然后und变成：

und :: Bool -> Bool -> Bool
und False y = False
und x False = False
und True y  = y
und x True  = x
und (Delay x) (Delay y) = Delay $ und x y

效果很好：

λ und True False
False
λ und False nonTerm
False
λ und nonTerm False
False
λ case und nonTerm nonTerm of Delay _ -> "delayed" ; _ -> "not delayed"
"delayed"

跟进 , it looks like what you're looking for can be done with unamb

λ :m +Data.Unamb 
λ let undL False _ = False ; undL _ a = a
λ let undR _ False = False ; undR a _ = a
λ let und a b = undL a b `unamb` undR a b
λ und True False
False
λ und False False
False
λ und False True
False
λ und True True
True
λ und undefined False
False
λ und False undefined
False

Answer 2

Haskell确实懒。懒惰意味着除非需要，否则不评估表达式。然而，懒惰并不意味着可以以任意顺序计算两个表达式。 Haskell 中表达式的求值顺序很重要。例如，考虑您的 und 函数：

und :: Bool -> Bool -> Bool
und False y = False
und y False = False

首先，我想指出这个功能是不完整的。完整的函数为：

und :: Bool -> Bool -> Bool
und False y = False
und y False = False
und y True  = True          -- you forgot this case

其实und函数可以写得更简洁（也更偷懒）如下：

-- if the first argument is False then the result is False
-- otherwise the result is the second argument
-- note that the second argument is never inspected

und :: Bool -> Bool -> Bool
und False _ = False
und _     x = x

无论如何，Haskell中的模式匹配语法只是case表达式的语法糖。例如，您的原始（不完整）函数将被脱糖为（直到 alpha 等价）：

und :: Bool -> Bool -> Bool
und x y = case x of False -> False
                    True  -> case y of False -> False
                                       True  -> undefined

由此可见：

您的函数不完整，因为最后一个案例是 undefined。
如果第一个参数是 True，您的函数将计算第二个参数，即使它不需要。请记住，case 表达式总是强制对被检查的表达式求值。
您的函数首先检查 x，然后如果 x 的计算结果为 True，则检查 y。因此，这里确实有一个明确的评估顺序。请注意，如果 x 计算为 False，则永远不会计算 y（证明 und 确实是惰性的）。

由于这种计算顺序，您的表达式 und (non_term 1) False 出现了分歧：

  und (non_term 1) False
= case non_term 1 of False -> False
                     True  -> case False of False -> False
                                            True  -> undefined
= case non_term 2 of False -> False
                     True  -> case False of False -> False
                                            True  -> undefined
= case non_term 3 of False -> False
                     True  -> case False of False -> False
                                            True  -> undefined
                .
                .
                .
                .

如果需要，您可以创建一个具有不同求值顺序的函数：

und :: Bool -> Bool -> Bool
und x y = case y of False -> False
                    True  -> x     -- note that x is never inspected

现在，表达式 und (non_term 1) False 的计算结果为 False。但是，表达式 und False (non_term 1) 仍然存在分歧。所以，你的主要问题是：

Is there a way to implement und (i.e. and in German) correctly (not just partially as above) so that both
und (non_term 1) False
and
und False (non_term 1)
return False?

简短的回答是否定的。您总是需要特定的评估顺序；并且根据评估的顺序，und (non_term 1) False 或 und False (non_term 1) 会有所不同。

这是否意味着 Haskell 是 wrong/faulty？不。Haskell 做了正确的事情，只是没有产生任何答案。对于人类（可以并行计算两个表达式）来说，und (non_term 1) False 的结果显然必须是 False。但是，计算机必须始终具有计算顺序。

那么，实际问题是什么？在我看来，实际问题是 either/or:

平行评价。 Haskell 应该并行计算表达式的两种方式并选择最先终止的表达式：

import Data.Unamb (unamb)

type Endo a = a -> a

bidirectional :: Endo (a -> a -> b)
bidirectional = unamb <*> flip

und :: Bool -> Bool -> Bool
und = bidirectional (&&)

一般递归。以我的拙见，一般递归对于大多数用例来说过于强大：它允许你编写像 non_term x = non_term (x + 1) 这样荒谬的函数。这样的功能是非常无用的。如果我们不考虑这些无用的函数作为输入，那么你原来的 und 函数是一个非常好的函数（只需实现最后一种情况或使用 &&）。

希望对您有所帮助。

Answer 3

Is there a way to implement und (i.e. and in German) correctly (not just partially as above) so that both
und (non_term 1) False
and
und False (non_term 1)
return False?

如果您对理论感兴趣，有一个经典的理论结果表明上述函数在递归的惰性 lambda 演算（称为 PCF）中 不可能。这是 Plotkin 在 1977 年提出的。您可以在第 8 章 Winskel's notes on denotational demantics 中找到讨论 "Full Abstraction"。

即使证明涉及更多，这里的关键思想是 lambda 演算是一种顺序、确定性语言。因此，一旦惰性二元函数被输入两个布尔值（可能是底部值），它就需要决定先评估哪个，从而确定评估顺序。这将打破 or 和 and 的对称性，因为如果选择的参数发散，那么 or/and 也会发散。

正如其他人提到的，在 Haskell 中，有一个库通过非顺序方式定义 unamb，即利用底层的一些并发性，因此超出了 PCF 的能力范围。有了它，您可以定义并行 or 或 and.

Haskell 和懒惰

Haskell and laziness

haskell

termination

lazy-evaluation