Cover by Oliver Sturm

Safari, the world’s most comprehensive technology and business learning platform.

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required

O'Reilly logo

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

image

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 ...

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required