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 vs in functional style of programming.
With Java 8 stream API, Java developers got a taste of functional ways to use lists in the form of 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
flatMap(...) are done directly to the list instead of an intermediate object like
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 roughly how they are implemented.
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 innest layer.
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
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
FuncList is a functional list.
Being functional has two implications: it is read-only and it has functional operations.
FuncList is a read-only list.
That means you cannot change its value in place using mutable operations list such as
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
java.util.List requires these methods, there is not much we can do at this point.
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.
with(index, value) method create a new list with the value at the index changed to the given value.
Other methods are
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
FuncListhas functional operations built-in.
The functional operations are operations such as
reduce and the likes
which currently available with
FuncList, these operations are accessible right there in the list.
// Given the structure (read more about Struct here) @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);
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
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
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.
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.
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
because there is no need to convert to
Stream and collect back to a
Caveat: Laziness and Immutability
There are, however, some caveat of doing lazy-evaluated lists in non-functional programming languages
where the non-pure functions can be used with them.
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.
equals(...) method is a termination operation and causes the filtering to process.
As the filtering is random, you get a random result; hence not equals to itself.
If you are using non-pure or expensive functions, there are a few things you can do.
Fist, you may want to finalize the result so it will not be evaluated again.
toImmutableList() or its alias
freeze() can be used to create the final immutable list.
You can also change to eager mode using
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
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 is it implement?
FuncList and its subclasses simply wrap Java
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 does not need to reimplement list and stream -- just use Java's
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
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).
The aims of FunctionalJ is to bring functional programming goodies to Java. List and Map, which are basic but super useful data structure, are used differently in FP and OOP. FunctionalJ implements lazy-evaluated functional list and map in Java and enables Java developers to use List and Map in the functional ways.