layout: true <footer> <span class="icon github"> <svg version="1.1" class="github-icon-svg" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" x="0px" y="0px" viewBox="0 0 16 16" enable-background="new 0 0 16 16" xml:space="preserve"> <path fill-rule="evenodd" clip-rule="evenodd" fill="#C2C2C2" d="M7.999,0.431c-4.285,0-7.76,3.474-7.76,7.761c0,3.428,2.223,6.337,5.307,7.363c0.388,0.071,0.53-0.168,0.53-0.374c0-0.184-0.007-0.672-0.01-1.32c-2.159,0.469-2.614-1.04-2.614-1.04c-0.353-0.896-0.862-1.135-0.862-1.135c-0.705-0.481,0.053-0.472,0.053-0.472c0.779,0.055,1.189,0.8,1.189,0.8c0.692,1.186,1.816,0.843,2.258,0.645c0.071-0.502,0.271-0.843,0.493-1.037C4.86,11.425,3.049,10.76,3.049,7.786c0-0.847,0.302-1.54,0.799-2.082C3.768,5.507,3.501,4.718,3.924,3.65c0,0,0.652-0.209,2.134,0.796C6.677,4.273,7.34,4.187,8,4.184c0.659,0.003,1.323,0.089,1.943,0.261c1.482-1.004,2.132-0.796,2.132-0.796c0.423,1.068,0.157,1.857,0.077,2.054c0.497,0.542,0.798,1.235,0.798,2.082c0,2.981-1.814,3.637-3.543,3.829c0.279,0.24,0.527,0.713,0.527,1.437c0,1.037-0.01,1.874-0.01,2.129c0,0.208,0.14,0.449,0.534,0.373c3.081-1.028,5.302-3.935,5.302-7.362C15.76,3.906,12.285,0.431,7.999,0.431z"/> </svg> </span> <a href="https://github.com/sikoried"><span class="username">sikoried</span></a> </footer> --- # Introduction to Functional Programming Korbinian Riedhammer --- # Functional Programming ## Immutable Objects ## Functions as First-Class Citizens --- # Immutable Objects If objects cannot be changed after their creation, parallelization becomes much easier. `java.lang.String` - no methods to change instance - always returns _new_ instance `final` modifier for attributes and variable, sort of: - only prevents overwriting of primitive type or reference - object may still be mutated .skip[ > No mutation means no `for`/`while`! ] --- # Functions as First-Class Citizens ```java @FunctionalInterface interface Function<A, B> { B apply(A obj); } ``` ```java Function<Integer, Integer> square1 = new Function<Integer, Integer>() { @Override public Integer apply(Integer i) { return i * i; } } ``` Or shorter as lambda expression `(arglist) -> { block; }` ```java Function<Integer, Integer> square2 = (Integer i) -> { return i * i }; ``` Or even shorter, for single instructions ```java Function<Integer, Integer> square3 = i -> i * i; ``` --- # Why Functional Programming? ## Immutability simplifies parallelization ## Separation of Concerns Functions as first-class citizens help to separate the iteration logic from the actual business logic. --- # Example Say you want to - retrieve all students from a database, - filter out those who took _Softwarearchitektur_, - load their transcript of records from another database - print all class names --- # Iterative Solution ```java for (Student s : getStudents()) { if (s.getClasses().contains("Softwarearchitektur")) { ToR tor = db.getToR(s.getMatrikel()); for (Record r : tor) { System.out.println(r.getName()); } } } ``` --- # A Simple Immutable List `head` stores the data, `tail` links to the next element. The end of the list is explicitly modeled. ```java class List<T> { final T head; final List<T> tail; private List(T el, List<T> tail) { this.head = el; this.tail = tail; } boolean isEmpty() { return head == null; } // ... } ``` --- # Some Helper Functions Some factory functions for convenience: ```java class List<T> { // ... static <T> List<T> empty() { return new List<T>(null, null); } static <T> List<T> list(T elem, List<T> xs) { return new List<>(elem, xs); } static <T> List<T> list(T... elements) { if (elements.length == 0) return empty(); int i = elements.length - 1; List<T> xs = list(elements[i], empty()); while (--i >= 0) xs = list(elements[i], xs); return xs; } } ``` --- # Recursive Sort Algorithms --- # Recursive Sort Algorithms ## Insertion Sort ```java static <T extends Comparable<T>> List<T> isort(List<T> xs) { if (xs.isEmpty()) return xs; else return insert(xs.head, isort(xs.tail)); } private static <T extends Comparable<T>> List<T> insert(T x, List<T> xs) { if (xs.isEmpty()) return list(x, empty()); else { if (x.compareTo(xs.head) < 0) return list(x, xs); else return list(xs.head, insert(x, xs.tail)); } } ``` --- # Recursive Sort Algorithms ## Merge Sort ```java static <T extends Comparable<T>> List<T> msort(List<T> xs) { if (xs.isEmpty()) return xs; // no element at all else if (xs.tail.isEmpty()) return xs; // only single element else { int n = length(xs); List<T> a = take(xs, n/2); List<T> b = drop(xs, n/2); return merge(msort(a), msort(b)); } } private static <T extends Comparable<T>> List<T> merge(List<T> xs, List<T> ys) { if (xs.isEmpty()) return ys; else if (ys.isEmpty()) return xs; else { if (xs.head.compareTo(ys.head) < 0) return list(xs.head, merge(xs.tail, ys)); else return list(ys.head, merge(xs, ys.tail)); } } ``` --- # Anonymous Classes, Lambda, References ```java static <A> void forEach(List<A> xs, Consumer<A> c) { if (xs.isEmpty()) return; else { c.accept(xs.head); forEach(xs.tail, c); } } ``` And here's a `Consumer` that prints elements to `System.out`: ```java List<Integer> xs = list(1, 2, 3, 4); forEach(xs, new Consumer<Integer>() { @Override public void accept(Integer i) { System.out.println(i); } }); // or shorter with lambda forEach(xs, i -> System.out.println(i)); // or even shorter with method references forEach(xs, System.out::println); ``` --- # Example ### Iterative Solution (see earlier slide) ```java for (Student s : Database.getStudents()) { if (s.getClasses().contains("Softwarearchitektur")) { Transcript tr = Database.getToR(s.getMatrikel()); for (Record r : tr) System.out.println(r); } } ``` --- # Example ### Functional Solution ```java Database.getStudents().stream() .filter(s -> s.getClasses().contains("Softwarearchitektur")) .map(Student::getMatrikel) .map(Database::getToR) .flatMap(t -> t.records.stream()) // stream of lists to single list .forEach(System.out::println); ``` --- .skip.center[  ]