For Loop Over a Recursive Call Ocaml

Question

I'm working on an implementation of prime decomposition in OCaml. I am not a functional programmer; Below is my code. The prime decomposition happens recursively in the prime_part function. primes is the list of primes from 0 to num. The goal here being that I could type prime_part into the OCaml interpreter and have it spit out when n = 20, k = 1.

2 + 3 + 7
5 + 7

I adapted is_prime and all_primes from an OCaml tutorial. all_primes will need to be called to generate a list of primes up to b prior to prime_part being called.

(* 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)

I'm largely confused with the reclusive nature with the for loop. I see that List.ittr is the OCaml way, but I lose access to my variables if I define another function for List.ittr. I need access to those variables to recursively call prime_part. What is a better way of doing this?

I can articulate in Ruby what I'm trying to accomplish with OCaml. n = any number, k = 1, lst = [], primes = a list of prime number 0 to 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

Here are a few comments on your code.

1. You can define nested functions in OCaml. Nested functions have access to all previously defined names. So you can use List.iter without losing access to your local variables.

2. I don't see any reason that your function prime_part_constructive returns an integer value. It would be more idiomatic in OCaml for it to return the value (), known as "unit". This is the value returned by functions that are called for their side effects (such as printing values).

3. The notation a.(i) is for accessing arrays, not lists. Lists and arrays are not the same in OCaml. If you replace your for with List.iter you won't have to worry about this.

4. To concatenate two lists, use the @ operator. The notation lst.concat doesn't make sense in OCaml.

Update

Here's how it looks to have a nested function. This made up function takes a number n and a list of ints, then writes out the value of each element of the list multiplied by n.

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

The write1 function is a nested function. Note that it has access to the value of n.

Update 2

Here's what I got when I wrote up the function:

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

It works for your example:

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

Note that this function returns the list of partitions. This is much more useful (and functional) than writing them out (IMHO).