One of the most elegant and frequently usable data structures in many functional programming languages is immutable linked list based on “cons” pairs.

Immutable linked list can be implemented in different ways and it is not limited to implementation based on cons pair.

Short reminder of immutable list advantages: safe for use by untrusted code, thread-safe and can be used with no risk of race conditions, can be used as a constant, more memory-efficient than his mutable sibling (mutable list).

Understanding “cons"

Term “cons” has been taken from Lisp and means function which constructs a pair of two values or pointers to two values. And it can be thought as a pair or tuple of two values.

Cons pair

The simplest implementation of cons in Java:

package com.scalabledeveloper.concepts.conslist;

class Cons<A, B> {
    final A first;
    final B second;

    Cons(A first, B second) {
       this.first = first;
        this.second = second;
    }

    @Override
    public String toString() {
        return "cons(" + first + ", " + second + ")";
    }
}

It is not ready for production usage! Important methods are not implemented and omitted for readability (equals, hashCode and null-safety checks are required). But it is immutable and easy to use. Example of usage:

package com.scalabledeveloper.concepts.conslist;

public class Main {
    public static void main(String[] args) {
        var cons = new Cons<>(1, 2);

       System.out.println(cons.first);
       // 1
       System.out.println(cons.second);
       // 2
       System.out.println(cons);
       // cons(1, 2)
    }
}

Or, of course, existent implementation of pair or tuple in Java can be used.

Immutable list based on cons

How all this related to elegant immutable linked list?

Implementation of list can be built based on cons pairs. In case of list, the first element of cons points to element or value and the second element points to the remaining part of the list, called tail. List is terminated by nil element, which is also empty list.

Cons list

It does not consumes a lot of memory - new list is an old list as a tail plus a new element as a head. It also provides fast sequential access. There is an example of list construction based on pair:

package com.scalabledeveloper.concepts.conslist;

public class Main {
    public static void main(String[] args) {
        var cons = new Cons<>(1, new Cons(2, new Cons(3, null)));

        System.out.println(cons);
        // cons(1, cons(2, cons(3, null)))
    }
}

In this example null is a trick and not real and empty list. API is still not concise, not usable and requires some improvements.

There is a lot of syntactic sugar and functions in functional programming languages for working with cons lists. In Scala there is List and Nil objects, :: operator instead of cons and a lot of utility functions for working with lists. A couple of examples:

1 :: 2 :: 3 :: Nil
// List(1, 2, 3): scala.collection.immutable.List

List(1, 2, 3)
// List(): scala.collection.immutable.List

Nil
// List(): scala.collection.immutable.List

List(1, 2, 3).sum
// 6: Int

List(1, 2, 3).map(_ * 2)
// List(2, 4, 6): scala.collection.immutable.List

In terms of brevity and conciseness Java is far away from Scala, but it can come near easy.

Basic implementation in Java - ConsList

API design

One example of concise API could be:

package com.scalabledeveloper.concepts.conslist;

import static com.scalabledeveloper.concepts.conslist.ImmutableConsList.listOf;

public class Main {
    public static void main(String[] args) {
        var list = listOf(1, 2, 3);

        System.out.println(list);
        // cons(1, cons(2, cons(3, nil)))

        System.out.println(list.isEmpty());
        // false

        var multiplied = list.map(x -> x * 2);

        System.out.println(multiplied);
        // cons(1, cons(2, cons(3, nil)))
        System.out.println(list);
        // cons(1, cons(2, cons(3, nil)))

        var filtered = listOf(1, 2, 3, 4, 5).filter(x -> x > 2);

        System.out.println(filtered);
        // cons(3, cons(4, cons(5, nil)))
    }
}

Static factory method listOf creates list based on cons pairs:

package com.scalabledeveloper.concepts.conslist;

import java.util.Arrays;

import static com.scalabledeveloper.concepts.conslist.Cons.cons;
import static com.scalabledeveloper.concepts.conslist.Nil.nil;

public abstract class ImmutableConsList<T> {

    public static <T> ImmutableConsList<T> listOf(T... elements) {
        if (elements.length == 0) {
            return nil();
        }

        return cons(elements[0], listOf(Arrays.copyOfRange(elements, 1, elements.length)));
    }
}

If elements are absent empty list (nil) is returned. If there are some elements - cons pair is returned, where head is first element of given array and tail is list of rest elements. To make this function work nil() and cons() functions need to be implemented. Function cons returns pair of head and tail:

package com.scalabledeveloper.concepts.conslist;

import java.util.function.Function;

class Cons<T> extends ImmutableConsList<T> {
    private T head;

    private ImmutableConsList<T> tail;

    private Cons(T head, ImmutableConsList<T> tail) {
        this.head = head;
         this.tail = tail;
    }

    public static <T> Cons<T> cons(T head, ImmutableConsList<T> tail) {
        return new Cons<>(head, tail);
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public T head() {
        return head;
    }

    @Override
    public ImmutableConsList<T> tail() {
        return tail;
    }

    @Override
    public String toString() {
        return "cons(" + head + ", " + tail + ")";
    }
}

And function nil represents empty list:

package com.scalabledeveloper.concepts.conslist;

import java.util.NoSuchElementException;
import java.util.function.Function;

public class Nil<T> extends ImmutableConsList<T> {
    private static Nil instance;

    private Nil() {
    }

    public static <T> Nil<T> nil() {
        if (instance == null) {
            instance = new Nil<T>();
        }

        return instance;
    }

    @Override
    public boolean isEmpty() {
        return true;
    }

    @Override
    public T head() {
        throw new NoSuchElementException("head of empty list");
    }

    @Override
    public ImmutableConsList<T> tail() {
        throw new UnsupportedOperationException("tail of empty list");
    }

    @Override
    public String toString() {
        return "nil";
    }
}

Abstract class represents list API:

package com.scalabledeveloper.concepts.conslist;

import java.util.Arrays;
import java.util.function.Function;

import static com.scalabledeveloper.concepts.conslist.Cons.cons;
import static com.scalabledeveloper.concepts.conslist.Nil.nil;

public abstract class ImmutableConsList<T> {
    public abstract boolean isEmpty();

    public abstract T head();

    public abstract ImmutableConsList<T> tail();

    public static <T> ImmutableConsList<T> listOf(T... elements) {
         // … 
    }
}

Some functions should be added to list API to make such list usable.

Utility functions

Type of suitable algorithms can been seen through solving some problems.

For example, in terms of cons list, sum of elements of list is sum of head and sum of tail. Implemented as it sounds:

package com.scalabledeveloper.concepts.conslist;

import static com.scalabledeveloper.concepts.conslist.ImmutableConsList.listOf;

public class Main {
    public static void main(String[] args) {
        var list = listOf(1, 2, 3);

        System.out.println(sum(list));
        // 6
    }

    public static int sum(ImmutableConsList<Integer> list) {
        return list.isEmpty() ? 0 : list.head() + sum(list.tail());
    }
}

Multiplication of each element by 2:

package com.scalabledeveloper.concepts.conslist;

import static com.scalabledeveloper.concepts.conslist.Cons.cons;
import static com.scalabledeveloper.concepts.conslist.ImmutableConsList.listOf;
import static com.scalabledeveloper.concepts.conslist.Nil.nil;

public class Main {
    public static void main(String[] args) {
        var list = listOf(1, 2, 3);
        
        System.out.println(mulBy2(list));
        // cons(2, cons(4, cons(6, nil)))
    }

    public static ImmutableConsList<Integer> mulBy2(ImmutableConsList<Integer> list) {
        return list.isEmpty() ? nil() : cons(list.head() * 2, mulBy2(list.tail()));
    }
}

Head and tail decomposition approach is very frequent while working with cons list. Last implementation of multiplication can be abstracted to map. Map of elements:

@Override
public <R> ImmutableConsList<R> map(Function<T, R> mapper) {
    return isEmpty() ? nil() : cons(mapper.apply(head), tail.map(mapper));
}
<code>

Map of empty list is empty list: 

<code>
@Override
public <R> ImmutableConsList<R> map(Function<T, R> mapper) {
    return nil();
}

Usage:

package com.scalabledeveloper.concepts.conslist;

import static com.scalabledeveloper.concepts.conslist.ImmutableConsList.listOf;

public class Main {
    public static void main(String[] args) {
        var list = listOf(1, 2, 3);

        System.out.println(list.map(x -> x * 2));
        // cons(2, cons(4, cons(6, nil)))

        System.out.println(list.map(x -> x % 2 == 0 ? "even" : "odd"));
        // cons(odd, cons(even, cons(odd, nil)))

        var languages = listOf("Italian", "Russian", "English");

        System.out.println(languages.map(String::toUpperCase));
        // cons(ITALIAN, cons(RUSSIAN, cons(ENGLISH, nil)))
    }
}

Filtering elements:

@Override
public ImmutableConsList<T> filter(Function<T, Boolean> predicate) {
    if (predicate.apply(head)) {
        return cons(head, tail.filter(predicate));
    } else {
        return tail.filter(predicate);
    }
}

Again, empty list is empty list:

@Override
public ImmutableConsList<T> filter(Function<T, Boolean> predicate) {
    return nil();
}

These functions show immutability and usability of such list. One more example of immutability is drop function:

@Override
public ImmutableConsList<T> drop(int n) {
    if (n <= 0) {
        return this;
    } else {
        return tail.drop(n - 1);
    }
}

Dropping of zero elements is list itself. Dropping at least 1 element is tail. Usage:

package com.scalabledeveloper.concepts.conslist;

import static com.scalabledeveloper.concepts.conslist.ImmutableConsList.listOf;

public class Main {
    public static void main(String[] args) {
        var list = listOf(1, 2, 3);

        System.out.println(list.drop(0));
        // cons(1, cons(2, cons(3, nil)))

        System.out.println(list.drop(1));
        // cons(2, cons(3, nil))

        System.out.println(list.drop(3));
        // nil
    }
}

It is very suitable to convert such list to Java collection to operate with it in case if some feature is missed:

@Override
public Collection<T> toCollection() {
    var collection = new ArrayList<T>();
    collection.add(head);
    collection.addAll(tail.toCollection());

    return Collections.unmodifiableList(collection);
}

For empty list:

@Override
public Collection<T> toCollection() {
    return Collections.emptyList();
}

Iterable is easy to implement through toCollection method:

public abstract class ImmutableConsList<T> implements Iterable<T> {
    // … 

    @Override
    public Iterator<T> iterator() {
        return toCollection().iterator();
    }

    public abstract Collection<T> toCollection();

    // … 
}

And usage:

package com.scalabledeveloper.concepts.conslist;

import static com.scalabledeveloper.concepts.conslist.ImmutableConsList.listOf;

public class Main {
    public static void main(String[] args) {
        var fruits = listOf("Orange", "Apple", "Banana");

        for (var fruit : fruits) {
            System.out.print(fruit + " ");
        }
        // Orange Apple Banana 
    }
}

These implementations are not effective and could cause stack overflow for big lists. And even in Scala you can meet imperative implementation behind the scenes:

sealed abstract class List[+A] extends // … 

// … 

  override def drop(n: Int): List[A] = {
      var these = this
      var count = n
      while (!these.isEmpty && count > 0) {
          these = these.tail
          count -= 1
      }
      these
  }

// … 

}

List, Stream and other interfaces

We can go further and make cons list a friend of Java Collections Framework - to implement List interface. But! There is one problem - Java collections have been developed and considered as mutable collections and it is hard to implement List interface using cons list. For example, how to implement method remove:

public interface List<E> extends Collection<E> {
    // …

    boolean remove(Object o); 

    // ...
}

It does not returns new instance of list without element, it returns result of operation and this is not enough. This is not a bad situation. Java has not been designed as functional programming language and this is normal not to expect functional features from it. But anyway Java has some immutable interfaces which can be implemented, for example it can be Iterable if considered without implementation of Iterator::remove method) or Stream.

Ready Implementations in Java

There is no need to implement all this stuff in Java. Java is mature platform and there is a lot of ready implementations for every taste and color. Implementing such type of collection is good for learning but not for production needs. There is only example of implementations based on cons. For example Google Guava library has a beautiful immutable collections, but implementations is based on java.util.AbstractCollection.

Functional Java

Very good Functional Java library provides implementation of List based on cons pairs with clear and concise API:

import fj.data.List;
import static fj.data.List.list;
import static fj.function.Integers.add;
import static fj.Show.intShow;
import static fj.Show.listShow;

public final class List_map {
    public static void main(final String[] args) {
        final List<Integer> a = list(1, 2, 3);
        final List<Integer> b = a.map(add.f(42));
        final List<Integer> c = a.map(i -> i = 42);
        listShow(intShow).println(b); 
        // [43,44,45]
    }
}

Scala collections

Immutable list implementation in Scala is implemented through cons pairs. The only requirement is to include Scala standard library to Java project and Scala collections can be used directly in Java:

import scala.collection.immutable.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = list(1, 2, 3, 4, 5);

        System.out.println(list);
        // List(1, 2, 3, 4, 5)

        System.out.println(list.map(x -> x * 2));
        // List(2, 4, 6, 8, 10)
    }

    private static <T> List<T> list(T... elements) {
        List<T> list = List.empty();
        for (int index = elements.length - 1; index >=0 ; --index) {
            list = list.$colon$colon(elements[index]);
        }

        return list;
    }
}

But with a lot of limitations, because functions in Scala collections use Scala type system and not Java and this limitation requires to convert from one type to another. For example, filter:

System.out.println(list.filter(x -> (int) x > 2));
// List(3, 4, 5)

But as experiment it is possible.

Performance

Cons list is very fast on head or tail retrieval and prepend operation - it is a constant time. New element in list is old list plus new element, list is not copied. Iteration through head/tail decomposition is also fast.

And there are also downsides of such structure:

Random access costs. It is a linear time.
Update of specific element is also the linear time.

Usage

General advice is to use such kind of immutable data structures as much as possible and until this is possible.

When to use it

Immutable cons list is thread-safe and preferable in multithreaded environment. List can not be modified and can be thought as a constant, this approach facilitates multithreading programming.
Recursive algorithms with head and tail decomposition is very concise when cons list is used.
In case if list is built through time and elements are only prepended to it. Prepend is very cheap operation and if most of operations with list are prepend operations - cons list is suitable.

When not to use it

In case if there is a need in functional style manipulation with lists (map, filter and so on), there is an API in Java - Stream which provides such kind of operations.
In case if random access is required by index, arrays of ArrayList is more preferable.
In case of append operation, it takes linear time to iterate across all list and append element.
In case if list should be modified a lot of time, it can be less performant than mutable sibling with direct mutation in nodes.

Exercises

The best way to learn and understand concept is to practice and perform exercises:

Implement method size which will return the size of the list.
Implement method reverse which will return reversed list. E.g. listOf(1, 2, 3).reverse() will return listOf(3, 2, 1).
Implement method concat which will concatenate 2 lists to one. E.g. listOf(1, 2, 3).concat(listOf(4, 5, 6)) will return listOf(1, 2, 3, 4, 5, 6).
Implement method equals which will compare 2 lists. E.g. listOf(1, 2, 3).equals(listOf(1, 2, 3)) will return true and listOf(3, 2, 1).equals(listOf(1, 2, 3)) will return false.

June 27, 2018

Immutable (Cons) List in Java