Functional Programming in C#: Classic Programming Techniques for Modern Projects

IMPLEMENTING IMMUTABLE CONTAINER DATA STRUCTURES

The rest of this chapter provides several examples, with explanations, for the implementation of container data structures that are persistent in nature. The algorithms for these implementations are taken from Chris Okasaki’s book Purely Functional Data Structures (Cambridge University Press). The book contains these algorithms implemented in the functional languages ML and Haskell, and quite a few compromises had to be made in translating to C#.

Linked List

Every programmer has written a singly linked list, and as a programming task usually given to those who are just learning the trade, it can be quite daunting. Part of the reason is that these lists are generally to be implemented in a mutable fashion, which means lots more effort than for a persistent implementation.

The algorithm for the persistent list type isn’t hard to understand. It is based on the idea that if a unit of work has been started with a reference of the list in an “old” state, any perceived change to the list should not result in a change from that active unit’s point of view. Figure 16-1 shows the three steps for the process of adding elements to the list:

FIGURE 16-1: Persistent list add

1. The application holds a reference to the list, i.e. the Head element of it, in a variable list.

2. A separate unit of work is started and gets a reference to the list ...