title: Slow Haskell and Python code with Project Euler #2
body: <p>I was practicing a bit with Haskell to get to know the language (It's amazing) so I went to project euler and did problem #2 which took quite a while (~ 30-40s I don't know how long exactly) to finish. I wondered why it took so long so I tried the same with F#, C# Javascript and Python. F# and C# took a couple of ms to finish as well as javascript but python took more time than Haskell did. Why is that? These are my implementations</p>
  
  <p>Haskell</p>
  
  <pre class="lang-hs prettyprint-override"><code>fib 0 = 1
  fib 1 = 1
  fib n = fib (n-1) + fib (n-2)
  
  genFibs n maxVal = 
  if fib n &lt; maxVal then 
      fib(n):(genFibs (n+1) maxVal) 
  else []
  
  totalSum = sum (filter even (genFibs 1 4000000))
  
  main = print totalSum
  </code></pre>
  
  <p>F#</p>
  
  <pre class="lang-ml prettyprint-override"><code>let rec fib n = 
      match n with
      | n when n &lt; 2 -&gt; 1
      | n -&gt; fib (n-1) + fib (n-2)
  
  let rec genFibos n max = 
      match fib(n) &lt; max with
      | true -&gt; fib(n)::(genFibos (n + 1) max)
      | false -&gt; []
  
  genFibos 1 4000000
  |&gt; Seq.where (fun n -&gt; n % 2 = 0)
  |&gt; Seq.sum
  </code></pre>
  
  <p>C#</p>
  
  <pre class="lang-cs prettyprint-override"><code>static int Fib(int n)
  {
      return n &lt; 2 ? 1 : Fib(n - 1) + Fib(n - 2);
  }
  
  public static int EvenFibs()
  {
      var n = 1;
      var totalSum = 0;
      var num = 1;
      while(num &lt; 4000000)
      {
          num = Fib(n);
          if (num % 2 == 0) totalSum += num;
          n += 1;
      }
      return totalSum;
  }
  </code></pre>
  
  <p>Python</p>
  
  <pre class="lang-py prettyprint-override"><code>knownVals = { }
  def fib(n):
  if n not in knownVals:
     knownVals[n] = 1 if n &lt; 2 else fib(n-1) + fib(n-2)
  return knownVals[n]
  
  n = 1
  stillCounting = True
  totalSum = 0
  
  while stillCounting: 
      num = fib(n)
      if num &gt; 4000000:
          stillCounting = False
      else:
          if num % 2 == 0:
              totalSum += num
          n += 1
  
  print(totalSum)
  </code></pre>
  
  <p>Javascript</p>
  
  <pre><code>(function () {
  
  function fib(n) {
      return n &lt; 2 ? 1 : fib(n - 1) + fib(n - 2);
  }
  
  var totalSum = 0;
  var num = 1;
  var n = 1;
  
  while(num &lt; 4000000)
  {
      num = fib(n);
      if (num % 2 == 0) totalSum += num;
      n += 1;
  }
  
  alert(totalSum);
  
  })();
  </code></pre>
  
  <p>So can someone explain why Haskell and Python were slow and the F# and C# were fast on this and how I can enhance it? Any help would be appreciated!</p>
  
  <p><strong>EDIT</strong>: Haskell code corrected, Python better implementation using memoization</p>