SC functional programming

software engineering › 6.031 software construction

R26: map, filter, reduce

problems: write a method that finds all the words in the Java files in your project.

Approach 0:

Use recursion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Find all the files in the filesystem subtree rooted at folder.
 * @param folder root of subtree, requires folder.isDirectory() == true
 * @return list of all ordinary files (not folders) that have folder as
 *         their ancestor
 */
public static List<File> allFilesIn(File folder) {
    List<File> files = new ArrayList<>();
    for (File f : folder.listFiles()) {
        if (f.isDirectory()) {
            files.addAll(allFilesIn(f));
        } else if (f.isFile()) {
            files.add(f);
        }
    }
    return files;
}

Goal: design functions that operate over sequences of elements.

Approach 1: abstracting out control flow

Ex 1: Iterator abstraction

Without worrying about the data representations.

1
2
3
for (int ii = 0; ii < files.size(); ii++) {
    File f = files.get(ii);
    // ...
1
2
3
4
Iterator<File> iter = files.iterator();
while (iter.hasNext()) {
    File f = iter.next();
    // ...

Ex 2: map/filter/reduce abstraction

use streams to represent the entire sequence of elements.(java,cpp都有stream的datatype)

  • map : Stream<‍E> × (E → F) → Stream<‍F>

Approach 1.1 higher order functions: pass function in functions.

Java related: call chaining, method reference.

1
2
List.of(1, 4, 9, 16).stream()
    .map(x -> Math.sqrt(x))
1
2
List.of(1, 4, 9, 16).stream()
    .map(Math::sqrt)
1
2
Function<Double,Double> mySquareRoot = Math::sqrt;
mySquareRoot.apply(16.0); // returns 4.0

  • filter : Stream<‍E> × (E → boolean) → Stream<‍E>

  • reduce : Stream<‍E> × E × (E × E → E) → E

    Three design choices in the reduce operation.

    1. whether to require an initial value

      1
      2
      3
      4
      5
      6
      7
      List.of(1,2,3).stream()
          .reduce(0, (x,y) -> x+y)
      // computes (((0+1)+2)+3) to produce the integer 6
        
      List.of(5, 8, 3, 1).stream()
          .reduce(Math::max)
      // computes max(max(max(5,8),3),1) and returns an Optional<Integer> value containing 8

    2. the order in which the elements are accumulated.

    • Depends on the associativity. If non-associative, the order of combination changes.

    1. reduction to another type

      in java: reduce : Stream<‍E> × F × (F × E → F) × (F × F → F) → F

      • an accumulator ⊙ : F × E → F that adds an element from the sequence (of type E) into the growing result (of type F)
      • a combiner ⊗ : F × F → F that combines two partial results, each accumulated from part of the sequence, into a growing result