Publié par

Il y a 7 années -

Temps de lecture 9 minutes

Programmation fonctionnelle – Solution des exercices du XKE de novembre

Lors du XKE du mois de novembre, j’ai présenté une introduction à la programmation fonctionnelle. Cette présentation fût suivie d’une partie Hands On où les participants ont pu s’essayer (parfois dans la douleur, mais toujours dans la bonne humeur) à ce paradigme avec le langage Java. Je vous propose dans cet article un ensemble de solutions sur les exercices présentés. De quoi occuper vos longues soirées d’hiver.

Hands On 1 : Fonction récursive

Programmer une version de la fonction factorielle.

// test unitaire
fact(0) = 1
fact(1) = 1

fact(5) = 120

fact(10) = 3628800

Réaliser cet exercice en Java seulement puis en utilisant l’interface Function de Guava, dans sa forme récursive simple puis dans sa forme récursive terminale.

Voici l’implémentation en Java qui suit assez bien la définition mathématique récursive de la fonction factorielle.

public static int factorial(int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

Voici l’équivalent avec Guava qui ressemble beaucoup à l’implémentation précédente.

Function<Integer, Integer> factorial = new Function<Integer, Integer>() {
    @Override public Integer apply(Integer n) {
        if (n == 0) return 1;
        else return n * apply(n - 1);
    }
};

Pour utiliser la fonction Guava, il suffit de taper :

Integer result = factorial.apply(5);

Passons à la version récursive terminale en Java.

private static int fact(int n, int k) {
    if (n == 0) return k;
    else return fact(n - 1, n * k);
}

public static int factorial(int n) {
    return fact(n, 1);
}

Et l’équivalent Guava.

public class FactorialFunction implements Function<Integer, Function<Integer, Integer>> {
    @Override
    Function<Integer, Integer> apply(final Integer n) {
        return new Function<Integer, Integer>() {
            @Override
            public Integer apply(Integer k) {
                if (n == 0) return k;
                else return FactorialFunction.this.apply(n - 1).apply(k * n);
            }
        };
    }
}

FactorialFunction fact = new FactorialFunction();
Integer result = fact.apply(5).apply(1); // factorial of 5

La version Guava est étonnement plus complexe au regard de la version Java. Ceci s’explique par deux difficultés :

  1. la fonction factorielle récursive terminale prend deux paramètres,
  2. la fonction factorielle récursive terminale est… récursive.

Pour le premier point, il faut savoir que Guava ne définit que des fonctions ne prenant qu’un seul paramètre en entrée. Pour avoir une fonction prenant en entrée deux paramètres, nous avons alors deux possibilités :

  • une fonction qui prend deux paramètres équivaut à une fonction qui prend en paramètre un élément, sachant que cet élément est un couple de valeurs ce qui nous obligerais à créer un type Pair<T1, T2> ou Tuple2<T1, T2>,
  • une fonction qui prend deux paramètres équivaut à une fonction qui prend un premier paramètre et retourne une fonction qui prend le paramètre suivant et retourne le résultat final.

Cette seconde solution s’appelle la curryfication. Elle correspond à transformer une fonction de n paramètres en un chaînage de n fonctions prenant chacune un des paramètres et se renvoyant les unes des autres. Ce qui est très utile par exemple pour évaluer partiellement une fonction.

C’est la solution choisie ici. Ce qui explique la signature un peu particulière : Function<Integer, Function<Integer, Integer>>. Autrement dit, notre fonction factorielle est une fonction qui prend un entier et retourne une fonction qui prend un autre entier et retourne un nouvel entier en résultat. Pour rappel, l’interface Function prend deux types en paramètre : le premier correspond au type du paramètre en entrée et le second au type retourné par la fonction.

Concernant maintenant le fait que la fonction soit récursive en plus du fait que j’ai choisi d’utiliser la curryfication, cela nous oblige à nommer explicitement notre fonction, ou plus exactement à définir une classe nommée. Ceci permet d’utiliser la notation : FactorialFunction.this.apply(...). Grâce à cette notation, on demande à Java de ne pas faire un appel à la méthode apply() dans laquelle se trouve directement notre instruction, mais plutôt à la méthode apply() de la classe FactorialFunction.

Hands On 2 : Filter

On fournit une liste de salaires. Ecrire la méthode HandsOn.lessThan() qui ne conserve que les salaires inférieurs strictement à 3000 en utilisant Iterables.filter().

// test unitaire
Iterable<Double> salaries = Arrays.asList(1000.0, 2000.0, 2500.0, 3000.0, 4000.0);
Iterable<Double> newSalaries = HandsOn.lessThan(3000.0, salaries);
assertThat(newSalaries).containsOnly(1000.0, 2000.0, 2500.0);

Cet exercice se résout simplement. À noter, qu’au vu de la verbosité de Java (et en attendant Java 8), il vaut mieux utiliser une variable intermédiaire avec un nom significatif pour la fonction que de créer la fonction dans l’appel à la méthode filter(). Ainsi, la lisibilité du code s’en trouve améliorée.

private Predicate<Double> isLessThan(final double threshold) {
    return new Predicate<Double>() {
        @Override
        public boolean apply(Double salary) {
            return salary < threshold;
        }
    };
}

public static Iterable<Double> lessThan(double threshold, Iterable<Double> salaries) {
    return Iterables.filter(salaries, isLessThan(threshold));
}

Hands On 3 : Map / Transform

On fournit une liste de salaires. Ecrire la méthode HandsOn.increaseSalaries() qui applique une augmentation identique à une liste de salaires en utilisant Iterables.transform() (équivalent de map en Guava).

// test unitaire
Iterable<Double> salaries = Arrays.asList(1000.0, 2000.0, 2500.0, 3000.0, 4000.0);
Iterable<Double> newSalaries = HandsOn.increaseSalaries(salaries, 0.02);
assertThat(newSalaries).containsOnly(1020.0, 2040.0, 2550.0, 3060.0, 4080.0);

De même, cet exercice se résout simplement.

private Function<Double, Double> increaseSalary(final double rate) {
    return new Function<Double, Double>() {
        @Override
        public Double apply(Double salary) {
            return salary * (1.0 + rate);
        }
    };
}

public static Iterable<Double> increaseSalaries(Iterable<Double> salaries, double rate) {
    return Iterables.transform(salaries, increaseSalary(rate));
}

Hands On 4 : Fold / Reduce

La fonction fold(list, init, function) n’existe pas en Guava. Ecrire la fonction fold() et utiliser cette fonction pour calculer une somme de nombres.

// signature
// <T, R> R fold(Iterable<T> values, R init, Function<R, Function<T, R>> function)

// test unitaire
List<Integer> values = Arrays.asList(1, 2, 3);
Integer result = HandsOn.fold(values, 0, sum);
assertThat(result).isEqualTo(6);

La fonction fold est en réalité assez simple.

public static <T, R> R fold(Iterable<T> values, R init, Function<R, Function<T, R>> function) {
    return fold(values.iterator(), init, function);
}

public static <T, R> R fold(Iterator<T> values, R init, Function<R, Function<T, R>> function) {
    R result = init;
    while (iterator.hasNext()) {
        result = function.apply(result).apply(iterator.next());
    }
    return result;
}

On aurait pu résoudre l’exercice avec une structure for-each sur l’Iterable values passé en paramètre. J’ai fait le choix d’avoir une fonction disponible à la fois pour les Iterable et les Iterator.

Pour le test unitaire, nous avons besoin de la fonction sum. Voici comment la définir :

Function<Integer, Function<Integer, Integer>> sum = new Function<Integer, Function<Integer, Integer>>() {
    @Override
    public Function<Integer, Integer> apply(final Integer a) {
        return new Function<Integer, Integer>() {
            @Override
            public Integer apply(Integer b) {
                return a + b;
            }
        };
    }
};

Hands On 5 : Zip

Écrire la fonction HandsOn.zipWith(function, list1, list2) qui fusionne deux listes en se basant sur une fonction.

// signature
// <T1, T2, R> Iterable<R> zipWith(Function<T1, Function<T2, R>> function, Iterable<T1> list1, Iterable<T2> list2)

// test unitaire
Iterable<Integer> result = zipWith(sum, Arrays.asList(1, 2), Arrays.asList(3, 4, 6));
assertThat(result).containsExactly(4, 6);

Voici l’implémentation de la fonction zipWith à la fois pour les Iterable et les Iterator.

public static <T1, T2, R> Iterable<R> zipWith(Function<T1, Function<T2, R>> function, Iterable<T1> list1, Iterable<T2> list2) {
    return new Iterable<R>() {
        @Override
        public Iterator<R> iterator() {
            return zipWith(function, list1.iterator(), list2.iterator());
        }
    };
}

public static <T1, T2, R> Iterator<R> zipWith(Function<T1, Function<T2, R>> function, Iterator<T1> iterator1, Iterator<T2> iterator2) {
    return new AbstractIterator<R>() {
        @Override
        protected R computeNext() {
            if (!(iterator1.hasNext() && iterator2.hasNext())) {
                return endOfData();
            }
            return function.apply(iterator1.next()).apply(iterator2.next());
        }
    }
}

On voit ici l’utilisation de la classe AbstractIterator qui simplifie l’écriture d’instances d’Iterator. On voit aussi comment utiliser la méthode endOfData() pour marquer la fin du flux. La fonction sum qui apparaît dans le test unitaire est exactement la même que la fonction sum de l’exercice précédent.

Hands On 6 : Liste d’entiers infinis avec Guava

Écrire la méthode HandsOn.enumPositiveInts() qui retourne un Iterable<Integer> contenant tous les entiers à partir de 0 jusqu’à l’infini. Vous écrirez cette méthode est utilisant la classe AbstractIterator mise à disposition par Guava.

// test unitaire
Iterable<Integer> fiveInts = Iterables.limit(HandsOn.enumPositiveInts(), 5);
assertThat(fiveInts).containsExactly(0, 1, 2, 3, 4);

Iterable<Integer> fiveNextInts = Iterables.limit(Iterables.skip(HandsOn.enumPositiveInts(), 5), 5);
assertThat(fiveInts).containsExactly(5, 6, 7, 8, 9);

On peut caractériser la notion de suite infinie avec un Iterator.

public static Iterable<Integer> enumPositiveInts() {
    return new Iterable<Integer>() {
        @Override
        public Iterator<Integer> iterator() {
            return new AbstractIterator<Integer>() {
                private int nextValue = 0;

                @Override
                protected Integer computeNext() {
                    int current = nextValue;
                    nextValue++;
                    return current;
                }
            };
        }
    };
}

On peut voir que « l’infini » est représenté par le fait que nous ne faisons pas appel à la méthode endOfData().

Hands On 7 : Fibonnacci sous forme de liste infinie

Écrire la fonction HandsOn.fibs() qui retourne une liste infinie contenant la suite de Fibonnacci.

// test unitaire
assertThat(Iterable.limit(HandsOn.fibs(), 8)).containsExactly(0, 1, 1, 2, 3, 5, 8, 13);

Cette exercice ressemble au précédent, sauf qu’il faut pouvoir conserver les deux étapes précédentes.

public static Iterable<Integer> fibs() {
    return new Iterable<Integer>() {
        @Override
        public Iterator<Integer> iterator() {
            return fibIterator();
        }
    }
}

public static Iterator<Integer> fibIterator() {
    return new AbstractIterator<Integer>() {
        private int a = 0;
        private int b = 1;

        @Override
        protected Integer computeNext() {
            int result = a;
            a = a + b;
            b = result;
            return result;
        }
    }
}

Il faut savoir que cette façon d’écrire la suite Fibonnacci est très efficace par rapport à la version connue utilisant une double récursivité (fib(n) = fib(n-1) + fib(n-2)). La version ci-dessus est complètement linéaire et la récupération de l’élément suivant ne nécessite pas d’explorer une arborescence.

Publié par

Publié par François Sarradin

Consultant Java et λ développeur. Blog personnel : http://kerflyn.wordpress.com/ Twitter : @fsarradin

Commentaire

4 réponses pour " Programmation fonctionnelle – Solution des exercices du XKE de novembre "

  1. Publié par , Il y a 7 années

    Merci pour tous ces exemples très bien documentés !

    Je me rends compte que je ne sais plus vraiment codé en Java, et que j’en suis fort aise :) Presque tous ces exemples sont donnés en Scala, et il y aurait moins de répétition de types… Bref.

    En tout cas, merci de l’initiative de présenter ces concepts, et vivement Java 8 :)

    Joyeuses fêtes !

  2. Publié par , Il y a 7 années

    C’est bizarre quand même.
    Plus je regarde les exemples de factorielles (par exemple), moins je vois l’intérêt de faire quoique ce soit d’autre que la toute première implémentation récursive java.

    compact et compréhensible.

  3. Publié par , Il y a 7 années

    @skai: plutôt d’accord. Après, le but de l’exercice est surtout d’explorer des possibilités et surtout de voir comment reproduire deux types de fonctions récursives d’un côté avec Java, de l’autre avec les fonctions de Guava.

    La première version en Java est compacte et compréhensible car elle correspond très précisément à la définition mathématique qu’on a l’habitude de voir ou à l’idée qu’on se fait de la fonction factorielle (à noter qu’Haskell fait mieux: fact n = product [1..n]). Après, le monde mathématique peut se permettre de faire fi des problèmes d’optimisation inhérents au remplissage de la pile d’appel ; comportement problématique lorsqu’on utilise des fonctions récursives. La seconde version en Java est une transformation de la première version qui permet de résoudre ces problèmes. Mais elle n’a d’intérêt que si Java avait la possibilité d’optimiser les fonctions récursives terminales, en remplaçant l’appel récursif par une boucle. Je suis d’accord que l’ajout d’un second paramètre à la méthode n’est pas vraiment intuitif.

    Du côté Guava, l’intérêt d’avoir des objets de type Function (je ne parle pas du cas particulier de la factorielle) est de pouvoir stocker des fonctions dans des variables, de les passer en paramètre d’autres fonctions/méthodes et/ou de retourner des fonctions depuis d’autres fonctions/méthodes. Cette capacité fait qu’avec Java, on peut faire de la programmation fonctionnelle. On peut donc utiliser des outils liés à ce paradigme qui, s’ils sont correctement maîtrisés, permettent de simplifier drastiquement le code des applications tout en améliorant sa compréhension. Je trouve sympa de pouvoir écrire : transform(salaries, increaseBy(0.05)). Et je ne peux le faire que dans le cadre de la programmation fonctionnelle. Mais le prix à payer en Java, c’est plus de verbosité et le fait de batailler avec les generics qui interfèrent avec le contenu des fonctions aussi simples soient-elles. On le voit bien avec la fonction factorielle.

  4. Publié par , Il y a 6 années

    Pour la reponse 4, n’est-il pas etrange d’utiliser un while? Je pensais qu’en fonctionnel la recursivite etait la regle.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Nous recrutons

Être un Xebian, c'est faire partie d'un groupe de passionnés ; C'est l'opportunité de travailler et de partager avec des pairs parmi les plus talentueux.