How not to reverse a list

 Brian McNamara, the latest addition to our stellar F# dev team, wrote up a great blog post on some pitfalls of F#. Specifically, how if you aren't careful something as simple as reversing the items in a list can take on order O(N^2) time and potentially cause a StackOverflow.

You can read the full post here:

https://lorgonblog.spaces.live.com/Blog/cns!701679AD17B6D310!163.entry

 

This isn't the first time someone wrote about how deceptive F# can be with regard to performance. Earlier this week Robert Pickering had a great response to another blog implying that F# was slower than C#; but with a few key optimizations Robert demonstrated that F#'s performance profile is about the same as C#.

https://strangelights.com/blog/archive/2008/03/25/1610.aspx

 

The moral here is that the exact IL opcodes your compiler emits isn't nearly as important as the asymptotic time complexity for the algorithm you use. F# isn't a slow language by any means, but to the novice functional programmer (such as myself) it is easy to fall into the trap of favoring concise code over performant code. As was the case in the naive list reverse implementation. When we get closer to shipping I'll be sure to devote a series of blog posts to documenting the runtime performance of F# library functions and how to write performant F# code.