Для Loop Over Recursive Call Ocaml

Question

Я работаю над реализацией простого разложения в OCaml. Я не функциональный программист; Ниже мой код. Основное разложение происходит рекурсивно в функции prime_part. primes - это список простых чисел от 0 до num. Цель здесь в том, что я мог бы ввести prime_part в интерпретатор OCaml и он выплюнул при п = 20, к = 1.

2 + 3 + 7 
5 + 7 

Я приспособил is_prime и all_primes из учебника OCaml. all_primes необходимо вызвать для генерации списка простых чисел до b до того, как будет вызываться prime_part.

(* 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. п = любое число, к = 1, LST = [], воспламеняет = список простых чисел от 0 до п

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

Вот несколько комментариев на вашем коде.

1. Вы можете определить вложенные функции в OCaml. Вложенные функции имеют доступ ко всем ранее определенным именам. Таким образом, вы можете использовать List.iter, не теряя доступ к вашим локальным переменным.

2. Я не вижу причин, по которым ваша функция prime_part_constructive возвращает целочисленное значение. В OCaml было бы более идиоматично возвращать значение (), известное как «единица». Это значение, возвращаемое функциями, вызываемыми для их побочных эффектов (например, значения печати).

3. Обозначение a.(i) предназначено для доступа к массивам, а не к спискам. Списки и массивы в OCaml не совпадают. Если вы замените for на List.iter, вам не придется беспокоиться об этом.

4. Чтобы скомпоновать два списка, используйте оператор @. Обозначение lst.concat не имеет смысла в OCaml.

Update

Вот как это выглядит, чтобы иметь вложенную функцию. Эта выполненная функция принимает число n и список ints, а затем выписывает значение каждого элемента списка, умноженного на n.

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

Функция write1 является вложенной функцией. Обратите внимание, что он имеет доступ к значению n.

Update 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]] 

Обратите внимание, что эта функция возвращает список разделов. Это гораздо полезнее (и функционально), чем записывать их (IMHO).