Functional Programming in Java

Past, Present, and Future

Martin Snyder / @MartinSnyder

Example Functions

\[\begin{aligned} x & = f(g) \\ y & = f(h) \\ z & = g(y) \\ \omega & = sin(\theta) \\ state' & = f(state, input) \end{aligned} \]

Properties of Mathematical Functions

  • Behavior Dependant Solely on Parameters
  • Consistent Evaluation
  • Explicit Dependencies
  • Factorable & Composable

Implications of Functions

  • Immutability
    • Persistent Data Structures
      • Recursion
        • Higher Order Functions
    • Expressions
      • Referential Transparency
        • Lazy Evaluation

Definition - Immutable

not capable of or susceptible to change
- merriam-webster.com

Benefits of Immutability

  • No unexpected manipulations
  • Sharing instead of copying
  • Trivial caching
  • Multi-threaded Accessible
  • Reusable object instances

Immutability in Java

  • final keyword
  • Strings
  • Numerics
  • Guava Collection
  • Java 8 - Streams
  • Java 9 - Collection factory methods

Java Reusable Object Instances

Source

              String one = "one";
              String two = "two";
              String compiledString = "onetwo";
              String runtimeString = one + two;
              String optimizedString = runtimeString.intern();
Output

              compiledString and runtimeString are equal but not the same
              compiledString and optimizedString instances are the same

Java Immutable Transformations

Source

              Integer[] intArray = { 1, 2, 3, 4, 5 };
              int magicNumber = Arrays
                .stream(intArray)
                .map(i -> i * 2)
                .filter(i -> i > 5)
                .reduce((acc, i) -> acc + i)
                .get();

              System.out.println("The magic number is " + magicNumber);
Output

              The magic number is 24

Java Immutable Collections

Source

              List<Integer> intList = List.of(1, 2, 3, 4, 5);
              intList.add(6);
Output

              Exception in thread "main" java.lang.UnsupportedOperationException
                at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:72)
                at java.base/java.util.ImmutableCollections$AbstractImmutableCollection.add(ImmutableCollections.java:76)
                at com.martinsnyder.fpjava.ImmutableCollections.main(ImmutableCollections.java:8)

The Perils of Mutability

The Perils of Mutability


                public class Person {
                  public String givenName;
                  public String familyName;
  
                  public boolean equals(Object o) { ... }
                  public int hashCode() { return Objects.hash(givenName, familyName); }
                  public String toString() { return givenName + " " + familyName; }
                }

The Perils of Mutability

Source

                Person martin = new Person("Martin", "S");
                Set<Person> people = new HashSet<>();
        
                people.add(martin);
                martin.givenName = "Marty";
                people.add(martin);
                Set<Person> peopleCopy = new HashSet<>(people);
Output

                people                           : [Marty S, Marty S]
                people.contains(... "Martin" ...): false
                people.size()                    : 2
                peopleCopy.size()                : 1

Definition - Persistent data structure

In computing, a persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable...
- wikipedia.org

Persistent Data Structure


              public interface List<T> {
                T head();
                List<T> tail();
                boolean isEmpty();
              }

Persistent Data Structure


              class Empty<T> implements List<T> {
                public T head() { throw new RuntimeException(".head() invoked on empty list"); }
                public List<T> tail() { throw new RuntimeException(".tail() invoked on empty list"); }
                public boolean isEmpty() { return true; }
              }

              class Node<T> implements List<T> {
                private final T item;
                private final List<T> next;
        
                public T head() { return item; }
                public List<T> tail() { return next; }
                public boolean isEmpty() { return false; }

                Node(T item, List<T> next) { ... }
              }

Definition - Recursion

Recursion (adjective: recursive) occurs when a thing is defined in terms of itself or of its type ... The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition.
- wikipedia.org

Recursive Algorithm


              static <T> int length(List<T> l) {
                if (l.isEmpty()) {
                  return 0;
                }
                else {
                  return 1 + length(l.tail());
                }
              }

Definition - Higher-order function

A higher-order function is a function that does at least one of the following:
  • takes one or more functions as arguments (i.e. procedural parameters)
  • returns a function as its result.
- wikipedia.org

Generalized Recursion (Fold)


              interface Combiner<R, T> {
                R combine(R r, T t);
              }
          
              static <R, T> R fold(R acc, List<T> l, Combiner<R, T> combiner) {
                if (l.isEmpty()) {
                  return acc;
                }
                else {
                  R nextAcc = combiner.combine(acc, l.head());
                  return fold(nextAcc, l.tail(), combiner);
                }
              }

Using Fold


              static <T> int length(List<T> l) {
                return fold(0, l, (acc, next) -> acc + 1);
              }

              static <T> String listToString(List<T> l) {
                return fold("", l, (acc, next) -> acc + next.toString());
              }

              static int sum(List<Integer> l) {
                return fold(0, l, (acc, next) -> acc + next);
              }

Example

Source

              List<Integer> numbers = new Node<>(8, new Node<>(6, new Node<>(7, new Node<>(5, new Node<>(3, new Node<>(0, new Node<>(9, new Empty<>())))))));

              System.out.println("List is " + listToString(numbers));
              System.out.println("lengthRecursive is " + lengthRecursive(numbers));
              System.out.println("Length is " + length(numbers));
              System.out.println("Sum is " + sum(numbers));
Output

              List is 8675309
              lengthRecursive is 7
              Length is 7
              Sum is 38

Definition - Expression

An expression in a programming language is a combination of one or more constants, variables, operators, and functions that the programming language interprets (according to its particular rules of precedence and of association) and computes to produce ("to return", in a stateful environment) another value.
- wikipedia.org

Conditional Assignment vs. Expression

Before

              final int conditionalInt;
              if (someInt % 2 == 0)
                conditionalInt = 17;
              else
                conditionalInt = 20;
After

              final int expressionInt = (someInt % 2 == 0) ? 17 : 20;

Switch Assignment vs. Expression

Before

              final String conditionalString;
              switch (conditionalInt) {
                case 0: conditionalString  = "zero";         break;
                case 1: conditionalString  = "one";          break;
                default: conditionalString = "notZeroOrOne"; break;
              }
After (Java 12 - JEP 325, Java 13 - JEP 354)

              final String expressionString =
              switch (conditionalInt) {
                case 0  -> "zero";
                case 1  -> "one";
                default -> "notZeroOrOne";
              };

Definition - Referential Transparency

An expression is called referentially transparent if it can be replaced with its corresponding value without changing the program's behavior. This requires that the expression be pure, that is to say the expression value must be the same for the same inputs and its evaluation must have no side effects.
- wikipedia.org

Referential Transparency Checker


              interface Combiner<R, T> { R combine(T t1, T t2); }
              interface Invocable<T> { T invoke(); }

              static <T, R> boolean looksReferentiallyTransparent(
                Invocable<T> invocable, Combiner<R, T> combiner) {
                  T singleResult = invocable.invoke();
                  R combinedSingleResult =
                    combiner.combine(singleResult, singleResult);
          
                  R combinedDoubleInvocation =
                    combiner.combine(invocable.invoke(), invocable.invoke());
          
                  return combinedSingleResult.equals(combinedDoubleInvocation);
              }

Referential Transparency Example

Source

              boolean floorLooksRT = looksReferentiallyTransparent(
                  () -> Math.floor(3.4d), Double::sum);
              boolean nanoTimeLooksRT = looksReferentiallyTransparent(
                  System::nanoTime, Long::sum);

              System.out.println("floorLooksRT: " + floorLooksRT);
              System.out.println("nanoTimeLooksRT: " + nanoTimeLooksRT);
Output

              floorLooksRT: true
              nanoTimeLooksRT: false

Definition - Lazy Evaluation

lazy evaluation [...] is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation).
- wikipedia.org

Fibonacci Puzzler

Each new term in the Fibonacci sequence is generated by adding the previous two terms. What is the total sum of the first 17 odd Fibonacci numbers?
Inspired by projecteuler.net

Fibonacci Supplier


              class FibonacciSupplier implements Supplier<Long> {
                long a = 0;
                long b = 1;

                public Long get() {
                  long next = a + b;
                  a = b;
                  b = next;
                  return next;
                }
              }

Puzzler Solution

Source

              Stream<Long> fibStream =
                Stream.generate(new FibonacciSupplier());

              // Sum of first 17 odd fibonacci numbers
              long magicNumber = fibStream
                  .filter(i -> i % 2 != 0)
                  .limit(17)
                  .reduce(0L, Long::sum);

              System.out.println("Solution is " + magicNumber);
Output

              Solution is 257113

Type Systems

Thank You!

Martin Snyder / @MartinSnyder

// Twitter script to format Tweets