Chapter 10. Efficiency of data structures
This chapter covers
- Optimizing and improving recursive functions
- Using tail-recursion and continuations
- Working efficiently with lists and arrays
So far in this book, we’ve used functional techniques such as recursion and functional data structures like immutable lists. We’ve written the code in the most straightforward way we could, using the basic F# collection type (a list) and expressing our intentions directly. This works very well in many situations, but when it comes to processing large data sets, “obvious” code sometimes leads to performance problems. In this chapter, we’ll look at techniques for writing code that work regardless of the size of the input and examine ways to optimize the performance of functions working with data. We’ll still strive to keep the code as readable as possible.
If you’ve been developing for any significant length of time, you’ve almost certainly written a program that caused a stack overflow exception. In functional programming this error can easily be caused by a naïvely written recursive function, so we’ll explore several ways of dealing with functions that can cause this error when processing large amounts of data. This will be our starting topic, and we’ll return to it at the end of the chapter.