ocaml - 在不炸毁堆栈的情况下生成素数

Question

我正在学习 OCaml(请原谅我的风格)，并且正在尝试编写一个函数来生成不超过某个上限的素数列表。我已经设法通过几种不同的方式做到这一点，所有这些方式都有效，直到您将它们扩展到相对较高的上限。

如何更改这些(其中任何一个)以使递归不会填满堆栈？我以为我的 while 循环版本可以实现这一点，但显然不是!

生成器

let primes max =
  let isPrime p x =
    let hasDivisor a = (x mod a = 0) in
    not (List.exists hasDivisor p) in

  let rec generate p test =
    if test < max then
      let nextTest = test + 2 in
      if isPrime p test then generate (test :: p) nextTest
                        else generate p nextTest
    else p in

  generate [5; 3; 2] 7;;

这是我最成功的解决方案，因为它在运行 primes 2000000;; 时不会立即溢出堆栈。但是它只是坐在那里消耗 CPU；我只能假设它最终会完成!以下备选方案均存在栈溢出问题:

Eratosthenes 的递归筛法

let primes max =
  let rec sieve found toTest =
    let h = List.hd toTest
    and t = List.tl toTest in

    let newPrimes = h :: found
    and doesntDivide x = (x mod h <> 0) in

    let nonDivisors = List.filter doesntDivide t in
      if nonDivisors = [] then newPrimes
                          else sieve newPrimes nonDivisors in

  let rec range a b =
    if a > b then []
             else a :: range (a + 1) b in

  let p = range 2 max in

  sieve [] p;;

Eratosthenes v2 的递归筛法

let primes max =
  let rec sieve toTest =
    let h = List.hd toTest
    and t = List.tl toTest in
    let doesntDivide x = (x mod h <> 0) in
    let nonDivisors = List.filter doesntDivide t in
      if nonDivisors = [] then [h]
                          else (h :: sieve nonDivisors) in

  let rec range a b =
    if a > b then []
             else a :: range (a + 1) b in

  let p = range 2 max in

  sieve p;;

Eratosthenes 的 While 环筛法

let primes max =
  let rec range a b =
    if a > b then []
             else a :: range (a + 1) b in

  let tail = ref (range 2 max)
  and p    = ref [] in

  while !tail <> [] do
    let h = List.hd !tail
    and t = List.tl !tail in
    let doesntDivide x = (x mod h <> 0) in
    let newTail = ref (List.filter doesntDivide t) in

    tail := !newTail;
    p := h :: !p
  done;

  !p;;

Answer 1

堆栈溢出的发生是因为您的范围函数不是尾递归的。一个有效的是，例如

  let rec range store a b =
    if a > b then store
    else range (a :: store) (a + 1) b
  in

  let p = List.rev (range [] 2 max) in

根据该定义和格式行，给出

$ ocamlopt -o primes2 primes2.ml
$ ./primes2
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
...

既然你在学习，我也会主动给你一些风格评论:)

• 不要使用 hd 和 tl。更喜欢模式匹配。然后编译器可以告诉你你错过的案例。例如

  let rec sieve found toTest = 让 h = List.hd toTest 和 t = List.tl toTest in

会是

let rec sieve found = function
  | h :: t -> ...
  | [] -> Error handling...

• 不要使用 x = []。使用模式修补。

  将 x 与| [] -> ...| h::t -> ...

• 使用匿名函数而不是短的(即 <= 1 行)命名的一次性函数:

  让不除 x = (x mod h <> 0) inlet nonDivisors = List.filter doesntDivide t in

  let nonDivisors = List.filter (fun x -> (x mod h <> 0)) t in

• 谨慎使用命令式功能。