0

假设我有以下程序：

foo x y = let l1 = foo 0 x
              l2 = foo 0 y
          in l1 + l2

这只是一个简单的例子，但我认为足以用于演示目的。我怎么能在每次新的（递归）调用foo时改变l1和l2中表达式的求值顺序？我知道它们在表达式内部被评估为惰性（在这种情况下是在运算符中的表达式），而不是在声明它们时，但我需要一种方法，因为可能存在程序进入无限循环的情况。如果这种无限递归发生在第二个求值参数l2上，则没有问题，因为l1总是在*l2之前求值，但如果反过来，即无限地求值l1表达式，则*l2***没有机会评估。因此，如果我可以在每个新的foo函数调用上在 ***l1*和l2表达式评估之间进行权衡，问题就会得到解决。寻找一个好的/通用的解决方案。

编辑：忘了说x或y或两者都可能是无限的结构（列表），这就是问题所在。

4

1 回答 1

1

问题

为了得到一个好的答案，我们首先需要一个具体的问题。考虑为零或另一个自然数Z的后继的自然数。S nn

data Nat = Z | S Nat

zero = Z
one  = S Z
two  = S $ S Z

在 Haskell 中，我们还可以编写无限递归数据结构，例如

infinity = S infinity

只要Nat不是单个数字，infinity我们就可以确定它是偶数还是奇数。

even :: Nat -> Bool
even  Z    = True
even (S n) = odd n

odd :: Nat -> Bool
odd  Z    = False
odd (S n) = even n

对于有限Nat的 s ，evenisTrue或is 。这没关系，但是如果我们想检查两个数字中的任何一个是否是？我们可以编写一个简单的实现：Falseeven infinityundefinedeven

eitherEven :: Nat -> Nat -> Bool
eitherEven x y = even x || even y

只要第一个参数是有限的，这就会做得很好。在下文中，even是任何偶数并且odd是任何奇数。

eitherEven even even     == True
eitherEven even odd      == True
eitherEven even infinity == True
eitherEven odd  even     == True
eitherEven odd  odd      == False
eitherEven odd  infinity == undefined

True但是当第一个参数是无限的时，即使第二个参数是无限的，它也不会返回Even

eitherEven infinity even     == undefined -- this should be True
eitherEven infinity odd      == undefined
eitherEven infinity infinity == undefined

一个简单的解决方案

该问题的一个简单解决方案是在测试第一个参数和测试第二个参数之间交替进行。当我们递归调用函数时，我们交换参数以交替测试两个参数中的哪一个。

eitherEven :: Nat -> Nat -> Bool
eitherEven Z         _ = True
eitherEven (S Z)     y = even y 
eitherEven (S (S x)) y = eitherEven y x

即使第一个参数不是有限的，这也具有所需的输出。

> eitherEven infinity two
True

对于参数未对称处理的更复杂的问题，您可以传递一个Bool标志并在每个步骤中翻转它。一般来说，您可以使用任何状态机来跟踪您在哪里工作。

这个解决方案不是很令人满意，因为当我们想要测试三个数字中的任何一个是否为偶数时，它并不能立即解决要做什么。为此，我们需要编写一个新函数。

anyEven3 :: Nat -> Nat -> Nat -> Bool
anyEven3 Z         _ _ = True
anyEven3 (S Z)     y z = eitherEven y z
anyEven3 (S (S x)) y z = anyEven3 y z x

我们放在x最后是因为我们想同时尝试y，z然后x再试一次。我们正在排队。如果我们可以证明队列中的第一件事产生了结果，那么True我们就完成了。如果我们可以证明队列中的第一件事没有产生结果，我们将其从队列中移除并使用适用于较小输入集的版本。如果我们不能决定队列中第一件事的结果，我们把它放在最后。可以看到相同的模式，eitherEven其中接受两个参数，甚至even只接受一个参数。

anyEven :: [Nat] -> Bool
anyEven = go []
    where
        go [] [] = False
        go r  [] = go [] (reverse r)
        go r (      Z  :_ ) = True
        go r (    S Z  :ns) = go r     ns
        go r ((S (S x)):ns) = go (x:r) ns
于 2015-02-07T19:05:32.833 回答