For循环递归调用Ocaml

Question

我正在研究 OCaml 中素数分解的实现。我不是函数式程序员；下面是我的代码。质数分解在 prime_part 函数中递归发生。 primes是从0到num的素数列表。这里的目标是我可以在 OCaml 解释器中输入 prime_part 并在 n = 20, k = 1.

时将其吐出

2 + 3 + 7
5 + 7

我从 OCaml 教程中改编了 is_prime 和 all_primes。在调用 prime_part 之前，需要调用 all_primes 来生成最多 b 的素数列表。

(* adapted from http://www.ocaml.org/learn/tutorials/99problems.html *)
let is_prime n =
    let n = abs n in
    let rec is_not_divisor d =
      d * d > n || (n mod d <> 0 && is_not_divisor (d+1)) in
    n <> 1 && is_not_divisor 2;;

let rec all_primes a b =
  if a > b then [] else
    let rest = all_primes (a + 1) b in
    if is_prime a then a :: rest else rest;;

let f elem =
    Printf.printf "%d + " elem

let rec prime_part n k lst primes =
    let h elem =
        if elem > k then
            append_item lst elem;
        prime_part (n-elem) elem lst primes in
    if n == 0 then begin
        List.iter f lst;
        Printf.printf "\n";
        ()
    end
    else
        if n <= k then
        ()
        else 
            List.iter h primes;
            ();;

let main num = 
    prime_part num 1 [] (all_primes 2 num)

我对 for 循环的隐蔽性感到很困惑。我看到 List.ittr 是 OCaml 方式，但如果我为 List.ittr 定义另一个函数，我将无法访问我的变量。我需要访问这些变量以递归调用 prime_part。这样做的更好方法是什么？

我可以在 Ruby 中阐明我试图用 OCaml 完成的事情。 n = 任意数, k = 1, lst = [], primes = 0 到 n

的素数列表

def prime_part_constructive(n, k, lst, primes)
if n == 0
  print(lst.join(' + '))
  puts()
  end
  if n <= k
    return
  end
  primes.each{ |i|
    next if i <= k
    prime_part_constructive(n - i, i, lst+[i], primes)
    }
end

Answer 1

以下是对您的代码的一些评论。

您可以在 OCaml 中定义嵌套函数。嵌套函数可以访问所有先前定义的名称。因此，您可以使用 List.iter 而不会失去对局部变量的访问权限。
我看不出有任何理由表明您的函数 prime_part_constructive return 是整数值。在 OCaml 中，return 值 () 更符合习惯，称为 "unit"。这是由函数调用的值 return 产生的副作用（例如打印值）。
符号 a.(i) 用于访问数组，而不是列表。 OCaml 中的列表和数组不同。如果您将 for 替换为 List.iter，您就不必担心这一点。
要连接两个列表，请使用 @ 运算符。符号 lst.concat 在 OCaml 中没有意义。

更新

这是嵌套函数的样子。这个组成的函数接受一个数字 n 和一个整数列表，然后写出列表中每个元素的值乘以 n.

let write_mults n lst =
    let write1 m = Printf.printf " %d" (m * n) in
    List.iter write1 lst

write1函数是一个嵌套函数。请注意，它可以访问 n.

的值

更新 2

这是我编写函数时得到的结果：

let prime_part n primes =
    let rec go residue k lst accum =
        if residue < 0 then
            accum
        else if residue = 0 then
            lst :: accum
        else
            let f a p =
                if p <= k then a
                else go (residue - p) p (p :: lst) a
            in
            List.fold_left f accum primes
    in  
    go n 1 [] []

它适用于您的示例：

val prime_part : int -> int list -> int list list = <fun>
# prime_part 12 [2;3;5;7;11];;
- : int list list = [[7; 5]; [7; 3; 2]]

注意这个函数returns分区列表。这比写出来（恕我直言）更有用（和功能）。

For循环递归调用Ocaml

For Loop Over a Recursive Call Ocaml

recursion

ocaml

primes

prime-factoring