Haskell执行顺序

Question

Haskell执行顺序

4

isOdd, isEven :: Int -> Bool
isOdd n
    | n<=0 = False
    | otherwise = isEven (n-1)
isEven n
    | n<0 = False
    | n==0 = True
    | otherwise = isOdd (n-1)

我不太理解这段代码，在isOdd函数中，只定义了什么是False，然后转到isEven函数，那么Haskell如何知道n是奇数呢？

- user3358850

2

没有理由将所有负整数声明为既不是偶数也不是奇数。isOdd n | n < 0 = isOdd (-n)（对于isEven同样如此）是完全合理的。 - chepner

3个回答

2

这些函数是相互递归的（每个函数都可以调用另一个函数），有基本情况。让我们通过使用isOdd来进行示例评估。首先，我将把警卫条件改为等效的if语句，以便在此答案中更加清晰（尽管我通常建议使用警卫条件）。

isOdd, isEven :: Int -> Bool
isOdd n =
  if n <= 0
    then False
    else isEven (n-1)

isEven n =
  if n < 0
    then False
    else if n == 0
           then True
           else isOdd (n-1)

现在，我们可以尝试通过一个示例评估^[1]来进行步骤:

    isOdd 3

==> if 3 <= 0                  (Applying isOdd to 5 and expanding the body)
      then False
      else isEven (3-1)

==> isEven (3-1)               (3 > 0)

==> if 2 < 0
      then False
      else if 2 == 0
             then True
             else isOdd (2-1)

==> isOdd (2-1)                (4 > 0, so the first two branches aren't taken)

==> if 1 <= 0                  (Applying isOdd to 1 and expanding the body)
      then False
      else isEven (1-1)

==> isEven 0

==> if 0 < 0
      then False
      else if 0 == 0
             then True
             else isOdd (0-1)

==> True                      (0 == 0, so the second branch is taken)

这些函数有效的直觉是：如果非负整数（自然数）n大于0，则如果它的前一个数（n-1）是偶数，则n是奇数，反之亦然。这是因为偶数和奇数交替出现。当你遇到不理解的函数（或者在本例中是一对函数）时，我建议使用像这样的小例子逐步进行评估。请注意，以下注释[1]不影响此问题，我已经稍微简化了形状为x-1的表达式被简化为相应的数字。

- David Young

抱歉，我有点困惑，"(0 == 0, 所以执行第二个分支)" 这句话的意思好像是 3 应该是偶数。 - user3358850

在这一步中，isEven被调用并传入参数0（因为它可以被2整除，所以是偶数）。第二个分支是说“如果0 == 0那么就是True...”。True是评估isOdd 3的最终结果。中间的内容是从isOdd 3到最终结果True所经过的步骤。从更高层次的角度来看，整个逻辑链类似于“要知道3是否为奇数，请查看2是否为偶数。要查看2是否为偶数，请查看1是否为奇数。要查看1是否为奇数，请查看0是否为偶数。0被“定义”为偶数（可以这么说）”。 - David Young

而且由于 0 是偶数，所以所有前面的语句都是正确的（1 是奇数，2 是偶数，最后，3 是奇数）。 - David Young

0

这被称为“相互递归”或“相互递归函数”，就像您需要定义终止状态（或退出条件）的递归函数一样。不过，您的定义并不是最好的，这里有一个更好的替代方案

isEven,isOdd :: Int -> Bool
isEven 0 = True
isEven n = isOdd  (n - 1)
isOdd  0 = False
isOdd  n = isEven (n - 1)

这里设置了终止条件为0（对称地），并且相互递归最终会在其中一个上结束。

请注意，这仅定义为非负整数，但没有通过类型Int加以强制。

您的定义也不正确，但至少对于负数将会终止。

- karakfa

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lazersmoke · Accepted Answer

这里有两个不同的函数：isOdd和isEven。它们是相互定义的：如果一个数字为负或零，则它是“非奇数”，如果比该数字少一，那么它就是“偶数”。如果一个数字为负，则它是“非偶数”，如果它为零或比该数字少一，则它是“奇数”。

这是定义这些函数的一种相当不直观的方式，但这与“执行顺序”或“求值顺序”无关。事实上，只要编译器按照Haskell报告中指定的延迟/严格语义执行计算并得出正确的结果，它就允许执行任何计算。

这些函数的更好实现如下（来自Prelude）：

even, odd       :: (Integral a) => a -> Bool
even n          =  n `rem` 2 == 0
odd             =  not . even

换句话说，如果你将一个整数型的东西除以2余数为0，则该数是偶数；否则就是奇数。

注意：上面链接中的INLINEABLE pragma只是一种优化方式，可以忽略不计。