anchor.diff:  
   Folding 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 an 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 and an interesting challenge!).
  +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 you can write java program 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. 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?
  -
  -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.
  +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 consist 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: https://rosettacode.org/wiki/Knapsack_problem/0-1#Java[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 code.
  +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: https://rosettacode.org/wiki/Knapsack_problem/0-1#Java[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. Although being functional, our program will still be object oriented. The first thing we will need is a class to represent items. It will be a very basic class:
  +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:
   
   [source,java]
   ----
  
positive.code: 
  We simply start with an empty list and add the elements to it, one after the other, starting from the right.
  
  For our specific problem, we will 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 inserting each element in the new list:
  
  [source,java]
  ----
  
negative.code: 
  == 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, https://www.manning.com/books/functional-programming-in-java[Functional Programming in Java], or to this article: http://www.fpinjava.com/2014/12/03/Stack-safe-recursion-in-Java.html[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.