Step 2: Working with Functional Lists

Article
09/12/2011

Applies to: Functional Programming

Authors: Tomas Petricek and Jon Skeet

Referenced Image

Get this book in Print, PDF, ePub and Kindle at manning.com. Use code “MSDN37b” to save 37%.

Summary: The second part of the tutorial looks at lists. Lists can be used for storing an arbitrary number of values of the same type. This article explores how to use them in F# and how to implement the same functionality in C#.

This topic contains the following sections.

Introducing Functional Lists
Functional List Processing
Summary
Additional Resources
See Also

This article is an excerpt from Real World Functional Programming: With Examples in F# and C# by Tomas Petricek with Jon Skeet from Manning Publications (ISBN 9781933988924, copyright Manning Publications 2009, all rights reserved). No part of these chapters may be reproduced, stored in a retrieval system, or transmitted in any form or by any means—electronic, electrostatic, mechanical, photocopying, recording, or otherwise—without the prior written permission of the publisher, except in the case of brief quotations embodied in critical articles or reviews.

Introducing Functional Lists

Functional lists are a recursive data structure. Many readers will be more familiar with recursive computations, which is a related concept. In that scenario, recursion means that a function can call itself to perform some (smaller) part of work. A computation like this can only complete if it has a special case that can return the result immediately. Recursive data structures follow the same principle.

A list is either empty or composed from an element and another list. This means that a special value represents an empty list, and that there is a way to construct a list by taking an existing list and prepending an element at the beginning. The first option (an empty list) is sometimes called nil, and the second option produces a cons cell (short for constructed list cell). Figure 1 shows a sample list constructed using an empty list and four cons cells.

Figure 1. A functional list containing four values

Referenced Image

The figure shows a functional list containing 6, 2, 7, and 3. The rectangles represent cons cells, which contain a value and a reference to the rest of the list. The last cons cell references a special value representing an empty list.

The next section shows what the idea looks like in F# and shows code that constructs several list values.

Creating Functional Lists in F#

As Figure 1 illustrates, every cons cell stores a single value from the list (called the head) and a reference to the rest of the list (called the tail), which can be either another cons cell or an empty list (nil). F# provides several ways for constructing lists:

> let ls1 = [] XE "[] (value)" 
val ls1 : 'a list = []
> let ls2 = 6::2::7::3:: XE ":: (operator)" []
val ls2 : int list = [6; 2; 7; 3]

> let ls3 = [6; 2; 7; 3]
val ls3 : int list = [6; 2; 7; 3]

> let ls4 = [1 .. 5] XE "[ .. ] syntax" 
val ls4 : int list = [1; 2; 3; 4; 5]

> let ls5 = 0::ls4
val ls5 : int list = [0; 1; 2; 3; 4; 5]

The first command creates an empty list, which is written as []. As the output shows, F# created a value containing no elements. The type of the list is a bit unclear because F# doesn't yet know the type of values contained in the list, so it infers that the type is a list of "something." This is called a generic value and is very similar to generic methods.

The second example is much more interesting. The command shows how lists are created under the covers: it takes an empty list and uses the syntax for creating a cons cell ::. Unlike operators such as +, the :: construct is right associative, which means that it composes values from the right to the left. When reading the expression in that direction, it is easy to see that the snippet constructs a list cell from value 3 and an empty list and then uses the result together with value 7 to construct another cell, and so on. After entering the expression, F# Interactive reports that we created a list of type int list, which is another way of writing the generic type list<int>.

The next two examples use a piece of syntactic sugar F# provides for creating lists. The first one uses square brackets with list elements separated by semicolons, and the second uses dot-dot to create a list containing a range of numbers.

The last example uses cons cells to create a list by appending the values at the beginning of another list. As the output shows, ls5 contains 0 at the beginning and then all elements from the ls4 list.

An important fact about functional lists is that they’re immutable. This means that a created list cannot be modified; it is impossible to add or remove an element. Functions that need to add new elements or remove existing ones always return a new list without modifying the original one. The next section offers more detail on how lists work by showing a C# implementation.

Implementing Functional Lists in C#

To show how a functional list type works, this section presents an implementation of the same functionality in C#. There are several ways for representing the fact that a list can be either empty or have a head and a tail. The object-oriented solution would be to write an abstract class FunctionalList<T> with two derived classes for representing the two cases—for example, EmptyList<T> and ConsCellList<T>. To make the code as simple as possible, this article uses a single class, with property IsEmpty, which denotes whether or not the instance contains a value. Note that every instance of the FunctionalList<T> type contains at most one value. When the instance represents an empty list, it doesn’t contain any value and, when it’s a cons cell, it stores exactly one value.

public class FunctionalList<T> {
    // Creates a new list that is empty
    public FunctionalList() {
        IsEmpty = true;
    }
    // Creates a new list containe value and a reference to tail
    public FunctionalList(T head, FunctionalList<T> tail) {
      IsEmpty = false;
      Head = head;
      Tail = tail;
   }
    // Is the list empty?
    public bool IsEmpty { get; private set; }
    // Properties valid for a non-empty list
    public T Head { get; private set; }
    public FunctionalList<T> Tail { get; private set; }
}

// Static class that provides nicer syntax for creating lists
public static class FunctionalList {
    public static FunctionalList<T> Empty<T>() {
        return new FunctionalList<T>();
    }
    public static FunctionalList<T> Cons<T>
            (T head, FunctionalList<T> tail) {
        return new FunctionalList<T>(head, tail);
   }
}

The FunctionalList<T> class is a generic C# class, so it can store values of any type. It has a property called IsEmpty, which is set to true when creating an empty list using the parameterless constructor. The second constructor takes two arguments, creates a cons cell, and sets IsEmpty to false. The first argument (head) is a value that is stored in the cons cell. The second argument (tail) is a list following the cons cell that is being created. The tail has the same type as the list created, which is written as FunctionalList<T>. The first constructor corresponds to the F# empty list (written as []), and the second one creates a cons cell in the same way as the double colon operator (head::tail).

As already mentioned, functional lists are immutable, so all properties of the class are read only. The implementation uses C# 3.0 automatic properties, which generate a getter and a setter of the property, but the setter is private, so it can’t be used from the outside. To make the type truly read only, the class sets the values of the properties only in constructors. Once a list cell is created, none of its properties can change.

When creating an immutable class using automatic properties, the C# compiler doesn't check whether the class is truly immutable. This is a trade-off for a more convenient syntax than when marking fields using readonly. The fact that there are many different implementation strategies for declaring immutable types demonstrates that immutability is not a language feature but a concept that can be used in different ways.

The sample also includes a nongeneric utility class FunctionalList with static methods that simplify the creation of generic lists by providing methods for creating an empty list (Empty) and for creating a cons cell (Cons). The advantage of using this class is that C# can infer the type arguments for a method call, so the caller doesn’t have to specify the type of values carried by the list, if it’s obvious from the context.

Functional List Processing

When working with lists in functional languages, the typical code for processing a list contains two branches:

A branch that performs an operation when the given list is an empty list
A branch that performs an operation when the argument is a cons cell

The latter branch generally performs a calculation using the head value and recursively processes the tail of the list. This common pattern will be shown later. The first example explores how to write code that chooses between these two branches using pattern matching.

Decomposing Lists Using Pattern Matching

Lists can be decomposed using pattern matching. The pattern matching needs to handle two cases—an empty list and a list containing the head and the tail. This can be done using the match construct, which supports multiple branches. The following code demonstrates how to print a message with the value of the first element or "Empty list" when the list is empty:

match list with 
| []         -> printfn "Empty list"
| head::tail -> printfn "Starting with %d" head

The snippet shows a pattern that matches an empty list on the second line and a pattern that extracts a head (the value of the first element) and a tail (the list appended after the head) on the third line. Both of these patterns are written with exactly the same syntax as when creating lists. An empty list is matched using [], and a cons cell is deconstructed using the ::. The second case is much more interesting because it assigns a value to two new symbols, head and tail. These will contain a number and the rest of the list obtained by decomposing the first cons cell. An empty list doesn’t carry any value, so the first pattern doesn’t bind a value to any symbol; it just signifies that the original list was empty.

Looking back at Figure 1, you can see that the first pattern corresponds to the nil ellipse, which doesn’t contain a value. The second pattern matches the cons cell rectangle and takes out the contents of its two parts. The F# compiler is clever enough to detect that the pattern matching provides patterns for all possible cases. If the snippet didn't include the case that handles an empty list, the compiler would emit a warning that the pattern matching may fail.

The next section combines the pattern matching with recursion and shows how to implement the usual pattern for processing lists.

Summing Numbers in a List with F#

The example in this section is a very simple function that adds all values stored in a list. Using imperative programming in C#, one would probably create a variable called total initialized to zero and add values of all elements in a loop. Functional programs should generally avoid mutable values and loops, so a different technique is needed. The function can be implemented using recursion and pattern matching to handle the two cases: when the list is empty and when the list is a cons cell. The following listing shows an F# function sumList and an F# Interactive command to test it:

> let rec sumList list =
      match list with
      | []         -> 0
      | head::tail -> head + sumList tail;;
val sumList : int list -> int

> sumList [ 1 .. 5 ];;
val it : int = 15

As mentioned in an earlier article, recursive functions are declared using let rec instead of simple let. The body of the function contains only the pattern matching construct. The code looks very similar to what was used before to decompose a list. The first branch is simple. If the list is empty, the function returns 0. The second branch is more interesting.

The pattern matching not only selects the execution path, but it also extracts the from the cons cell. Once the execution enters the second branch, head and tail values are already available. This adds to the robustness of the code: it isn't possible to access values that haven’t been matched by a pattern. It sounds trivial, but it prevents the code from accidentally trying to access the (nonexistent) elements of an empty list. Equipped with the two values, the snippet can implement the recursive case. It calls sumRest to process recursively the rest of the list and then adds the current element to the result.

Also, F# type inference was helpful again: the code didn’t explicitly mention any types, but F# still correctly inferred that the function takes a list of integers and returns an integer. The inference algorithm used the fact that the snippet tests whether the list value is an empty list or a cons cell to deduce that the type of the value is a list. Because one branch returns zero, it knows that the whole function returns an integer. The snippet is adding elements of the list together, so F# deduces that the argument is a list containing integers.

How would the same snippet look in C# and how is it manifested as .NET code? The next section shows that by implementing the operation in C#.

Summing Numbers in a List with C#

Pattern matching is a natural construct in functional languages, but there’s no corresponding feature in C#. Whether FunctionalList<T> represents an empty list or a cons cell must be checked using the if statement. Otherwise, the code looks very similar to the previous F# snippet:

int SumList(FunctionalList<int> numbers) {
   if (numbers.IsEmpty) return 0;
   else return numbers.Head + SumList(numbers.Tail);
}

The function can be called as follows:

// Creates list containing 1, 2, 3, 4, 5
var list = FunctionalList.Cons(1, FunctionalList.Cons(2,
   FunctionalList.Cons(3, FunctionalList.Cons(4,
   FunctionalList.Cons(5, FunctionalList.Empty<int>())))));

int sum = SumList(list); // Calculates sum and
Console.WriteLine(sum);  // prints '15' as the result

The SumList method first checks whether the list is empty. If it is nonempty, the method recursively calls itself to calculate the sum of elements in the tail and adds this result to the value stored in the head. Although this is nearly as simple as the F# version, it is not as safe. For example, you could accidentally swap the branches and access the Tail property of an empty list and eventually get the infamous NullReferenceException. F# avoids that by defining the values for accessing the head and the tail inside the pattern, so they can be used only if the pattern matches.

In the snippet, to test the function, you create a list using the utility methods Cons and Empty from the nongeneric FunctionalList class. This is a bit cumbersome, but it could be made nicer by implementing a method that creates a functional list from a normal .NET collection. Running the method on a sample input gives the expected result.

Summary

This tutorial presented working with functional lists in F# and C#. Like many collection types, functional lists are used for storing arbitrary numbers of elements of the same type. What makes them different from other collections is that they are immutable. Once a list is created, it cannot be changed. However, it is easy to create a list that contains additional items at the beginning just by creating a new cons cell.

The article started by showing you how to use lists in F# and how to implement the same data structure in C#. Then, it looked at writing a simple function to sum the elements in a list. By looking at the F# and the corresponding C# version at the same time, the article also explained how functional types are represented in .NET and how to write practical immutable types in C#.

Additional Resources

Lists are an example of immutable functional type, but immutability is used more widely in functional programming. The following articles discuss immutability in broader terms. They look at the benefits of immutability and, in particular, how it makes programs more readable:

To download the code snippets shown in this article, go to https://code.msdn.microsoft.com/Chapter-1-Introducing-F-c967460d