学习Haskell：看似循环的程序 - 请帮忙解释一下 [英] Learning Haskell: Seemingly Circular Program - Please help explain
问题描述
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。虽然本书确实提供了这个解释，为什么程序执行和终止：
ldp调用primes1，列表质数。这是懒惰列表的第一个例子。该列表被称为懒惰，因为我们只计算列表中需要进一步处理的部分。为了定义素数1，我们需要一个素数测试，但是这个测试本身是用函数LD来定义的，函数LD反过来指的是素数1。我们似乎在一个圈子里跑来跑去。这个圈可以通过避免2的素数检验而变得非恶性。如果给定2是素数，那么我们可以在LD检查中使用2的素数，其中3是素数，等等，然后我们就可以并运行
尽管我认为我理解了这个解释，但如果有人可以用外行的话来解释，我将不胜感激：
- 什么是懒惰列表，以及它如何应用于这种情况？
- 如何知道2是总理可以让程序变得非恶性？
任何答案都是非常感谢。
首先要注意的是，代码本身并不会执行任何操作。这只是一堆数学表达式，它直到我们尝试从它们中提取一些值才是循环的。我们怎么做？
我们可以这样做：
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:
ldp makes a call to primes1, the list of prime numbers. This is a first illustration of a ‘lazy list’. The list is called ‘lazy’ because we compute only the part of the list that we need for further processing. To define primes1 we need a test for primality, but that test is itself defined in terms of the function LD, which in turn refers to primes1. We seem to be running around in a circle. This circle can be made non-vicious by avoiding the primality test for 2. If it is given that 2 is prime, then we can use the primality of 2 in the LD check that 3 is prime, and so on, and we are up and running
While I think I understand this explanation, I would greatly appreciate it if someone could explain in laymen's terms:
- What a "lazy list" is and how it applies in this context?
- How knowing that 2 is prime allows the program to be non-vicious?
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 these
expressions manageable, I'm now ignoring the print and take parts, but
remember 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 get stuck. 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's
expand 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 value to 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 large and 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, and the 2 helps because it ensures that when we reach the recursive step we always have enough values already calculated. (Imagine expanding that expression if we didn't know the 2, we'd end up stuck in a loop pretty quickly.)
这篇关于学习Haskell：看似循环的程序 - 请帮忙解释一下的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
