More Notes on F# 2.0
by Geoffrey Smith
In these notes, we look more deeply at a number of aspects of programming in F#. In particular we consider not only thecorrectnessof our programs (as guaranteed by the Checklist), but also theirefficiency.
- More on Pattern Matching
Experienced F# programmers do not ordinarily program withList.isEmpty,List.head, andList.tail, preferring to use pattern matching style. There are four advantages to using pattern matching:
- It's pretty!
- If you accidentally applyList.headorList.tailto an empty list, you get an exception. In contrast, the patternx::xsmatches only a nonempty list, safely bindingxto the head and bindingxsto the tail.
- The F# compiler checks whether you have included enough patterns to cover all possible inputs. If not, it gives anIncomplete pattern matcheswarning.
- The F# compiler checks whether a pattern isredundant, in the sense that no input will cause it to be used. If so, F# gives aThis rule will never be matchedwarning.
Advantage 3 is particularly nice. For example, here is a function to find the last element of a list:
> let rec last = function
| [x] -> x
| x::xs -> last xs;;
let rec last = function
------^
stdin(1,16): warning FS0025: Incomplete pattern matches on this expression.
For example, the value '[]' may indicate a case not covered by the pattern(s).
val last : 'a list -> 'a
The warning is alerting you thatlastis not defined on[]. (Note that because of a bug in the current F# compiler, the examples that F# gives are sometimes incorrect.) If we calllaston the empty list, we get an exception:
> last ([] : int list);;
Microsoft.FSharp.Core.MatchFailureException: The match cases were incomplete
at FSI_0002.last[a](FSharpList`1 _arg1)
at .$FSI_0007.main@() Stopped due to error
(Note that without the type annotation on[], we would have gotten avalue restrictionerror.)
Note that it is not anerrorto have incomplete pattern matches, but only awarning. Whether you should get rid of such warnings in your code is really a matter of taste. In the case oflast, it is arguably reasonable to omit a case for the empty list, since the empty list has no last element. The only downside is that we then get the non-specific exceptionMatchFailureException. To get a clearer error message, we can raise our own exception explicitly. The easiest way to do this is with thefailwithfunction, which takes astringargument, which is the desired error message:
> let rec last = function
| [] -> failwith "empty list has no last element"
| [x] -> x
| x::xs -> last xs;;
val last : 'a list -> 'a
> last ([] : int list);;
Microsoft.FSharp.Core.FailureException: empty list has no last element
(By the way, F# includes a variety of exception-handling constructs liketry ... with ....)
Thelastfunction also helps to illustrate advantage 2 above. Suppose that we writelastusingList.isEmpty,List.head, andList.tail, rather than using pattern matching:
> let rec last xs =
ifList.isEmpty (List.tailxs) then List.headxs else last (List.tailxs);;
val last : 'a list -> 'a
Now the compilerno longer warns usof the possibility of exceptions. But, of course,last ([] :int list)will still raise an exception, sinceList.tail []raises an exception.
Remark: By the way, there is a subtle typing pitfall associated with testing for an empty list. Suppose we had not usedList.isEmptybut instead "= []" in our definition. Then it turns out thatlastis not fully polymorphic:
> let rec last xs =
ifList.tailxs = [] then List.headxs else last (List.tailxs);;
val last : 'a list -> 'a when 'a equality
Finally, here's an example of advantage 4. Suppose we are trying to define thelastfunction, but we put the patterns in the wrong order:
> let rec last = function
| [] -> failwith "empty list has no last element"
| x::xs -> last xs
| [x] -> x;;
| [x] -> x;;
--^^^^
stdin(52,3): warning FS0026: This rule will never be matched.
val last : 'a list -> 'a
Recall that F# tries the patterns in order. This means that the pattern[x]will never be matched---it matches only lists of length 1, but the patternx::xsalready matches all nonempty lists. Hence this function will actually raise an exception on all inputs!
Remark: Interestingly, the check forincomplete pattern matchesis computationally difficult; it is anNP-hardproblem.
Here is why. Given any boolean propositionp, we can define an F# functionfoothat hasincomplete pattern matchesiffpis satisfiable. For example, ifpis
(b + c + d)(~b + c + ~d)(a + c + d)(a + b + ~c)(~a + ~c + d)(~b + ~c + ~d)
then we can definefooas follows:
let foo = function
| (a, false, false, false) -> 1
| (a, true, false, true) -> 2
| (false, b, false, false) -> 3
| (false, false, true, d) -> 4
| (true, b, true, false) -> 5
| (a, true, true, true) -> 6
Note that each clause of the definition "covers" the truth assignments that falsify the corresponding clause ofp. Since testing the satisfiability of boolean propositions is NP-hard, so is checking for incomplete pattern matches.
We now briefly mention a few other aspects of pattern matching.
We can use a complex pattern to select (for example) the third element of a list:
let third (_ :: _ :: x :: _) = x
In this example, we used thewildcard pattern_, which matches anything but does not create a binding.
We can use patterns inmatchexpressions, letting us match on an intermediate value (rather than just on the input to the function):
> let foo s =
matchString.length s with
| 0 -> "empty"
| 1 -> "short"
| _ -> "long";;
val foo : string -> string
Note that the indentation of nestedmatchexpressions can be significant:
let foo x = function
| 1 -> match x with
| 0 -> true
| 1 -> false
| 2 -> true
We conclude our discussion of patterns by noting a significant restriction:you can't use the same identifier more than once in a pattern:
> let same = function
| (n,n) -> true
| _ -> false;;
| (n,n) -> true
-----^^
stdin(100,6): error FS0038: 'n' is bound twice in this pattern
II. More on Local Declarations
As we have seen, we can make a sequence of local declarations in the body of a function. For example, here is a function to find the roots of a quadratic polynomial:
> let roots (a,b,c) =
let disc = sqrt (b*b - 4.0*a*c)
lettwoa = 2.0*a
((-b+disc)/twoa, (-b-disc)/twoa);;
val roots : float * float * float -> float * float
> roots (1.0, 5.0, 6.0);;
val it : float * float = (-2.0, -3.0)
> disc;;
disc;;
^^^^^
stdin(128,1): error FS0039: The value or constructor 'disc' is not defined.
The most important use of such local declarations is to avoidrecomputation. Inroots, for example, we calculatediscandtwoaonly once, but use them twice. While the savings in this case is modest, sometimes avoiding recomputation can be critical to the efficiency of a program. We will discuss this point more fully in Section V below.
Another (less important) use of local declarations is to define auxiliary functions within the definition of an outer function. Such auxiliary functions are not visible outside; also, they have access to the outer function's parameters.
Here's an example:
> let map f xs =
let rec map_aux = function
| [] -> []
| y::ys -> f y :: map_auxys
map_auxxs;;
val map : ('a -> 'b) -> 'a list -> 'b list
Note thatmap_auxdoes not need to pass the function parameterfto its recursive calls.
We remark that, when defining functions, simultaneous declaration usingandpermits mutual recursion:
let rec f n = if n = 0 then 1 else g n
and g m = m * f(m-1)
III. Two Semantic Issues - Static Scoping and Eager Evaluation
Static Scoping
Suppose a function contains a free identifier. How do we find its binding? One possibility is to use the binding in effect where the function isdefined; this is calledstatic scoping(orlexical scoping). Another possibility is to use the binding in effect when the function iscalled; this is calleddynamic scoping. Here's an example that shows that F# uses static scoping.
> let x = 3 in let f y = x+y
let x = 6
f x;;
val it : int = 9
The binding that F# uses for the free identifierxin functionfis the binding in effect at the place in the program text wherefisdefined, namely 3. Notice that whenfiscalled, the binding ofxis 6.
Notice also the above example makes clear thatlet x = 6is really adeclaration of a constant, not anassignment to a variable.
It is interesting to notice that languages like C and Java also use static scoping. Consider the program above, rewritten into C:
int x = 3;
int f(int y) {return x+y;}
main() {
int x = 6;
f(x);
}
As in F#, the free identifierxinfrefers to the binding in effect at the place wherefwasdefined. Thus we get a result of 9, as in F#. Note however that in C the globalxis a variable, rather than a constant. So if we change the main program to
main() {
x = 6;
f(x);
}
then we get a result of 12, rather than 9. Here the point is that thebindingof the freexinfis simply to thememory locationof the globalx. Thecontentsof that memory location can change as the program runs, affecting the behavior off.
From the point of view of language design, there is now a consensus that static scoping is better than dynamic scoping. The reason is that, under dynamic scoping, one cannot understand a function with free identifiers by simply studying its definition---at the time of acallto the function, there could be new bindings for the free identifiers that would completely change the function's behavior.
Eager Evaluation
An F# function call first evaluates the arguments and then passes them to the function. (Notice that C and Java behave in the same way.) This implies that the built-in&operation cannot be implemented as a user-defined function. For suppose we make the following attempt:
> let myand (e1,e2) = if e1 then e2 else false;;
valmyand : bool * bool -> bool
The trouble is that, under eager evaluation, we don't get short-circuit evaluation. Under eager evaluation, F# immediately evaluates bothe1ande2, even thoughmyandneeds the value ofe2only whene1is true.
> let x = 0;;
val x : int = 0
> x > 0 & 10/x > 2;;
val it : bool = false
> myand (x > 0, 10/x > 2);;
System.DivideByZeroException: Attempted to divide by zero.
at .$FSI_0009._main() stopped due to error
Some functional languages (such as Haskell) uselazy evaluation, in which function arguments are evaluated only when they are actuallyneeded. Interestingly, we can fake lazy evaluation in F# by using first-class functions---we can make each argument into a parameterless function, which we call only when we need the argument's value:
> let myand (e1, e2) = if e1() then e2() else false;;
valmyand : (unit -> bool) * (unit -> bool) -> bool
> myand ((fun () -> x > 0), (fun () -> 10/x > 2));;
val it : bool = false
IV. A Larger Example –QuickSort
Quicksort needs a function to split a list around a "pivot" element:
> let rec split pivot = function
| [] -> ([],[])
| x::xs -> let (left,right) = split pivot xs
if x <= pivot then (x::left, right)
else (left, x::right);;
val split : 'a -> 'a list -> 'a list * 'a list when 'a : comparison
Givensplit, QuickSort takes just a few lines of code:
> let rec qsort = function
| [] -> []
| [x] -> [x]
| x::xs -> let (left, right) = split x xs // x is the pivot
qsort left @ x :: qsort right;;
valqsort : 'a list -> 'a list when 'a : comparison
> qsort [3;1;4;1;5;9;2;6;5];;
val it : int list = [1; 1; 2; 3; 4; 5; 5; 6; 9]
> qsort [3.0; 1.5; 0.6];;
val it : float list = [0.6; 1.5; 3.0]
> qsort ["fish"; "dinosaur"; "elephant"; "cat"];;
val it : string list = ["cat"; "dinosaur"; "elephant"; "fish"]
As an exercise, you should check thatqsortsatisfies the Checklist. Also, notice thatqsortalways uses thefirstelement of the list as the pivot element; this is not really a good thing to do.
V. Writing Efficient Recursive Programs
So far, our focus has been on writingcorrectrecursive programs. In this section, we turn our attention toefficiency. We will give techniques for determining theasymptotic time complexity("big O running time") of an F# function, and discuss various pitfalls that lead to inefficiency. Our discussion will focus on efficient processing oflists.
Implementation of Lists
To begin with, we need to understand how F# implements lists internally. F# uses a classic implementation technique that goes all the way back to the late 1950's in the programming languageLisp. The idea is that a list is represented as apointer to a linked list of cons cells.
Acons cellis just a heap-allocated block of memory containing two pointers. It can be drawn like this:
The first pointer points to the list'shead; the second pointer points to itstail.
For example, here is how the list[1;2;3]is represented:
In this picture,Xdenotes thenull pointer.
Actually, small values likeints may actually be putintothe left half of the cons cell, rather than having a pointer to them. But, in general, an F# value will have a large representation and will need to be accessed via a pointer.
Given this representation, we can see how F#'s built-in list operations are implemented:
- e1 :: e2
Here the values ofe1ande2are pointersp1andp2. We allocate a new cons cell, putp1andp2into it, and return a pointer to the new cons cell. - List.isEmpty e
Here the value ofeis a pointerp. We just test whetherpis the null pointer. - List.head e
Again, the value ofeis a pointerp. Ifpis a null pointer, then we raise anArgumentException. Otherwise, we return theleftpointer of the cons cell thatppoints at. - List.tail e
Again, the value ofeis a pointerp. Ifpis a null pointer, then we raise anArgumentException. Otherwise, we return therightpointer of the cons cell thatppoints at.
Notice that all of these implementations takeconstant time, regardless of the size of the list.
Similarly, pattern matching on a list can be done in timeproportional to the size of the pattern, butindependent of the size of the list. For instance, matching a listLagainst the patternx::y::zjust requires looking at the first two cons cells ofL(if ithasat least two cons cells) and making the bindings:
But there is one worry with this implementation strategy for lists. Weallocatea new cons cell with every cons operation, but we neverdeallocateany cons cells! Of course the answer to this problem is to usegarbage collection. A garbage collector analyzes the heap to determine which cons cells can no longer be reached from any currently-bound identifiers. Such cons cells can safely be recycled.
Determining Asymptotic Time Complexity of a Recursive Function
We now present a simple approach to determining the asymptotic time complexity ("big O running time") of a recursive function processing lists. Our approach requires us to do two things:
- Determinehow many recursive invocationsof the function there will be on an input of lengthn.
- Determinehow much work each of these invocations does directly, not counting the cost of any recursive calls that it makes.
The total running time is simply theproductof these two quantities.
Example Asymptotic Time Complexities
Let's try this approach on some examples. To begin with, consider the following implementation oflength:
let rec length = function
| [] -> 0
| x::xs -> 1 + length xs
How many recursive invocations will there be? Onlength L, notice that ifLhas lengthn, then we will have a total ofn+1 recursive invocations (counting the original invocation), since each recursive call is on the tail of the input.
How much work does each invocation do directly? Based on our discussion above, we see that the input Ltolengthis simply a pointerp. We pattern match againstp; if it is a null pointer, then we return 0; otherwise we fetch the left and right pointers of the cons cell thatppoints at, binding them toxandxs. We passxsas the argument to a recursive call, and then return 1 plus the value returned by the recursive call. (Notice that wedocharge an invocation for the cost ofcomputing the argumentsto its recursive calls. In this case that work is trivial, since we are passingxs, which is a pointer whose value we already have.) In total, you should see that all of this direct work takesconstanttime, independent of the size ofL.
Finally, we conclude that the running time oflengthis (n+1)*O(1) = O(n), on an input of lengthn. Hencelengthtakeslineartime.
Next considerxs @ ys, here defined as an uncurried prefix operator:
let rec append = function
| ([], ys) -> ys
| (x::xs, ys) -> x :: append (xs,ys)
Ifxshas lengthnandyshas lengthm, then notice that we get a total ofn+1 invocations. And each of these invocations again does O(1) work. So in total the running time is O(n). In other words,xs @ ystakes time proportional to the length ofxsbut independent of the length ofys. This asymmetry is very important to keep in mind when you use@.
Remark: It is also interesting to notice that onappend xsys, F# makes atop-level copyof the cons cells ofxs, but simplysharesall of the cons cells ofys. This sharing is very important in making programming with immutable values efficient.
Pitfalls for Efficiency of Recursive Functions
We next discuss some importantpitfallsthat you must watch out for as you try to write efficient recursive functions. The basic principle is to be careful abouthow many recursive invocations you makeand abouthow much work each invocation does directly.
First let's look at functionsplitfromHomework 2:
let rec split = function
| [] -> ([],[])
| [a] -> ([a],[])
| a::b::cs -> let (M,N) = split cs
(a::M, b::N)
In the third case, we recursively splitcsonce, and use the resulttwice. If, instead of using the locallet, we wrote the third case as
| a::b::cs -> (a :: fst (split cs), b :: snd (split cs))
then we would recursively splitcstwice.
What are the asymptotic time complexities of these two definitions ofsplit?
First, with either definition ofsplit, it is clear that each invocation does aconstantamount of work directly. How many recursive invocations are there on an input of lengthn? Whenn> 1, the first definition makesonerecursive call on a list of lengthn-2, while the second definition makestwosuch calls.
Hence the first definition makes aboutn/2 recursive invocations total, and hence takeslineartime, O(n).
But the second definition makes 2 calls on lists of lengthn-2, 4 calls on lists of lengthn-4, 8 calls on lists of lengthn-6, 16 calls on lists of lengthn-8, and so on, until finally making (ifnis even) 2n/2calls on lists of length 0.
Hence the second definition takesexponentialtime, O(2n/2)! (Try the two definitions on lists of size 55, and you will already see a huge difference in performance.)
Thus we see that avoiding recomputation by usingletcan be absolutely critical to the efficiency of recursive definitions.
Next consider the following definition oflast:
let rec last xs =
ifList.isEmptyxs then failwith "empty list has no last element"
elifList.lengthxs = 1 then List.headxs
else last (List.tailxs)
This definition makes only alinearnumber of recursive invocations. But each invocation does alinearamount of work, because each invocation calculatesList.lengthxs. As a result, this definition oflasttakesquadratictime!
Of course, it is easy to fix the inefficiency inlast; just replace "List.lengthxs = 1" with "List.isEmpty (List.tailxs)", or (better yet) use pattern matching style.