by Pierre-Yves SaumontFolding the Universe is actually the title of a book by Peter Engel which is subtitled "Origami From Angelfish to Zen", suggesting that anything in the universe may be modelled out of folded paper. The analogy with computer programming is interesting since, in functional programming, nearly every problem can be solve with folds.
Computer programming is primarily about abstraction. Instead of doing the same basic tasks again and again, we once write programs to performs these tasks, and we can then build larger programs by composing these basic tasks. Probably one difference between functional and imperative programmers is the way they handle task abstractions. Most often, imperative programmers start thinking about abstracting subtasks when they realize that they are repeatedly writing the same code. But the depth of abstraction is often kept quite minimal. The main reason is that higher level abstractions are generally provided by the language. Arithmetic operations on integers, for example, is provided by nearly all programming languages, so there is no need to write specific code to abstract them (although it is possible, and an interesting challenge!).
Loops are another kind of abstraction that is provided by many languages. Most imperative programmers would not believe that there exist programming languages without loops. Is it possible to program without loops? Of course, it is. It is even possible to program with absolutely no control structures.
Maybe you think that it is possible in some very specific languages specially designed for this. Nothing could be more wrong. Take Java, for example. It is perfectly possible to write any program without ever using a for loop, a while loop, a switch case selector, or event an if..else construct. You don’t believe it? Read on.
Not only can you write java programs without any control structure, but you can also completely avoid variables. Is this useful? Well, avoiding variables is indeed very useful to write safer concurrent programs since it frees us from all concurrency problems, such as deadlock, livelocks, stale data, races, corruption and more. But it is also safer for non concurrent programs since you can confidently reuse data knowing that it will not have been altered.
Avoiding control structures also brings many advantages, but it is more difficult to make it evident. Evidence comes with usage. But in all cases, it is a very rewarding challenge. So why not give it a try?
Warning: If you are the kind of programmer who think in terms of best practices, design patterns, productivity through the use of multiple libraries, or if you have ever thought that "this is not the way Java (or anything else) has been intended to be used", or if you think that we should never try to reinvent the wheel, you should probably not continue reading. (By the way, if the wheel had not been reinvented many times, it would still be circular and spinning around its center, so there would be no cars, no trains, nor anything else using modern wheels, but this is another story.)
The challenge
The challenge is to solve a well known computer problem while using no variables (only constants) and no control structures. We can create classes and methods, we can use the arithmetic operations and comparisons. We could do without, but we would have to design a whole number system with operators, based on folds, which is perfectly feasible, but a bit cumbersome. We will use Java 8 Function and BiFunction, because creating ours would be a waste of time (but minimal, since this would need only three lines of code each).
The problem to solve is known as the Knapsack problem. Basically, it consists in packing a knapsack with items in the best possible manner. The knapsack has a maximum capacity, and each item has a name, a weight and a value. The goal is to pack the maximum value in the knapsack without exceeding its capacity. If you want to get an idea of how to solve this in a traditional imperative manner in Java, you can look at this example: Knapsack problem/0-1. I strongly encourage you to look at the example to have an idea of how this problem may be solved in imperative style in just 300 lines of (non reusable) code.
How to handle the problem
First, we will define the business objects. The first thing we will need is a class to represent items. It will be a very basic class:
public class Item {
public final String name;
public final int weight;
public final double value;
public Item(String name, int weight, double value) {
this.name = name;
this.weight = weight;
this.value = value;
}
public String toString() {
return String.format("item(%s, %s, %s)", name, weight, value);
}
}If you don’t like public fields, feel free to make them private and write the corresponding getters. It is absolutely useless, however, just making the code longer. The toString method is for convenience, in order to print the result. In fact, there is absolutely no logic in this class.
Then, we need a class to represent the knapsack:
public class Knapsack {
private final List<Item> items;
private final double value;
private final int weight;
private final int available;
private Knapsack(double value, List<Item> items, int weight, int available) {
this.value = value;
this.items = items;
this.weight = weight;
this.available = available;
}
private Knapsack add(Item item) {
return new Knapsack(this.value + item.value, this.items.cons(item), this.weight + item.weight, this.available - item.weight);
}
private boolean canAccept(Item item) {
return item.weight <= this.available;
}
private Knapsack maxValue(Knapsack that) {
return this.value >= that.value ? this : that;
}
public String toString() {
return String.format("Total value: %s\nTotal weight: %s\nItems:\n%s",
value, weight, items.foldRight("",
(item, string) -> String.format("\t%s\n%s", item, string)));
}
private static Knapsack empty(int capacity) {
return new Knapsack(0.0, List.list(), 0, capacity);
}
private static Knapsack pack(List<Item> items, Knapsack knapsack) {
...
}
public static Knapsack pack(List<Item> items, int knapsackCapacity) {
return pack(items, empty(knapsackCapacity));
}
}As you can see, a Knapsack has four properties: a list of items, a value, a weight, and an available capacity, meaning how much weight can be added before the knapsack is full. The value and weight fields are for convenience and optimization. We could compute them each time we need them, but it would waste time. They are used for memoization of the weight an value, which trades times against memory space.
The constructor is private, and we have only one factory method called empty that creates an empty knapsack. Adding an item to the knapsack is done through the add method, which does not mutate anything but creates and returns a new Knapsack with the updated value. You might argue that the List<Item> is mutated, but it is not, because it is not a Java List. More on this later.
There are three utility methods: canAccept(Item) allows knowing if the knapsack has enough available capacity to receive a given item. The maxValue method compares two Knapsack instances and returns the one with the greatest value. The toString method, of course, returns a readable representation of the knapsack.
The interesting part is the pack method, which takes a list of items and a Knapsack and returns the Knapsack (in fact a new one) with as much value as possible packed into it. Plus, there is a convenience pack method taking a list of items and a capacity.
Before looking at the core of the problem (the pack method), lets see how this program will be used:
public static void main(String... args) {
int capacity = 400;
final List<Item> items = List.<Item>list()
.cons(new Item("map", 9, 150.0))
.cons(new Item("compass", 13, 35.0))
.cons(new Item("water", 153, 200.0))
.cons(new Item("sandwich", 50, 160.0))
.cons(new Item("glucose", 15, 60.0))
.cons(new Item("tin", 68, 45.0))
.cons(new Item("banana", 27, 60.0))
.cons(new Item("apple", 39, 40.0))
.cons(new Item("cheese", 23, 30.0))
.cons(new Item("beer", 52, 10.0))
.cons(new Item("cream", 11, 70.0))
.cons(new Item("camera", 32, 30.0))
.cons(new Item("tshirt", 24, 15.0))
.cons(new Item("trousers", 48, 10.0))
.cons(new Item("umbrella", 73, 40.0))
.cons(new Item("trousers", 42, 70.0))
.cons(new Item("overclothes", 43, 75.0))
.cons(new Item("notecase", 22, 80.0))
.cons(new Item("sunglasses", 7, 20.0))
.cons(new Item("towel", 18, 12.0))
.cons(new Item("socks", 4, 50.0))
.cons(new Item("book", 30, 10.0));
System.out.println(Knapsack.pack(items, capacity));
}
}As you can see, it is very simple, although the way the list is constructed may look a bit weird. As said earlier, this is not a Java List, but a functional singly linked list. It is represented by an abstract List class and two internal subclasses, Nil and Cons representing the empty and non empty lists. A Nil has no property, while a Cons has a head, which is the first element in the list, and a tail which is the rest of the list:
public abstract class List<A> {
public List<A> cons(A a) {
return new Cons<>(a, this);
}
private static class Nil<A> extends List<A> {
}
private static class Cons<A> extends List<A> {
private final A head;
private final List<A> tail;
private Cons(A head, List<A> tail) {
this.head = head;
this.tail = tail;
}
}
@SuppressWarnings("rawtypes")
private static List NIL = new List.Nil();
@SuppressWarnings("unchecked")
public static <A> List<A> list() {
return NIL;
}
}As you can see, it is a very simple data structure. The parent class defines a method cons adding an element to the list. It has also a static factory method returning an empty list. Note that this method returns an untyped singleton, which means that their can exist only one empty list. As a consequence, all empty lists are considered equals.
Folding
Now you can see how the list of items is constructed. However, you may wonder how we could ever use this list, since there is no mean to access its elements. In fact, we only need one operation: folding the list. Any processing you can imagine on a list may be done with a fold. Folding consists in taking a value of the intended result type (generally different from the elements type) and combining it with an element, then combining the result with the next element and so on until all elements have been processed.
Folding right or left
We can fold a list starting from the left (the head of the list) or for the right (the last element of the list). To fold from the left, we use a left associative operation. To fold from the right, we need… well, you guess.
Here is how we can write a foldRight method. First the signature in the abstract parent List class:
public abstract <B> B foldRight(B z, BiFunction<A, B, B> f);The z parameter is the starting result. It is called z by convention, meaning "zero", by analogy with the starting result for the sum of a list of integers.
The operation used for the fold is represented by a BiFunction, taking an A (element of the list) and a B the current result) and returning a B (the next current result). In the Nil class, the implementation simply return z, since there is no element to which to apply the function:
public <B> B foldRight(B z, BiFunction<A, B, B> f) {
return z;
}In the Cons class, the implementation simply combine the head element with the result of a recursive call to fold the tail:
public <B> B foldRight(B z, BiFunction<A, B, B> f) {
return f.apply(head, tail.foldRight(z, f));
}Note that this implementation is recursive, and recursion happens on the stack, so it will blow the stack for lists of more than a few thousands elements. In my book Functional Programming in Java, I show how to make recursion happen on the heap, but this would be a bit too long for this article. Alternatively, you can have a look at this article: Stack safe recursion in Java.
Folding, folding, folding…
With this method, we can solve nearly all the problems we might have to solve. To understand how we can do this, it’s interesting to first show how we can make a copy of the list:
public List<A> copy() {
return foldRight(list(), (a, list) -> list.cons(a));
}We simply start with an empty list and add the elements to it, one after the other, starting from the right.
For our specific Knapsack problem, we need a map method applying a function to all elements of the list. This exactly like a copy, excepted that we apply the function before adding each element to the new list:
public <B> List<B> map(Function<A, B> f) {
return foldRight(list(), (a, list) -> list.cons(f.apply(a)));
}We will also need a flatMap method doing the same thing with a function returning a list. Here is the implementation:
public <B> List<B> flatMap(Function<A, List<B>> f) {
return foldRight(list(), (a, list) -> list.foldRight(f.apply(a), (a2, list2) -> list2.cons(a2)));
}This may look a bit complicated, but it is in fact equivalent to the following, where the concat method is used to create a single list my concatenating two lists:
public <B> List<B> flatMap(Function<A, List<B>> f) {
return foldRight(list(), (a, list) -> list.concat(f.apply(a)));
}
public List<A> concat(List<A> list) {
return foldRight(list, (a, acc) -> acc.cons(a));
}We will also need a method to return the length of the list:
private int length() {
return foldRight(0, (a, length) -> length + 1);
}Here, we ignore the elements, simply adding one to the result at each step. (Note that this is a very inefficient way to get the length of a list. Using memoization is much faster although it uses more memory.)
Eventually, we will need to access the head and the tail of the list. But we can’t simply add methods for this, since we would not know what to return in the Nil class. For the tail, we could return an empty list, but what about the head?
A (temporary!) solution is to return a List<A> for the head, which will either be an empty list, for a Nil, or a list containing a single element, in case of a Cons. Here is the implementation:
public List<A> head() {
int length = this.length();
return foldRight(list(), (a, list) -> length - list.length() != 1
? list.cons(a)
: List.<A>list().cons(a));
}For the tail, we will return a List<List<A>>:
public List<List<A>> tail() {
int length = this.length();
return new Cons<>(foldRight(list(), (a, list) -> length - list.length() == 1
? list
: list.cons(a)), list());
}These methods are really not efficient, but it is just to show that everything can be done with a fold. We will optimize these later by declaring abstract methods in the parent class and writing much simpler implementations in each subclass.
We now have all the elements we need.
The heart of the problem
Now, you think we are left with the hard part: implementing the pack method. First, let’s look at the algorithm:
-
look at the first element. If it does not fit into the knapsack, discard it.
-
if it fits, lets make two different computations:
-
first, add the element to the knapsack and continue with the rest of the list.
-
second, discard the element and continue with the rest of the list.
-
compare the values of the two results, select the highest, and return it.
-
Could’it be simpler? Here is the corresponding implementation:
private static Knapsack pack(List<Item> items, Knapsack knapsack) {
return items.head().flatMap(item -> items.tail().map(itemList -> knapsack.canAccept(item)
? pack(itemList, knapsack).maxValue(pack(itemList, knapsack.add(item)))
: pack(itemList, knapsack))).foldRight(knapsack, (a, b) -> a);
}The only weird thing to remark is that our algorithm returns a list containing the resulting knapsack, so we extract it with foldRight(knapsack, (a, b) → a)
We’re done, and the core of our program has only three lines. (It could be written in only one line!) The List class is not at all specific to our program and could be used as part of a future functional library. The rest of the code (the Item class and the rest of the Knapsack class) belongs to the business model, and is only a description of our business data. Here is an example of what our program displays:
Total value: 1030.0
Total weight: 396
Items:
item(map, 9, 150.0)
item(compass, 13, 35.0)
item(water, 153, 200.0)
item(sandwich, 50, 160.0)
item(glucose, 15, 60.0)
item(banana, 27, 60.0)
item(cream, 11, 70.0)
item(trousers, 42, 70.0)
item(overclothes, 43, 75.0)
item(notecase, 22, 80.0)
item(sunglasses, 7, 20.0)
item(socks, 4, 50.0)
About the head and tail methods
For these methods, we chose to return lists in order to be able to represent the absence of data. The main problem with this approach is that there is no mean to insure that some additional data will not be inserted by mistake in these lists. To avoid this, we generally use a different class, called Option, which is exactly like a List but where the Nil class is called None and the Cons class is called Some and has no tail. Other than this, it is exactly the same, excepted for the fold method which is called something else, like getOrElse and don’t use a function. (Or uses the default "identity" function to be more accurate.) Beside this, it is sometimes difficult to distinguish between real lists (that can have several elements) and "option" lists (that can have at most one). This may make the program more difficult to read. On the other hand, it makes it much easier to compose the two cases, since they are represented by the same type. In a next article, I’ll show in detail what this means.
The limitations of this solution
I have already indicated that since this program is recursive, and recursion in Java occurs on the stack, and since the stack has a very limited sized, this program will not work for much more than two or three thousands items. This may be out of concern, since a knapsack generally contains much less, but the problem is in fact much more general. It could be use to optimized the way to cut ropes or rods in pieces (while minimizing the loss), or to divide any quantity in the most efficient manner.
Recursion is sometimes called the goto of functional programming. This does not mean it should not be used, but that it should be abstracted. This is exactly what foldRight does. In other words, it is perfectly acceptable to use recursion inside the list class, although it probably should be used only once or twice. But using it in a business program is generally a bad practice. Moreover, in the real life, if we are using Java, we might want to optimize the fold for performance, using standard Java loops. In such case, it would be even more important to encapsulate these "dirty" parts in the List class. Or, as I already said, we can make recursion happen on the heap rather that on the stack. To learn how to do this, please refer to my book, Functional Programming in Java, or to this article: Stack safe recursion in Java.
This said, there is a much more radical limitation in this example. If you examine the pack method, you will see that it is bi-recursive, which means it calls itself twice. This means that for the first level, there will be two calls. Each of these two calls will trigger two new calls, for a total of four. It is not difficult to see that this number of calls will grow exponentially. The consequence is that this program will not overflow the stack because it will never run longer enough for this. It will not work for more than around thirty items. To make this program really useful, we must find a way to write it with a single recursive call, or, better, not using recursion at all (beside recursion in the List class). This is what I will show in a next article.