1

所以我正在编写一个程序来在haskell中生成一个素数列表。我创建了如下所示的两个函数：

{-
Given a list of prime numbers, this function will
add the next prime number to the list. So, given the 
list [2, 3], it will return [2, 3, 5]
-}
nextPrime xs =  xs ++ [lastVal + nextCounts]
    where
        lastVal       =  (head . reverse) $ xs
        isNextPrime y =  0 `elem` ( map ( y `mod`) xs )
        nextVals      =  (map isNextPrime [lastVal, lastVal+1 ..] )
        nextCounts    =  length $ takeWhile (\x -> x) nextVals


allPrimes xs = allPrimes np
    where 
        np = nextPrime xs

现在函数“nextPrime”正在做它应该做的事情。但是，当我调用 allPrimes 时，如下所示：

take 5 $ allPrimes [2,3]

程序进入无限循环。我认为 Haskells 的“懒惰”功能应该解决所有这些问题？我错过了什么？？

4

3 回答 3

3

如果你开始在纸上评估这个表达式，你就会明白为什么懒惰在这里没有帮助。从你的表达开始：

take 5 $ allPrimes [2,3]

首先，尝试计算 allPrimes 表达式：

allPrimes [2, 3]

变成

allPrimes np
    where 
        np = nextPrime [2, 3]

将where子句中的内容放入表达式中，它变成

allPrimes (nextPrime [2, 3])

现在，评估nextPrime [2, 3]（你可以这样做，ghci因为该函数有效）和 get [2, 3, 5]，你可以在前面的表达式中替换它，它变成

allPrimes [2, 3, 5]

重复上述，它变成

allPrimes [2, 3, 5, 7]

还有你的问题！allPrimes从未评估为任何值，它评估为allPrimes应用于越来越长的列表。要查看惰性在哪里起作用，请尝试在纸上评估类似以下的zip函数Prelude：

zip :: [a] -> [b] -> [(a,b)]
zip (a:as) (b:bs) = (a,b) : zip as bs

zip [1, 2, 3] ['a', 'b', 'c']

a变成1，as变成[2, 3]，b变成'a'，bs变成，['b', 'c']所以你得到

(1, 'a') : zip [2, 3] ['b', 'c']

这里的区别是有一个带有值的列表，然后列表的其余部分是一个表达式。在你的allPrimes函数中，你只是不断得到更多的表达式。

有关更多信息，请查看弱头范式，但是如果您是 Haskell 的新手，我建议您先熟悉语法和“在 Haskell 中思考”的基础知识，然后再开始研究 WHNF 之类的东西。

于 2013-09-29T17:23:12.600 回答
1

I'd read Drew's answer for a good explanation of what's going wrong, but for a quick demonstration for how to make this work,

nextPrime xs =  xs ++ [lastVal + nextCounts]
  where
    lastVal       =  (head . reverse) $ xs
    isNextPrime y =  0 `elem` ( map ( y `mod`) xs )
    -- ^ Style note, this name is super misleading, since it returns
    -- false when the number is prime :)
    nextVals      =  (map isNextPrime [lastVal, lastVal+1 ..] )
    nextCounts    =  length $ takeWhile (\x -> x) nextVals


allPrimes xs = last np : allPrimes np
  where np = nextPrime xs

Now we're constructing the list as we go, and haskell is lazy so it can grab the last element of np before evaluating the allPrimes np. In other words head (a : infiniteLoop) is a, not an infinite loop.

However this is really innefficient. Lists are singly linked in Haskell so last is O(n) as opposed to O(1) in something like Python. And ++ is also costly, O(n) for the length of the first list.

Instead

 nextPrime xs = lastVal + nextCounts
   where lastVal     = head xs
         isNextPrime = 0 `elem` map (y `rem`) xs
         nextVals    = map isNextPrime [lastVal ..]
         nextCount   = length $ takeWhile id nextVals

 allPrimes xs = p : allPrimes (p:xs)
    where p = nextPrime xs

So we keep the list reversed to avoid those costly traversals. We can also simplify nextPrime

import Data.Maybe
nextPrime xs = fromJust nextPrime
  where isPrime y =  not $ 0 `elem` map (rem y) xs
        nextPrime = find isPrime [head xs ..]

Where we just search the list for the first element which is prime and add it to our list. The fromJust is normally bad, if there were no next primes we'd get an error. But since we know mathematically that there will always be a next prime, this is safe.

In the end, the code looks like

 import Data.Maybe
 import Data.List
 nextPrime xs = fromJust nextPrime
   where isPrime y = 0 `notElem` map (rem y) xs
         nextPrime = find isPrime [head xs ..]
 allPrimes xs = p : allPrimes (p:xs)
   where p = nextPrime xs

To evaluate it, call allPrimes [2].

An even cleaner way to do this would be to have a function isPrime that returns whether a number is prime or not. And then just to have

allPrimes = filter isPrime [1..]

But I'll leave that to the curious reader.

于 2013-09-29T17:56:32.283 回答
0

正如 Drew 指出的那样，您的函数allPrimes不会从懒惰中受益，因为我们永远无法访问它计算的内容。这是因为我们要查看的列表是 allPrimes 的参数，而不是返回值。

所以我们需要公开 allPrimes 正在构建的列表，并且仍然保留一个函数调用，它将无限地构建这个列表的以下值。

好吧，由于 allPrimes 是对自身的一遍又一遍的重新应用，我们只需要一个公开中间值的函数。我们有一个！

 iterate f a == [a, f (f a),...]

因此，使用 iterate 和 nextPrime，我们可以构建以下（相当奇怪的）函数：

-- nextPrime renamed as nextPrimeList
infiniteListofListofPrimes =  iterate nextPrimeList [2,3]
primeN n =   (infiniteListofListofPrimes !! n) !! n
takeN n  =  take n (infiniteListofListofPrimes !! n)

我们正在生成我们的素数，但它看起来并不好。我们宁可有 [primes]，不要多余[[some primes]]。

下一步是在 WHNF 上构建列表：

elem1:elem2:aux
where aux = newvalue:aux

Whereaux将计算新值并为下一个保留所有内容。

为此，我们需要nextPrime坚持生成一个新的素数：

nextPrime xs = lastVal + nextCounts

并找到aux可以listOfPrimes永远建造的东西。

我想出了这个：

  infiniteListofPrimes = 2:3:aux 2
       where aux n  = nextPrime (take n infiniteListofPrimes):(aux (n+1))
于 2013-09-29T19:00:15.737 回答