使用未反转的累加器进行递归 - 是否可能？

Question

我最近一直在玩Haskell相当数量,我想出了这个函数来找到第n个素数:

nthPrime 1 = 2
nthPrime 2 = 3
nthPrime n = aux [2, 3] 3 5 n
  where
    aux knownPrimes currentNth suspect soughtNth =
      let currentIsPrime = foldl (\l n -> l && suspect `mod` n /= 0) 
                                 True knownPrimes
      in case (currentIsPrime, soughtNth == currentNth) of
        (True, True) -> suspect
        (True, False) -> aux (suspect:knownPrimes) (currentNth + 1) 
                             (suspect + 2) soughtNth
        _ -> aux knownPrimes currentNth (suspect + 2) soughtNth

我的问题是,有没有办法让累积参数(在这种情况下knownPrimes)不反转(通过时发生(suspect:knownPrimes))？

我尝试过使用,knownPrimes ++ [suspect]但这似乎效率低下.

我希望如果我能按顺序传递已知的素数,那么我可以进一步快速进行一些素数检查.

Answer 1

在Haskell中,如果您使用累加器来构建列表,但最终不得不反转它,通常情况下最好丢弃累加器,而是在计算结果时懒得生成列表.

如果你应用这种思维来搜索素数,并充分利用懒惰,你最终会得到一种众所周知的技术,可以产生所有素数的无限列表.如果我们尽可能少地重构你的代码来使用这种技术,我们得到类似的东西:

allPrimes = [2, 3] ++ aux 5
  where
    aux suspect =
      let currentIsPrime = foldl (\l n -> l && suspect `mod` n /= 0) True
                               $ takeWhile (\n -> n*n <= suspect) allPrimes
      in case currentIsPrime of
        True -> suspect : aux (suspect + 2)
        False -> aux (suspect + 2)

nthPrime n = allPrimes !! (n-1)

我已经删除了现在不必要的参数,并将代码从累积变为懒惰生成,并使用自己的结果作为主要除数的来源进行测试(这称为"打结").除此之外,这里唯一的变化是添加一个takeWhile检查:因为我们测试除数的列表是根据自身定义的,并且无限启动,我们需要知道列表中的哪个位置停止检查除数以便我们没有得到真正无限的递归.

除此之外,此代码效率低下:

foldl (\l n -> l && suspect `mod` n /= 0) True

不以检查是否存在没有除数列表中的一个好办法,因为书面,它不会停止一旦除数已经发现,即使&&本身shortcutting(只要它的第一个参数被发现是停False) .

为了允许正确的快捷方式,foldr可以使用a代替:

foldr (\n r -> suspect `mod` n /= 0 && r) True

或者,更好的是,使用预定义的功能all:

all (\n -> suspect `mod` n /= 0)

用我的评论

如果你all稍微使用和重构它会是这样的:

allPrimes :: [Integer]
allPrimes = 2 : 3 : aux 5
  where
    aux suspect 
      | currentIsPrime = suspect : nextPrimes
      | otherwise      = nextPrimes
      where
          currentIsPrime =
            all (\n -> suspect `mod` n /= 0)
            $ takeWhile (\n -> n*n <= suspect) allPrimes
          nextPrimes = aux (suspect + 2) 

nthPrime :: Int -> Integer
nthPrime n = allPrimes !! (n-1)