Συναρτήσεις και ροές

Διομήδης Σπινέλλης
 Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Συναρτησιακός προγραμματισμός

Εκφράσεις λάμδα

(a) -> {  return a * a; }
(a, b) -> {  return a + b; }
() -> {  return true; }

Διαθέσιμοι τύποι

Το πακέτο java.util.function ορίζει μια σειρά από διεπαφές FunctionalInterface:

Οι παραπάνω μπορούν κατά περίπτωση να εξειδικευτούν παραπάνω με ένα από τα προθέματα: Bi (δέχεται δύο ορίσματα)· Int, Long, Double (τύπος ορίσματος)· Το (τύπος επιστροφής).

Μέθοδοι σε συναρτήσεις

Οι παρακάτω μέθοδοι είναι διαθέσιμες ανάλογα με το αντικείμενο.

Παράδειγμα λάμδα

import java.util.function.Function;

class Lambda {
    public static void main(String args[]) {
        // Assign lambda to variable
        Function<Integer, Integer> square = (a) -> a * a;
        // Apply function to value
        System.out.println(square.apply(2));

        // Pass function to method and obtain function result
        Function<Integer, Integer> fourthPower = square.compose(square);
        System.out.println(fourthPower.apply(2));
    }
}

Μέθοδοι ως συναρτήσεις

Μέθοδοι που ικανοποιούν μια διεπαφή Functional μπορούν να χρησιμοποιηθούν ως τέτοιες με τη χρήση του συμβόλου ::. 
import java.util.function.UnaryOperator;
import java.math.BigInteger;

// Methods compatible with a functional interface
class FunctionalFactorial {
    public static BigInteger factorial(BigInteger i) {
        if (i.equals(BigInteger.ZERO))
            return BigInteger.ONE;
        else
            return i.multiply(factorial(i.subtract(BigInteger.ONE)));
    }

    public BigInteger instanceFactorial(BigInteger n) {
        return factorial(n);
    }

    // Prints 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
    public static void main(String args[]) {
        UnaryOperator<BigInteger> f;

        f = FunctionalFactorial::factorial;
        System.out.println(f.apply(new BigInteger("100")));

        f = new FunctionalFactorial()::instanceFactorial;
        System.out.println(f.apply(new BigInteger("100")));
    }
}

Παράδειγμα σύνθεσης μεθόδων

import java.util.function.DoubleUnaryOperator;
import java.util.function.Function;
import static java.lang.Math.abs;
import static java.lang.Math.PI;

class Inverse {
    public static void main(String args[]) {
        Function<DoubleUnaryOperator, DoubleUnaryOperator> inverse =
            f -> x -> 1. / f.applyAsDouble(x);

	DoubleUnaryOperator cot = inverse.apply(Math::tan); // συνεφαπτομένη
	DoubleUnaryOperator sec = inverse.apply(Math::cos); // τέμνουσα
	DoubleUnaryOperator csc = inverse.apply(Math::sin); // συντέμνουσα

        final double EPSILON = 1e-15;
        assert abs(sec.applyAsDouble(0) - 1) < EPSILON;
        assert abs(csc.applyAsDouble(PI / 2) - 1) < EPSILON;
        assert abs(cot.applyAsDouble(PI / 4) - 1) < EPSILON;
    }
}

Ορισμός τύπων συναρτήσεων


@FunctionalInterface
interface TripletChooser <T> {
    T choose(T a, T b, T c);
}

class TripletChooserExample {
    public static void main(String args[]) {
        TripletChooser<String> getFirst = (a, b, c) -> a;
        System.out.println(getFirst.choose(args[0], args[1], args[2]));
    }
}

Παράδειγμα χρήσης τύπου συνάρτησης


@FunctionalInterface
interface Combiner {
    int combine(int a, char operator, int b);
}

public class CombinerExample {
    public static void main(String[] args) {
        Combiner arithmeticCombiner = (a, operator, b) -> {
            switch (operator) {
                case '+': return a + b;
                case '*': return a * b;
                default: throw new IllegalArgumentException("Invalid operator for arithmetic: " + operator);
            }
        };

        Combiner bitwiseCombiner = (a, operator, b) -> {
            switch (operator) {
                case '+': return a | b;
                case '*': return a & b;
                default: throw new IllegalArgumentException("Invalid operator for bitwise: " + operator);
            }
        };

        // Verify Arithmetic Combiner
        assert arithmeticCombiner.combine(5, '+', 3) == 8;
        assert arithmeticCombiner.combine(5, '*', 3) == 15;

        // Verify Bitwise Combiner
        assert bitwiseCombiner.combine(5, '+', 3) == 7;
        assert bitwiseCombiner.combine(5, '*', 3) == 1;
    }
}

Ροές

Μια ροή (stream) είναι μια επεξεργάσιμη ακολουθία ενός απροσδιόριστου αριθμού στοιχείων. Σε σχέση με μια συλλογή η ακολουθία έχει τις παρακάτω ιδιότητες.

Τύποι ροών

Ο τύπος Optional

Η παραμετρική κλάση java.util.Optional περιέχει μια τιμή τύπου T που μπορεί και να απουσιάζει.

Χρήσιμες μέθοδοι

Πηγές ροών

Ενδιάμεση επεξεργασία ροών

Τελική επεξεργασία ροών

Λέξεις κειμένου: Knuth vs McIlroy

Donald Knuth Douglas McIlroy

Σχετικά είναι αυτή η εργασία (https://dl.acm.org/doi/pdf/10.1145/5948.315654), αυτό το κόμικ (https://comic.browserling.com/97) και αυτό το βίντεο (https://www.youtube.com/watch?v=kQKrmDLvijo).

Παράδειγμα: Λέξεις κειμένου

/*
 * Output ordered list of a file's unique words
 */

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.stream.Stream;
import java.io.IOException;

class UniqueWords {
    public static void main(String args[]) {
        if (args.length != 1) {
            System.err.println("Usage: UniqueWords file");
            System.exit(1);
        }

        try {
            Files
                .lines(Paths.get(args[0]))
                .flatMap(line -> Stream.of(line.split("\\W+")))
                .sorted()
                .distinct()
                .filter((x) -> x.length() > 0)
                .forEach(System.out::println);
        } catch (IOException e) {
            System.err.println("Error reading line: " + e.getMessage());
            System.exit(1);
        }
    }
}

Παράδειγμα: εκτίμηση πληθάριθμου


/**
 * Estimate the number of distinct elements in a data stream
 * (F0 estimation problem) based on the algorithm published in the
 * Proceedings of 30th Annual European Symposium on Algorithms (ESA 2022)
 * https://doi.org/10.48550/arXiv.2301.10191
 */

import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class F0Estimator {

    // Probability to add an element
    private double p = 1.0;

    /**
     * Estimate number of unique elements in the passed stream
     * @param storageSize The storage to use
     */
    public <T> long uniqueElements(Stream<T> stream, int storageSize) {
        final float LOAD_FACTOR = 0.5f;

        Set<T> X = new HashSet<>(storageSize , LOAD_FACTOR);
        Random random = new Random();

        stream.forEach(element -> {
            // Ensure element is in the set with probability p
            if (random.nextDouble() < p)
                X.add(element);
            else
                X.remove(element);

            if (X.size() >= storageSize) {
                // Randomly keep each element in X with probability 1/2
                X.removeIf(e -> random.nextDouble() < 0.5);
                p /= 2;
                if (X.size() >= storageSize) {
                    throw new IllegalStateException("Threshold exceeded after sampling");
                }
            }
        });

        return (long) (X.size() / p);
    }

    public static void main(String[] args) {
        // Create a Random instance
        Random random = new Random();

        // Create a stream of many random integers
        Stream<Integer> stream = IntStream
            .generate(random::nextInt).limit(1_000_000_000)
            .map(i -> i & 0xffff)
            .boxed();

        final int STORAGE_SIZE = 1000;

        var estimator = new F0Estimator();

        long uniqueCount = estimator.uniqueElements(stream, STORAGE_SIZE);
        System.out.println("Estimated number of unique elements: " + uniqueCount);
    }
}

Η μέθοδος Newton-Raphson

Η προσεγγιστική μέθοδος Newton-Raphson μας επιτρέπει να βρούμε τη ρίζα οποιασδήποτε πραγματικής συνάρτησης. x n+1 = x n - f ( x n ) f ′ ( x n )

Τετραγωνική ρίζα με Newton-Raphson

Παράδειγμα: Υλοποίηση √2 με NR

Το παρακάτω παράδειγμα υπολογίζει τη √2 δημιουργώντας μια άπειρου μήκους ακολουθία με διαδοχικά καλύτερες προσεγγίσεις.

import java.util.Optional;
import java.util.function.Predicate;
import java.util.function.DoubleFunction;
import java.util.stream.Stream;


/** Find a square root using the Newton-Raphson approximation */
class SquareRoot {

    /** Obtain successive approximations of a function's root using the
     * Newton-Raphson method. */
    static class NewtonRaphson {
        /** f(x) and f'(x) */
        DoubleFunction fx, fdx;

        NewtonRaphson(DoubleFunction fx, DoubleFunction fdx) {
            this.fx = fx;
            this.fdx = fdx;
        }

        /** Return next approximation, given the previous one */
        Double nextApproximation(double previous) {
            // xₙ₊₁ = xₙ - f(xₙ) / f′(xₙ)
            return previous - (double)fx.apply(previous) / (double)fdx.apply(previous);
        }
    }

    /** Test whether successive parts of a series differ more than a value */
    static class NotWithin implements Predicate<Double> {
        /** Previous value in series */
        Optional<Double> previous = Optional.empty();
        /** Difference value above which the test method returns true */
        Double epsilon;

        NotWithin(double d) {
            epsilon = d;
        }

        /**
         * Return true if successive parts of the series do not differ by
         * less than the specified epsilon.
         */
        @Override
        public boolean test(Double d) {
            boolean r;

            if (previous.isPresent())
                r = (Math.abs(previous.get() - d) > epsilon);
            else
                r = true;
            previous = Optional.of(d);
            return r;
        }
    }

    public static void main(String args[]) {
        final double SQRT_TO_FIND = 2;
        DoubleFunction fx = (x -> x * x - SQRT_TO_FIND); // f(x) = x² - α
        DoubleFunction fdx = (x -> 2 * x); // f'(x) = 2x
        var rootTwo = new NewtonRaphson(fx, fdx);
        var greaterThanEpsilon = new NotWithin(1e-15);

	// SQRT_TO_FIND is also our first approximation
        System.out.println(Stream.iterate(SQRT_TO_FIND, rootTwo::nextApproximation)
            .dropWhile(greaterThanEpsilon)
            .findFirst()
            .get());
    }
}

Άσκηση: συναρτήσεις και ροές

Άσκηση 17

Μπορείτε να κατεβάσετε το αντίστοιχο αρχείο και να στείλετε τους βαθμούς σας από τους δεσμούς που βρίσκονται στη σελίδα των ασκήσεων.

Βιβλιογραφία

Περιεχόμενα