问题描述
目前我正在阅读由Doets和Van Eijck撰写的书籍The Haskell Road to Logic，Math，and Programming。在本书出版之前，我从未接触过任何函数式编程语言，所以请牢记。测试：ldp :: Integer - >整数
ldp n = ldpf primes1 n
ldpf :: [Integer] - >整数 - >整数
ldpf（p：ps）n | rem n p == 0 = p
| p ^ 2> n = n
|否则= ldpf ps n
primes1 :: [Integer]
primes1 = 2：filter prime [3 ..]
prime :: Integer - > Bool
prime n | n< 1 =错误不是正整数
| n == 1 = False
|否则= ldp n == n
有一个看似循环的编程，其中ldp调用primes1，它调用prime，它再次调用ldp。虽然本书确实提供了这个解释，为什么程序执行和终止：
尽管我认为我理解了这个解释，但如果有人可以用外行的话来解释，我将不胜感激：
任何答案都是非常感谢。
首先要注意的是，代码本身并不会执行任何操作。这只是一堆数学表达式，它直到我们尝试从它们中提取一些值才是循环的。我们怎么做？
我们可以这样做：
print $ take 1 primes1
这里没有问题。我们可以在不查看任何递归代码的情况下获取primes1的第一个值，它显式地为2.那么：
print $ take 3 primes1
让我们试着展开 primes1 获取一些值。为了让这些
表达式易于管理，我现在忽略了 print 和带部分，但是
请记住，我们只是因为它们才做这项工作。 primes1 是：
primes1 = 2：filter prime [3 .. ]
我们有我们的第一个值，第二步是扩展过滤器。
如果这是一种严格的语言，我们会尝试首先扩展[3 ..]，并获得
卡住。过滤器的一个可能的定义是：
pre $ filter f（x：xs）= if fx then x：filter f xs else filter f xs
给出：
primes1 = 2：if prime 3 then 3：filter prime [4 ..] else filter prime [4 ..]
我们下一步必须弄清楚 prime 3 是true还是false，所以让我们用
展开它定义 prime ， ldp 和 ldpf 。
primes1 = 2：if ldp 3 == 3 then 3：filter prime [4 ..] else filter prime [4 ..]
primes1 = 2：if ldpf primes1 3 == 3 then 3：filter prime [4 ..] else filter prime [4 ..]
现在，事情变得有趣了，primes1引用它自己，ldpf需要第一个值
来完成它的计算。
$ b
primes1 = 2：if ldpf（2：tail primes）3 == 3然后3：filter prime [4 ..] else filter prime [4 ..]
现在，我们在ldpf中应用guard子句并找到 2 ^ 2> 3 ，因此 ldpf（2：尾数）3 = 3 。
primes1 = 2：if 3 == 3 then 3：filter prime [4 ..] else filter prime [4 ..]
primes1 = 2：3：filter prime [4。 。]
我们现在拥有第二个值。请注意，我们评估的右侧从来没有增长过特别大的
，并且我们从来没有必要非常注意递归循环。
primes1 = 2：3：if prime 4 then 4：filter prime [5 ..] else filter prime [5 ..]
primes1 = 2：3：if ldp 4 == 4 then 4： filter prime [5 ..] else filter prime [5 ..]
primes1 = 2：3：if ldpf primes1 4 == 4 then 4：filter prime [5 ..] else filter prime [5 ..]
primes1 = 2：3：if ldpf（2：tail primes1）4 == 4 then 4：filter prime [5 ..] else filter prime [5 ..]
我们使用guard子句 rem 4 2 == 0 ，因此我们在这里得到2。
primes1 = 2：3：if 2 == 4 then 4：filter prime [5 ..] else filter prime [5 ..]
primes1 = 2：3：过滤素数[5 ..]
primes1 = 2：3：如果素数5然后5：过滤素数[6 ..] else filter prime [6 ..] ]
primes1 = 2：3：if ldp 5 == 5 then 5：filter prime [6 ..] else filter prime [6 ..]
primes1 = 2 ：3：if ldpf primes1 5 == 5 then 5：filter prime [6 ..] else filter prime [6 ..]
primes1 = 2：3：if ldpf（2：tail primes）5 == 5然后5：filter prime [6 ..] else filter prime [6 ..]
，所以我们递归：
primes1 = 2：3：if ldpf（tail primes）5 == 5 then 5：filter prime [6 ..] else filter prime [6 ..]
primes1 = 2：3：if ldpf（3：tail（tail primes））5 == 5 then 5：filter prime [6 ..] else filter prime [6 ..]
现在 3 ^ 2> 5 以便表达式为5。
primes1 = 2：3：if 5 == 5 then 5：filter prime [6 ..] else filter prime [6 ..]
primes1 = 2：3：5：filter prime [6 ..]
我们只需要三个值，所以评估可以停止。
所以，现在来回答你的问题。一个懒惰的列表只需要我们评估我们需要什么，和2帮助我们，因为它确保了当我们到达递归步骤时，我们总是有足够的值计算
。 （想象一下，如果我们不知道2的话，扩展这个表达式，我们最终会很快陷入一个相当于
的循环中。）
I'm currently going through the book "The Haskell Road to Logic, Math, and Programming" by Doets and Van Eijck. I've never been exposed to any functional programming language until this book, so keep that in mind.
Still early in the book, it gives the following code for a primality test:
ldp :: Integer -> Integer
ldp n = ldpf primes1 n
ldpf :: [Integer] -> Integer -> Integer
ldpf (p:ps) n | rem n p == 0 = p
| p^2 > n = n
| otherwise = ldpf ps n
primes1 :: [Integer]
primes1 = 2 : filter prime [3..]
prime :: Integer -> Bool
prime n | n < 1 = error "not a positive integer"
| n == 1 = False
| otherwise = ldp n == n
There is a seemingly circular programming going on in that ldp calls primes1, which calls prime, which calls ldp again. While the book does offer this as an explanation as to why the program executes and terminates:
While I think I understand this explanation, I would greatly appreciate it if someone could explain in laymen's terms:
Any answers are greatly appreciated.
The first thing to note is that on its own that code does nothing. It's just a bunch of mathematical expressions and it doesn't matter how circular it is until we try to extract some values from them. How do we do that?
We could do:
print $ take 1 primes1
There's no problem here. We can take the first value of primes1 without looking at any of the recursive code, it's there explicitly as 2. What about:
print $ take 3 primes1
Let's try expanding primes1 to get some values out. To keep theseexpressions manageable, I'm now ignoring the print and take parts, butremember that we're only doing this work because of them. primes1 is:
primes1 = 2 : filter prime [3..]
We have our first value, and the first step to our second is expanding filter.If this were a strict language we would try to expand [3..] first and getstuck. A possible definition of filter is:
filter f (x:xs) = if f x then x : filter f xs else filter f xs
which gives:
primes1 = 2 : if prime 3 then 3 : filter prime [4..] else filter prime [4..]
Our next step has to be figuring out if prime 3 is true or false, so let'sexpand it using our definitions of prime, ldp and ldpf.
primes1 = 2 : if ldp 3 == 3 then 3 : filter prime [4..] else filter prime [4..] primes1 = 2 : if ldpf primes1 3 == 3 then 3 : filter prime [4..] else filter prime [4..]
Now, things get interesting, primes1 references itself and ldpf needs the first valueto do its calculation. Luckily, we can get the first value easily.
primes1 = 2 : if ldpf (2 : tail primes) 3 == 3 then 3 : filter prime [4..] else filter prime [4..]
Now, we apply the guard clauses in ldpf and find 2^2 > 3, therefore ldpf (2 : tail primes) 3 = 3.
primes1 = 2 : if 3 == 3 then 3 : filter prime [4..] else filter prime [4..] primes1 = 2 : 3 : filter prime [4..]
We now have our second value. Note that the right hand side of our evaluation never grew especially largeand that we never needed to follow the recursive loop very far.
primes1 = 2 : 3 : if prime 4 then 4 : filter prime [5..] else filter prime [5..] primes1 = 2 : 3 : if ldp 4 == 4 then 4 : filter prime [5..] else filter prime [5..] primes1 = 2 : 3 : if ldpf primes1 4 == 4 then 4 : filter prime [5..] else filter prime [5..] primes1 = 2 : 3 : if ldpf (2 : tail primes1) 4 == 4 then 4 : filter prime [5..] else filter prime [5..]
We use the guard clause rem 4 2 == 0, therefore we get 2 here.
primes1 = 2 : 3 : if 2 == 4 then 4 : filter prime [5..] else filter prime [5..] primes1 = 2 : 3 : filter prime [5..] primes1 = 2 : 3 : if prime 5 then 5 : filter prime [6..] else filter prime [6..] primes1 = 2 : 3 : if ldp 5 == 5 then 5 : filter prime [6..] else filter prime [6..] primes1 = 2 : 3 : if ldpf primes1 5 == 5 then 5 : filter prime [6..] else filter prime [6..] primes1 = 2 : 3 : if ldpf (2 : tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
No guard matches, so we recurse:
primes1 = 2 : 3 : if ldpf (tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..] primes1 = 2 : 3 : if ldpf (3 : tail (tail primes)) 5 == 5 then 5 : filter prime [6..] else filter prime [6..]
Now 3^2 > 5 so that expression is 5.
primes1 = 2 : 3 : if 5 == 5 then 5 : filter prime [6..] else filter prime [6..] primes1 = 2 : 3 : 5 : filter prime [6..]
We only need three values, so evaluation can stop.
So, now to answer your questions. A lazy list is one that only requires us to evaluate what we need, andthe 2 helps because it ensures that when we reach the recursive step we always have enough values alreadycalculated. (Imagine expanding that expression if we didn't know the 2, we'd end up stuck in a loop prettyquickly.)
这篇关于学习Haskell：看似循环的程序 - 请帮忙解释一下的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！