Thinking functionally - Java 8 in Action: Lambdas, Streams, and Functional-Style Programming - page 363

13.2.4. Functional style in practice
Let's start by solving a programming exercise given to beginning students exemplifying
functional style: Given a List<Integer> value, for example, {1, 4, 9}, construct a
List<List<Integer>> value whose members are all the subsets of {1, 4, 9}—in any order. The
subsets of {1, 4, 9} are {1, 4 ,9}, {1, 4}, {1, 9}, {4, 9}, {1}, {4}, {9}, and {}.
There are eight subsets including the empty subset, written {}. Each subset is represented as
type List<Integer>, which means the answer is of type List<List<Integer>>.
Students often have problems thinking how to start and need prompting [ 2 ] with the remark that
“the subsets of {1, 4, 9} either contain 1 or do not.” The ones that don't are simply subsets of {4,
9}, and the ones that do can be obtained by taking the subsets of {4, 9} and inserting 1 into each
of them. This gives an easy, natural, top-down, functional-programming-style encoding in Java.
(A common programmer error is to say that an empty list has no subsets.)
2 Troublesome (bright!) students occasionally point out a neat coding trick involving binary
representation of numbers (the Java solution code corresponds to
000,001,010,011,100,101,110,111). We tell such students to calculate instead the list of all
permutations of a list; for the example {1,4,9} there are six of these.
The solution program produces {{}, {9}, {4}, {4, 9}, {1}, {1, 9}, {1, 4}, {1, 4, 9}} when given {1, 4,
9} as input. Do try it when you've defined the two missing methods.
Let's review what you've just done. You've assumed that the missing methods insertAll and
concat are themselves functional and deduced that your function subsets is also, because no
operation in it mutates any existing structure. (If you're familiar with mathematics, then you'll
recognize this argument as being by induction .)