8

Can you suggest simpler and clearer way to write this function?

let cartesian_product sequences = 
    let step acc sequence = seq { 
        for x in acc do 
        for y in sequence do 
        yield Seq.append x [y] }
    Seq.fold step (Seq.singleton Seq.empty) sequences
Vladimir Reshetnikov
  • 11,750
  • 4
  • 30
  • 51
  • 2
    See http://stackoverflow.com/questions/3334429/how-do-i-compute-the-cartesian-product-of-n-sequences-in-f/3334871#3334871 – Juliet Jun 27 '11 at 18:18
  • 3
    And for a C# solution that is basically the same as this F# solution, see http://stackoverflow.com/questions/3093622/generating-all-possible-combinations/3098381#3098381 – Eric Lippert Jun 27 '11 at 18:20

2 Answers2

2

I benchmarked the function Juliet linked to:

let items = List.init 6 (fun _ -> [0..9])
cart1 items |> Seq.length |> ignore

Real: 00:00:03.324, CPU: 00:00:03.322, GC gen0: 80, gen1: 0, gen2: 0

and a slightly modified (to make it an apples-to-apples comparison) version of yours:

let cartesian items =
  items |> Seq.fold (fun acc s ->
    seq { for x in acc do for y in s do yield x @ [y] }) (Seq.singleton [])

cartesian items |> Seq.length |> ignore

Real: 00:00:00.763, CPU: 00:00:00.780, GC gen0: 37, gen1: 2, gen2: 1

Yours is significantly faster (and causes fewer GCs). Looks to me that what you have is good.

Daniel
  • 47,404
  • 11
  • 101
  • 179
2

Less elegant, but (seems to be) faster solution:

let cartesian_product2 sequences = 
    let step acc sequence = seq { 
        for x in acc do 
        for y in sequence do 
        yield seq { yield! x ; yield y } }
    Seq.fold step (Seq.singleton Seq.empty) sequences

;

> cartesian items |> Seq.length;;
Real: 00:00:00.405, CPU: 00:00:00.405, GC gen0: 37, gen1: 1, gen2: 0
val it : int = 1000000
> cartesian_product2 items |> Seq.length;;
Real: 00:00:00.228, CPU: 00:00:00.234, GC gen0: 18, gen1: 0, gen2: 0
val it : int = 1000000
Ed'ka
  • 6,595
  • 29
  • 30
  • 1
    This seems faster because you're returning `seq>` instead of `seq>`, i.e., your inner sequences aren't being evaluated. Try `cartesian_product2 items |> Seq.map Seq.toList |> Seq.length`. – Daniel Jun 28 '11 at 16:51
  • @Daniel: Good point. But it's still 2 times faster than the author's solution (while still being lazy, as required). – Ed'ka Jun 28 '11 at 20:55
  • is this one faster for building the sequence and materializing it? or neither because the test didn't materialize the sub-sequences ? – Maslow Sep 12 '16 at 16:52