Example Functions

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

Benefits of Immutability

• No unexpected manipulations
• Sharing instead of copying
• Trivial caching
• No synchronization issues
• Copies are interchangeable

Immutability in Java

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

Java Reusable Object Instances

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

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

Java Immutable Transformations

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

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

              The magic number is 48

Java Immutable Collections

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

              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

If you don't think managing state is tricky, consider the fact that 80% of all problems in all complex systems are fixed by rebooting.

— stuarthalloway (@stuarthalloway) June 1, 2019

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

                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);

                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...

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.

Recursive Algorithm

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

Aside - Tail Recursion

              static <T> int lengthTailRecursive(List<T> l) {
                return lengthTailR(l, 0);
              }
          
              private static <T> int lengthTailR(List<T> l, int acc) {
                if (l.isEmpty()) {
                  return acc;
                }
                else {
                  return lengthTailR(l.tail(), acc + 1);
                }
              }

Tail Recursion Optimization

• Iterative and tail recursive algorithms can be compiled to the same output
• ... but not in Java

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.

Generalized Recursion (FoldLeft)

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

FoldLeft Application

              static <T> int lengthWithFold(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);
              }

Alternative Fold (FoldRight)

              static <R, T> R foldRight(R acc, List<T> l, Combiner<R, T> combiner) {
                if (l.isEmpty()) {
                  return acc;
                }
                else {
                  R interior = foldRight(acc, l.tail(), combiner);
                  return combiner.combine(interior, l.head());
                }
            }

FoldRight Application

              static <R, T> List<R> map(List<T> l, Transformer<R, T> transformer) {
                return foldRight((List<R>)new Empty<R>(), l, (soFar, el) ->
                  new Node<>(transformer.transform(el), soFar)
                );
            }

Example

              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("Offset List is " + listToString(map(numbers, i -> i > 0 ? i -1: i)));
              System.out.println("lengthRecursive is " + lengthRecursive(numbers));
              System.out.println("lengthTailRecursive is " + lengthTailRecursive(numbers));
              System.out.println("lengthWithFold is " + lengthWithFold(numbers));
              System.out.println("Sum is " + sum(numbers));

              List is        8675309
              Offset List is 7564208
              lengthRecursive is     7
              lengthTailRecursive is 7
              lengthWithFold 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.

Conditional Assignment vs. Expression

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

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

Switch Assignment vs. Expression

              final String conditionalString;
              switch (conditionalInt) {
                case 0: conditionalString  = "zero";         break;
                case 1: conditionalString  = "one";          break;
                default: conditionalString = "notZeroOrOne"; break;
              }

              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.

Referential Transparency Simplified

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

              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);

              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).

Laziness Example - Class Loading

For example, a Java Virtual Machine implementation may choose a "lazy" linkage strategy, where each symbolic reference in a class or interface (other than the symbolic references above) is resolved individually when it is used.

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?

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

              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);

              Solution is 257113

Themes

• Rigor over policy
• Limit possibilities
• Prevent the unexpected

Implications regarding data types

• Mathematical Rigor for Types
  • Algebraic Data Types
    • Pattern Matching

Definition - Algebraic Data Type

In computer programming, especially functional programming and type theory, an algebraic data type is a kind of composite type, i.e., a type formed by combining other types. Two common classes of algebraic types are product types (i.e., tuples and records) and sum types.

Conditional fields

              class Employee {
                String name;
                Date startDate;
                boolean isCurrentEmployee;
                Date endDate;
        
                long getMillisecondsOfService() {
                  if (isCurrentEmployee) {
                    return new Date().getTime() - startDate.getTime();
                  } else {
                    return endDate.getTime() - startDate.getTime();
                  }
                }
              }

Algebraic Data Type Examples

              interface EmploymentDates{}

              class CurrentEmployee implements EmploymentDates {
                Date startDate; }

              class TerminatedEmployee implements EmploymentDates {
                Date startDate;
                Date endDate; }

                sealed interface EmploymentDates{}
  
                record CurrentEmployee(Date startDate)
                  implements EmploymentDates {}
                record TerminatedEmployee(Date startDate, Date endDate)
                  implements EmploymentDates {}

Definition - Pattern Matching

In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern.

Visitor Pattern 1/2

              interface EmploymentDatesVisitor {
                void visit(CurrentEmployee ce);
                void visit(TerminatedEmployee te);
              }
              interface EmploymentDates{
                void visit(EmploymentDatesVisitor visitor);
              }
              class CurrentEmployee implements EmploymentDates {
                Date startDate;
                public void visit(EmploymentDatesVisitor visitor) {
                  visitor.visit(this);
                }
             }

Visitor Pattern 2/2

              class MillisecondsOfServiceVisitor implements EmploymentDatesVisitor {
                long millis;
                public void visit(CurrentEmployee ce) {
                  millis = new Date().getTime() - ce.startDate.getTime(); }
                public void visit(TerminatedEmployee te) {
                  millis = te.endDate.getTime() - te.startDate.getTime(); }
              }

              class EmployeeWithADT {
                long getMillisecondsOfService() {
                  MillisecondsOfServiceVisitor visitor = new MillisecondsOfServiceVisitor();
                  employmentDates.visit(visitor);
                  return visitor.millis;
                }

                String name;
                EmploymentDates employmentDates;        
              }

Enhanced Switch Expressions

              class EmployeeWithADT {
                long getMillisecondsOfService() {
                  return switch (employmentDates) {
                    case CurrentEmployee(var startDate) ->
                      new Date().getTime() - startDate.getTime();
                      
                    case TerminatedEmployee(var startDate, var endDate) ->
                      endDate.getTime() - startDate.getTime();
                  }
                }

                String name;
                EmploymentDates employmentDates;        
              }

Some Words about Optional

• Optional is conceptually (but not actually) an ADT
• Use it to avoid:
  • Sentinel Values
  • Unnecessary Exceptions
  • null

Producing Optional

              static Optional<Double> divide(double numerator
                                            ,double denominator) {
                return denominator == 0
                  ? Optional.empty()
                  : Optional.of(numerator / denominator);
              }
            
              System.out.println("1 / 0 = " + divide(1, 0));
              System.out.println("1 / 3 = " + divide(1, 3));

              1 / 0 = Optional.empty
              1 / 3 = Optional[0.3333333333333333]

Consuming Optional 1/3

              static int safeGet(Optional<Integer> optional, int defaultValue) {
                if (optional.isPresent()) {
                  return optional.get();
                }
                else {
                  return defaultValue;
                }
              }

              optional.orElse(defaultValue);

Consuming Optional 2/3

              static Optional<String> safeToString(Optional<Integer> optional) {
                if (optional.isPresent()) {
                  return Optional.of(optional.get().toString());
                }
                else {
                  return Optional.empty();
                }
              }

              optional.map(Object::toString);

Consuming Optional 3/3

              static Optional<Double> safeDivide(Optional<Integer> numerator, int by) {
                if (numerator.isPresent()) {
                  return divide(numerator.get(), by);
                }
                else {
                  return Optional.empty();
                }
              }

              numerator.flatMap(i -> divide(i, denominator));

Other Opinions 1/3

I wish we'd stop debating OOP vs FP, and started debating individual paradigms. Immutability, encapsulation, global state, single assignment, actor model, pure functions, IO in the type system, inheritance, composition... all of these are perfectly possible in either OOP or FP.

— Mathias Verraes (@mathiasverraes) July 23, 2019

Other Opinions 2/3

Onboarding people new to #Scala can be challenging but most difficult parts are not about syntax, but about the paradigm shift:

1. Immutability
2. Higher-order functions
3. Pervasive map/flatMap (Monads)
4. Suspending effects (Task/IO)
5. Referential transparency
6. Type classes

— Alex Nedelcu (@alexelcu) August 15, 2019

Other Opinions 3/3

Simple Recommendations

• Use final more, especially on raw data objects
• Favor Java-provided immutable collections
• Eliminate sentinel values
• Limit use of ADTs without pattern matching

Less Simple Recommendations

• Don't be in a hurry to unpack an Optional
• Create more containers like Optional
• Experiment with techniques on Project Euler
• Accelerate learning in an FP lang like Elm or Scala
• Read a book AND do the exercises