Chapter 2 covers the efficient implementation of stack and binary search trees when your data structures must be immutable. This chapter wound up being a lot of fun to work on because it helped me focus a lot on how to approach structuring my F# code and start laying the foundation for how to approach building elegant F# code.
There are two implementations of the stack in this chapter. The first is rather uninteresting and the second is significantly more educational. This section on Lists appeared to be more focused on using lists to represent other data structures in this case to build a stack data structure.
The first implementation is merely built on top of the existing list data structure. Below is the direct conversion into F#:
1 2 3 4 5 6 7 8
There really wasn’t a whole lot of interesting stuff in this first example.
The second section is much more fun: a custom data structure is built to represent the stack. Built as a recursively nested tuple. Which is actually identical to the traditional way of representing a regular list. This provides a nice way of building up an immutable list from primitives (tuples) in order to build a more complex data structure (a stack).
This was also the first part where I had an opportunity to experiment
with how to write this well in F# and reason through the pros and cons
of a specific approach. My first attempt was to get as close to the
book as possible and I used a
type with member methods to group the
CustomStack with its associated functions. The second approach uses
module CustomStack to group the type with the associated functions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
The first thing I learned was that the F# compiler autogenerates a function
IsEmpty. Despite working with the language for several months,
I’d somehow never noticed that when you create a discriminated union type
F# automatically adds member methods for check if a value is a specific
element in the discriminated union.
Using static member methods to group the related functions to the type didn’t
feel particularly elegant: you’d always have to prepend all calls to functions
CustomStack.. So I tried using another approach: using a
CustomStack to group the functions with the type. This would
provide the option of just calling the functions or prepending the module
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
This version felt much better to me, I also took the opportunity to create
++ for appends. There is an interesting consequence that
this approach creates by disconnecting the type parameter restrictions
that functions require from the type definition; this will come up
explicitly in the binary search trees section.
I tried a slightly different format for
type CustomStack and
placing the patterns on one line. I’m not sure how I feel about
this approach. It seems very easy to miss the
| and not properly
see the pattern definitions. Having everything on one line also
implies that everything is part of the same operation and that is
decidely not the case with pattern matching and DU definitions.