Nested loop and functional programming

Question

Please consider a C program that, given x, will return y and z such that y + z * 2 = x, for the smallest possible y. Roughly, I could create a nested loop:

for(y = 0; y < x; ++ y){
    for(z = 0; z < x; ++z){
        if(y + 2 * z == x){
            printf("%d + 2 * %d = %d", y, z, x);
        }
    }
} 

How could I translate this kind of nested loop in the functional way? Is it feasible? Is it reasonable or am I just misjudging the approach? My best attempt so far:

let foo x =
    let rec aux (y, z, q) =
        match (y + z * 2) with
        r when r = q -> (y, z)
        |_      -> aux(y + 1, z + 1, q)  //How to check different values of z
    aux(0, 0, x)                         //for each value of y?

It will not work, since it will just increment both y and z. How can I check different values of z, for every value of y?

Answer 1

You have to add those checks in the match.

See here what your code is missing:

let foo x =
    let rec aux (y, z, q) =
        match (y + z * 2) with
        | r when r = q -> (y, z)
        | _ when y = q -> failwith "not found !"
        | _ when z = q -> aux (y + 1, 0, q)
        | _            -> aux (y, z + 1, q)
    aux (0, 0, x)

And here's a different approach, equally functional but without recursion:

let foo2 x =
    let s =
        {0 .. x} |> Seq.collect (fun y ->
            {0 .. x} |> Seq.collect (fun z -> 
                seq [y, z]))
    Seq.find (fun (y, z) -> y + z * 2 = x) s

which in F# can be written using seq expressions:

let foo3 x =
    let s = seq {
        for y in {0 .. x} do
            for z in {0 .. x} do
                yield (y, z)}
    Seq.find (fun (y, z) -> y + z * 2 = x) s

and it resembles your original C program.