3 Functional data structures and immutability


This chapter covers

  • Building parallel applications with functional data structures
  • Using immutability for high-performant, lock-free code
  • Implementing parallel patterns with functional recursion
  • Implementing immutable objects in C# and F#
  • Working with tree data structures

Data comes in a multitude of forms. Consequently, it’s not surprising that many computer programs are organized around two primary constraints: data and data manipulation. Functional programming fits well into this world because, to a large extent, this programming paradigm is about data transformation. Functional transformations allow you to alter a set of structured data from its original form into another form without having to worry about side effects or state. For example, you can transform a collection of countries into a collection of cities using a map function and keep the initial data unchanged. Side effects are a key challenge for concurrent programming because the effects raised in one thread can influence the behavior of another thread.

3.1 Real-world example: hunting the thread-unsafe object

3.1.1 .NET immutable collections: a safe solution

3.1.2 .NET concurrent collections: a faster solution

3.1.3 The agent message-passing pattern: a faster, better solution

3.2 Safely sharing functional data structures among threads

3.3 Immutability for a change

3.3.1 Functional data structure for data parallelism

3.3.2 Performance implications of using immutability

3.3.3 Immutability in C#

3.3.4 Immutability in F#

3.3.5 Functional lists: linking cells in a chain

3.3.6 Building a persistent data structure: an immutable binary tree

3.4 Recursive functions: a natural way to iterate

3.4.1 The tail of a correct recursive function: tail-call optimization

3.4.2 Continuation passing style to optimize recursive function