Lazy-Evaluated Functional Lists

Haskel Style List in Java With FunctionalJ.io

Lists and maps are an essential part of programming. These basic data structures, however, are used differently in imperative/OOP than in the functional style of programming. With Java 8 stream APIs, Java developers got a taste of functional ways to use lists in the form of a stream, and it was sweet. The stream API, however, is not exactly how lists are used in the actual functional programming languages like Haskel. In those languages, operations such as map(...), filter(...), flatMap(...) are done directly to the list instead of an intermediate object like Stream; plus, that was done while still being lazy-evaluated. FunctionalJ.io brings in lazy-evaluated functional lists (called FuncList) and maps (called FuncMap) that are much closer in the way done in functional programming languages. This article discusses these functional data structures (though focusing more on the lists and less on the maps) — what are they, how to use them, their benefits, and how they are implemented.

FuncList

As mentioned, FuncList is a lazy-evaluated functional list. This is a mouthful and, for those unfamiliar, it can be unclear what it means. So, let's discuss each of these terms starting from the inner-most layer.

List

With FunctionalJ.io, lists are represented by the class FuncList and its subclasses. FuncList implements Java's List (the java.util.List) interface with most of its functionalities. That means you can almost use it in place of java.util.List. The following code shows that FunctList works just like other lists.

List<tring> counts = FuncList.of("One", "Two", "Three", "Four", "Five");
System.out.println(counts.get(1));  // Two
System.out.println(counts);         // [One, Two, Three, Four, Five]
System.out.println(counts.size());  // 5  

Functional List

FuncList is a functional list. Being functional has two implications: it is read-only and it has functional operations.

Read-Only List

FuncList is a read-only list. That means you cannot change its value in place using mutable operations list such as add, set, insert, remove, clear or sort. Calling these operations will result in a ReadOnlyListException being thrown. It is quite unfortunate that we have to include these methods but throw a runtime exception but since java.util.List requires these methods, there is not much we can do at this point.

Immutable Modification

Modifying in place is not allowed, but immutable modification is. Immutable modification is a process of creating a new object with the change instead of applying the change in place. For example, with(index, value) method create a new list with the value at the index changed to the given value. Other methods are append(...), prepend(...), insertAt(...), excludeAt(...) and similar. Names of these methods are quite descriptive so I will not explains further. It is import to note that all these immutable-modification operations are lazy so no massive copying of data is performed until it is actually needed. The following code demonstrates some of these methods.

List<String> counts = FuncList.of("One", "Two", "Three", "Four", "Five");
System.out.println(counts);                 // [One, Two, Three, Four, Five]
System.out.println(counts.append("Six"));   // [One, Two, Three, Four, Five, Six]
System.out.println(counts.prepend("Zero")); // [Zero, One, Two, Three, Four, Five]
System.out.println(counts.with(4, "5"));    // [One, Two, Three, Four, 5]  

Notice that "Six" was not added to counts (as you don't see "Six" in the later lines) but, rather, new list is created by append("Six") to include "Six" at the end. Same goes with precent ("Zero") and counts.with(4, "5").

Functional Operations

FuncListhas functional operations built-in. The functional operations are operations such as map, filter, flatMap, reduce and the likes which currently available with Stream. With FuncList, these operations are accessible right there in the list.

// Given the structure (read more about Struct here : https://dzone.com/articles/immutable-data-with-functionalio )
@Struct
void Employee(String name, LocalDate birthday, int compensation);
FuncList<Emplyee> employees = ... load employees ...;

// Then, the list of employees can be used as ...
double averageCompensationOfWiseEmplyees
= employees
        .filter  (employee -> employee.birthday.until(today).getYears() > 40)
  .mapToInt(employee -> employee.compensation)
  .average ()
  .orElse  (0);

Lazy Evaluation

With FuncList, both the immutable-modification and functional operations are lazy — meaning that they do not produce concrete intermediate list for each the step. It might be easier to think of Java Stream. There are two kinds of operations in Stream (and in FuncList): intermediate operations and terminal operations. Intermediate operations specify the transformation from one FuncList to another FuncList. Terminal operations produce a result or perform side-effect actions. FuncList is lazy so its intermediate operations do not produce any concrete result or side effect. Therefore, no extra memory or CPU is spent to copy the data from the original list to the new. For example, when the following code is executed, the values of list1 were not copied to list2 at all.

List<String> list1 = FuncList.of("One", "Two", "Three", "Four", "Five");
List<String> list2 = list1.append("Six");
// ^^ No copy of value here and the code run O(1) space and time.  

The copying of value only occurs when the value of list2 is asked. So the following code will result in the copying of value and it will run O(n) space and time.

      System.out.println(list2);  

This laziness also applied with functional operations so when filter and map, for example, is called, nothing actually happens, not until terminal operations like toString() is called. Unlike Stream, FuncList never closes so it can be reused again and again. Using already closed Stream will throw a runtime-exception which is hard to find and can be costly if happen in production. Code written with FuncList is also more readable than with Stream because there is no need to convert to Stream and collect back to a List.

Caveat: Laziness and Immutability

There are, however, some caveats to doing lazy-evaluated lists in non-functional programming languages where the non-pure functions can be used with them. A FuncList is read-only BUT its elements are not necessary "never changes." There are two reasons for this. First, the element itself might change if it is not immutable. Second, if the list is derived from another list, the derivation might not be pure, so it might not always lead to the same result. The following code highlights the behavior.

var cats = FuncList.of("Kitty", "Tigger", "Felix", "Schrödinger's");
var rand         = new Random();
var deadNotAlive = (Predicate<String>))((String s) -> rand.nextBoolean());
var deadCats     = cats.filter(deadNotAlive);
assertNotEquals(deadCats, deadCats);  

Notice that deadCats DOES NOT EQUAL TO deadCats! And that because the filter (if a cat is dead or alive) is random, the equals(...) method is a termination operation and causes the filtering to process. As the filtering is random, you get a random result; hence, it is not always equal to itself.

If you are using non-pure or expensive functions, there are a few things you can do. First, you may want to finalize the result so it will not be evaluated again. The method toImmutableList() or its alias freeze() can be used to create the final immutable list. You can also change to eager mode using eager(). NOTE: eager() will make all immediate operations terminal operations so elements copy will occur on every operation. Once made eager, you can also turn it back to lazy with lazy(). Second, you may want to cache the expensive function using. If you use FunctionalJ.io's Func1, you can just call its memoize() method to cache the value.

var surelyDeadCats = deadCats.toImmutableList();
assertEquals(surelyDeadCats, surelyDeadCats);  

How?

How is it implement? Well, FuncList and its subclasses simply wrap Java Stream. When you do list.map(...), for example, a FuncListDerived is created to capture the original list and the map action. When a terminating operation is called, it asks the original list for its Stream and call map(...) on it then pass the result for later operations. The best advantage of this is that FunctionalJ.io does not need to reimplement list and stream — just use Java's List and Stream; thus, much fewer places for bugs to hide. Plus, any improvement to Stream will automatically be carried forward.

There Is MORE!

There are also additional useful methods does not exist in both List and Stream. More information about those operations can be found on the documentation page. It is also possible to create an infinite list (similar to Scala Seq) using Streamable but that will be discussed later. There is, also, lazy-evaluated functional map (see the documentation page).

Conclusion

The aims of FunctionalJ.io is to bring functional programming goodies to Java. List and map are basic yet super useful data structures and are used differently in FP and OOP. FunctionalJ.io implements lazy-evaluated functional list and map in Java and enables Java developers to use list and map in the functional ways.

Happy coding!

 Nawa Man