Functional Programming in C#, Second Edition

12 A short introduction to functional data structures

This chapter covers

• Functional data structures
• Linked lists
• Binary trees

In chapter 11, you saw how to create immutable objects. Particularly, section 11.1 showed the pitfalls of state mutation when concurrency is involved. These pitfalls become even more evident when dealing with collections. Because it takes longer to process a large collection than to update a single object, there are greater chances of a race conditions occurring (we saw an example of this in section 1.1.3).

Now that you know about immutable objects, let’s look at some of the principles behind the design of immutable data structures. Note that the terms functional data structures and immutable data structures are used ...