Inside F#

Brian's thoughts on F# and .NET

Some common F# pitfalls to avoid

Posted by Brian on March 25, 2008

When reading other people’s blogs about F#, there are two common pitfalls I often see people make.  The first pitfall is that sometime people blindly code a recursive solution, without consideration as to whether the function is tail-recursive or not (which could lead to a StackOverflowException).  The second pitfall is that I often see people code little algorithms on lists that wind up being O(N^2) when in fact there’s a simple way to make it O(N).  So I thought I would demo this with some code.  The library function "List.rev" will reverse a list, but say we wanted to write that function ourselves… the code here shows two ways to do it, and the implications of those two strategies:

open System.Diagnostics

// naive way to reverse a list
//  – not tail recursive (can blow stack)
//  – O(N^2) algorithm (due to way append ‘@’ operator is used)
let rec rev1 list = 
    match list with
    | [] -> []
    | h::t -> (rev1 t) @ [h]

// one much better way
//  – uses loops and mutables, but is still short and readable (not inelegant)  
//  – O(N)
let rev2 list =
    let mutable result = []
    let mutable cur = list
    while cur <> [] do
        let h::t = cur
        result <- h :: result
        cur <- t
    result
    
// demo that functions do the right thing
let sample = [1; 2; 3; 4]
printfn "%A" (rev1 sample)
printfn "%A" (rev2 sample)
printfn "%A" (List.rev sample)  // the F# library function for reversing

let stopWatch = new Stopwatch()
let ResetStopWatch() = stopWatch.Reset(); stopWatch.Start()
let time op a =
    ResetStopWatch()
    let result = op a
    let ms = stopWatch.ElapsedMilliseconds
    result, ms

let timeEachReverse l =
    // do each twice, and sum times (to average a little)
    let (_,Lrevt1) = time List.rev l
    let (_,rev1t1) = time rev1 l
    let (_,rev2t1) = time rev2 l
    let (_,Lrevt2) = time List.rev l
    let (_,rev1t2) = time rev1 l
    let (_,rev2t2) = time rev2 l
    (rev1t1 + rev1t2, rev2t1 + rev2t2, Lrevt1 + Lrevt2)

let showResults n =
    let list = [for i in 1..n -> i]  // [1; 2; 3; … n]
    let (rev1time, rev2time, Lrevtime) = timeEachReverse list
    printfn "rev1:%5d  rev2:%5d  List.rev:%5d" rev1time rev2time Lrevtime
    
showResults 20000
// One run on my box printed:
//[4; 3; 2; 1]
//[4; 3; 2; 1]
//[4; 3; 2; 1]
//rev1:25189  rev2:    4  List.rev:    0

As you can see, the naive solution took more than 25 seconds to (twice) process a 20,000-element list, whereas the better solution took just 4ms and the library call executed in a blink.  So the moral is: don’t stumble into these pitfalls.  When writing recursive functions that can process arbitrarily large data, be careful to either use tail recursion or else switch to iteration.  And when writing functions on lists, be wary of how you construct new list values; it is especially easy to abuse the append (@) operator (which must copy its left-hand argument) and wind up with something N^2 instead of N.

This little bit of code shows off one other F# feature I rarely see people use.  Pattern-matching – it’s not just for the "match blah with" statement!  You can use patterns in most binding constructs; "let" is the most common example.  As a result, rather than saying

    while cur <> [] do
        let h = cur.Head 
        let t = cur.Tail 

we just said

    while cur <> [] do
        let h::t = cur

which binds the names "h" and "t" at once.  Similarly, since timeEachReverse returns a tuple of three values, we just write

    let (rev1time, rev2time, Lrevtime) = timeEachReverse list

to bind each result to a different name.

Advertisements

3 Responses to “Some common F# pitfalls to avoid”

  1. Stephan said

    Hi Brian,The "obvious" functional implementation of List.rev is of courselet rec rev1 list =     let rec rev acc = function        | h::t -> rev (h::acc) t        | []   -> acc    rev [] listOn my system (F# 1.9.3.14, Win XP 64) this implementation is (for large arrays) twice as fast as your imperative solution and even faster than List.rev from the library. Your imperative code is comparatively slow because you use "<> []" to check for the empty list, which  F# compiles  into a call to HashCompare.StructuralEqualityGeneric. You could avoid this by using pattern matching instead, though in the context of the while loop this would make things a little bit ugly. (But maybe you are using an internal version of F# that generates better code for  "<> []"… )Best regards,  Stephan

  2. Stephan said

    I forgot to mention: F#\’s optimizer turns the tail recursive implementation into a while loop, so there isn\’t really a reason to do it manually.

  3. Unknown said

    Or as the obvious implementation is more frequently written:let reverse = fold_left (::) []

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: