List Comprehensions in Java
Build sets in mathematical set-builder notation with Java, like { x * 2 | x E {1,2,3,4} ^ x is even }. Now in use in the jComprehension java library.
Full article: List%20Comprehensions%20in%20Java.pdf
ABSTRACT
In many programming languages, such as Haskell or python, it is popular to write list comprehensions, like we write in algebra
as the list of all even numbers in the set of real numbers. This article proposes an implementation of list comprehensions in Java, and then provides the implementation of the functions map and filter using the proposed code. Also, it supports binding more than one variable to the list’s definition, so we will be able to implement lists of cartesian products and also to add a relation that must hold between the two variables, like
INTRODUCTION
We may remember from algebra that we can define lists as lists comprehensions, which uses a special notation called set-builder notation. For example,
denotes the set of all pairs (x,y) such that x and y are real numbers and the product of both numbers equals the sum.
Today, this syntactic construct is integrated in many programming languages, such as
Haskell
[x * 2 | x <- [0 .. 99], x * x > 3]python
S = [2*x for x in range(100) if x**2 > 3]C#
var ns = Enumerable.Range(0, 100) .Where(x => x*x > 3) .Select(x => x*2);Scala
val s = for (x <- Stream.from(0); if x*x > 3) yield 2*xRuby
(0..100).select { |x| x**2 > 3 } .map { |x| 2*x }
and more. But the Java language does not provide a syntactic construct for this concept.
The usage of list comprehensions in Haskell motivated this article. Bringing the set-builder notation to Java, this different way of thinking problems. Instead of using for or while statements in your programs, you may work with map and filter functions, but take into account that thinking problems as list comprehensions is also another good way to practice programming.
The structure of this article follows:
1. Set-builder notation and list comprehensions definitions as we saw in algebra.
2. Some words about the implementation of Haskell’s list comprehensions. The implementation of map and filter with list comprehensions in Haskell.
3. The proposed implementation of list comprehensions in Java. The implementation of map, filter and the cartesian product with our new list comprehensions.
4. Discussion. Is this useful at industrial level? Possible enhancements and future work.
SET-BUILDER NOTATION
In set theory there is a popular way of defining sets: set-builder notation. Any list defined in this way is called a list comprehension. For example, let’s define the set of all integers that are even and are bigger or equals than 5
Which is read as give me the set of all x such that x belongs to the set of the integer numbers, x is even and x is greater than 5.
Going formal, a set is composed by three sections: a variable, a colon or vertical bar separator, and a logical predicate, which are contained in curly brackets. We may also quantify variables, either by using the existential quantifier, like we use in this definition of the set of all natural even numbers
or the universal quantifier, negations, etc.
Sometimes, we have to decide if we want our set-builder notation to be able to quantify not only elements that belong to a set, but also under sets as well. If we do this, we may encounter some situations like the one described as the Russell’s Paradox
which is read as give me the set of all sets S such that S does not contain themselves.
Let’s write the functions map and filter with the set-builder notation we learned. For the first one, we want the set of all the elements that are in a set S but with some transformation applied, let’s say the function f which holds
We could write our version of map like this(with some syntax sugar on the variable section)
And now we can do the same for the filter function
where x must belong to the set S and hold the predicate
LIST COMPREHENSIONS IN HASKELL
Haskell is one of the programming languages that supports writing list comprehensions. Let’s consider the example
[toUpper c | c <- s]
where s is a string such as “Hello” (s :: String). Strings in Haskell are lists of characters; the generator c <- s feeds each character of s in turn to the left-hand expression toUpper c, building a new list. The result of this list comprehension is “HELLO”.
And for multiple generators, we may have
[(i,j) | i <- [1,2], j <- [1..4]]
yielding the result
[(1,1),(1,2),(1,3),(1,4),(2,1),(2,2), (2,3),(2,4)]
In Haskell, list comprehensions are translated into equivalent definitions in terms of map, and concat. The translation rules are
[e |True] = [e]
[e | q] = [e | q, True]
[e | b, Q] = if b then [e | Q] else []
[e | p <- xs, Q] = let ok p = [e | Q] ok _ = [] in concat (map ok xs)
Now, we can write the functions map and filter as a list comprehensions as we did on the previous section
map f xs = [f x | x <- xs]
filter p xs = [x | x <- xs, p x]
LIST COMPREHENSIONS IN JAVA
Here is the proposed solution for list comprehensions in Java, where a new class ListComprehension has been added.
would be now expressed in Java as
Note that we are using lambdas here, so Java 8 is required.
One of the main goals when defining this Java API is that we want the user to read this code and read the same concepts as in the set-builder algebraic notation: give me the set (or list comprehension) of all x such that x belongs to the list of [1,2,3,4] and x is even.
And if you want to modify the output of the expression with some function, for example
we can write it in Java as
Now we can introduce our implementation of the functions map and filter with our new library
We have also the method is as an alias for holds.
Let’s consider now the case of binding two variables, like when doing the cartesian product. With mathematical syntax this would look like
and in Java
And what if we want to add a relation that must hold over those two variables? Like
That’s achieved by writing
The source code my be found at https://github.com/farolfo/list-comprehensions-in-java. Note how the code does not contain any for, while or if, this project has been developed only using the functions map and filter.
DISCUSSION
We got able to implement the functions map and filter using list comprehensions written in set-builder notation, Haskell and Java code, the latest one with an implementation of this article. We were also able to bind more than one variable, and write the cartesian product of two sets of integers and add a relation between the variables.
But our new implementation lacks of some functionality though, such as quantifiers exists and for-all under elements, quantifiers under sets (which we do have in set-builder notation), among others. Could it be possible to express quantification under sets in the Java implementation? How the Russells’s Paradox case would behave?
Another thing to take into consideration is the usage of list comprehensions in industrial production code. We have seen how Java adopted some functional programming fundamentals in its newer releases (Java 8), such as lambdas, map, filter, etc; may be is not too crazy to think that Java will adopt list comprehensions at some point, as Scala, Clojure and other programming languages have done.
REFERENCES
https://en.wikipedia.org/wiki/Set-builder_notation
https://wiki.haskell.org/List_comprehension
Philip Wadler, Comprehending Monads University of Glasgow
