title: F# functional style approach much slower
body: <p>Trying to learn F#, by solving some programming puzzles. I don't want to add too many details about the problem as I don't want to spoil the fun for others.</p>
  
  <p>Basically, the issue is to find all 4-uples { (i,j,k,l) | i ^ j ^ k ^ l != 0 } with no repetition (eg., (1,1,1,2) and (1,1,2,1) are the same and should be counted just once). </p>
  
  <p>I have found a O(n^3) approach which works, please see <code>countImperative(a,b,c,d)</code> below. But I also tried to refactor the code as to get rid of the nested for loops. However, I could not do so without a significant performance penalty. It was my impression that F#'s syntactic sugar would allow a more concise style (using pipes and folds), letting the compiler do the heavy-lifting to produce comparably fast code (compared to my nested for loops). The big performance hit comes from the calculation of the <code>partial2</code> sum.</p>
  
  <p>Here's the code:</p>
  
  <pre><code>open System
  open System.Diagnostics
  open System.Collections
  
  module quadruples =
      [&lt;EntryPoint&gt;]
      let main argv = 
          let input = "2000 2000 2000 2000"
          let ordered = [ for x in input.Split([|' '|]) -&gt; Convert.ToInt32(x) ] |&gt; List.sort
          let a,b,c,d = ordered.[0], ordered.[1], ordered.[2], ordered.[3]
          let inner(a,b) = a * (a-1) / 2 + a * (b-a) 
          let sw = new Stopwatch()
  
          sw.Start()
          let partial1 = [ 1.. b ] |&gt; List.fold (fun acc j -&gt; acc + (int64 ((min a j) * inner(c-j+1, d-j+1)))) 0L
          sw.Stop()
          let elapsed1 = (sw.ElapsedMilliseconds |&gt; double) / 1000.0
          printfn "Partial1: %f s" elapsed1
  
          sw.Restart()
          let combinations = [ for i in 1..a do for j in i+1..b do yield (j,i^^^j) ]
          let range = [ 1..c ]
          let partial2 = combinations |&gt; List.fold(fun acc (j,x) -&gt; acc + (range |&gt; List.skip(j-1) |&gt; List.fold(fun acc k -&gt; if k ^^^ x &lt; k || k ^^^ x &gt; d then acc + 1L else acc) 0L)) 0L
          sw.Stop()
          let elapsed2 = (sw.ElapsedMilliseconds |&gt; double) / 1000.0
          printfn "Partial2: %f s" elapsed2
          printfn "Functional: %d, Elapsed: %f s" (partial1 + partial2) (elapsed1 + elapsed2)
  
          // "imperative" approach
          let countImperative(a,b,c,d) =
              let mutable count = seq { 1..b } |&gt; Seq.fold (fun acc j -&gt; acc + (int64 ((min a j) * inner(c-j+1, d-j+1)))) 0L
              for i in 1..a do 
                  for j in i+1..b do 
                      let x = i ^^^ j
                      for k in j..c do
                          let y = x ^^^ k
                          if y &lt; k || y &gt; d then
                              count &lt;- count + 1L
              count
  
          sw.Restart();                        
          let count = countImperative(a,b,c,d)
          sw.Stop()
          printfn "Imperative: %d, Elapsed: %f s" count ((sw.ElapsedMilliseconds |&gt; double) / 1000.0)
          0 // return an integer exit code
  </code></pre>
  
  <p>So my question was, if there is any way to speed up the code (specifically the calculation of <code>partial2</code>) while maintaining F#'s nice syntax.</p>