F#: how to find Cartesian power

Question

I have a problem with writing a Cartesian power function. I found many examples about calculating Cartesian Product, but no one about Cartesian power.
For example, [1;2] raised to power 3 = [ [1;1;1] ; [1;1;2] ; [1;2;1] ; [1;2;2] ; [2;1;1] ; [2;1;2] ; [2;2;1]; [2;2;2] ]
I use following code to calculate Cartesian Product:

 let Cprod U V =
        let mutable res = []
        for u in U do
            for v in V do
                res <- res @ [[u;v]]
        res

And trying to calculate Cartesian power. I use following code to calculate Cartesian Product:

let Cpower U n =
    let mutable V = U
    for i=0 to n-1 do
        V <- Dprod U V
    V

Visual Studio said: Error The resulting type would be infinite when unifying ''a' and ''a list'. I will thankful for any help and links.

Answer 1

I solve my problem:

let rec Cprod = function
    | [] -> [[]]
    | hs::tss ->
        [ for h in hs do            
            for ts in D tss ->
                h::ts]

let Cpower U n = 
    let mutable inp = []
    for i=0 to n-1 do
        inp <- inp @ [U]
    Dprod inp

Answer 2

As for where the error comes from, we have the following type constraints

// Cprod: seq<`a> -> seq<`a> -> `a list list
let Cprod U V =
    ...

// Cpower: seq<`a> -> int -> ???
let Cpower U n =
    // V: seq<`a>
    let mutable V = U
    // n: int
    for i=0 to n-1 do
        (* The next line implies two type constraints:
           V: seq<`a>
           V: `a list list *)
        V <- Dprod U V
    V

That V must be an seq<`a> and an `a list list, and that U and V must have the same type means that `a = `a list, which is what results in the "infinite type" error message (the infinity type is ... list list list list. Even though the value of V is mutable, it must have a single type.

Answer 3

Here is a version ported from Haskell:

let replicate n x = [for i in 1 .. n -> x]
let sequence ms = 
  List.fold (fun m' m -> [for x in m do for xs in m' -> (x::xs)]) [[]] ms
let Cpower n l = replicate n l |> sequence

It works like counting: if you think of l as the digits, then it replicates them for the number of places you have, then counts over them using sequence.

In other words, all binary numbers less than 2^3 can be generated by replicating [0;1] 3 times to get [[0;1]; [0;1]; [0;1]] then running sequence on them.

This can be made lazier by switching to Seq.fold:

let sequence' ms =
  Seq.fold (fun m' m -> seq {for x in m do for xs in m' do yield (x::xs)})
           (seq {yield []})
           ms

This gives you a seq of the results instead of a list. Unfortunately, I can't tell by looking at it if it's lazy enough: it might have to generate the entire list in memory to start giving you the first element. You should be able to find out by stepping through it in the debugger. (Or you might be better at reading laziness than I am.)

Answer 4

I would also add that it is generally prefered to avoid using mutable values when writing F# code. It's fine when you're learning F# or when you need to optimize some code to run faster, but if you want to write a more idiomatic F# code, it's better to use recursion instead of mutable values.

I tried to write the Cartesian power a bit more elegantly and here is my version. It is implemented recursively. I explicitly handle the case when we need to calculate X^1 and the recursive case performs a Cartesian product like this: X^n = X * X^(n-1)

I'm using sequence expressions and the method generates elements of the sequence (to be returned as the result) using yield:

let rec cartesianPow input n = seq {
  if (n = 1) then
    // This handles the case when the recursion terminates. We need to turn
    // each element from the input into a list containing single element:
    //   [1; 2; 4] ^ 1 = [ [1]; [2]; [3] ]
    for el in input do 
      yield [el]
  else
    // We perform one Cartesian product (and run the rest of the 
    // power calculation recursively). Mathematically:
    //   [1; 2; 3] ^ n = [1; 2; 3] x ([1; 2; 3] ^ (n-1))
    for el in input do 
      for rest in cartesianPow input (n - 1) do
        yield el :: rest }

cartesianPow [ 0; 1 ] 3

This isn't the most efficient implementation (e.g. because using yield inside for loop may not be a good thing to do), but that would be only problem for large n. In F#, it is usually a good idea to start with the cleanest implementation that's easier to understand :-).