Listes chez Kotlin. Approche Haskell

Haskell est un langage entièrement fonctionnel et extrêmement concis. Quiconque a déjà essayé d'écrire du code dans Haskell remarque à quel point il est concis et élégant que d'écrire la même chose dans un langage impératif. À mon avis, réaliser la même chose en Java est impossible, mais Kotlin vous permet d'aller dans cette direction et d'essayer un style entièrement fonctionnel. Nous pouvons dériver toutes les fonctions complexes dont nous pouvons avoir besoin à partir de la base de départ des 3 fonctions les plus célèbres: cartographier, filtrer, réduire. De plus, j'ai créé un référentiel que vous pouvez étudier et voir les tests.

Avant de commencer, je voudrais attirer l'attention sur le fait qu'il ne vaut pas la peine de mettre en œuvre une approche fonctionnelle de cette manière, car le code sera extrêmement lent et ne devrait pas être utilisé dans des applications de production. Il existe certainement des options pour l'améliorer, mais le but de l'article n'est pas de divulguer ces options, mais d'envisager une approche alternative à l'écriture de code. Dans tous les cas, la compréhension de cette approche vous aidera à travailler avec des structures de données récursives, et vous pourrez apprécier la beauté et l'élégance de la façon dont le code est lu et combien il est plus facile à comprendre.

Fonctions de base

Les listes jouent un rôle très important dans le langage et de nombreuses fonctions utiles leur sont implémentées. Examinons certains d'entre eux et comment ils peuvent être mis en œuvre sur Kotlin.

head (x:_) = x head [] = badHead 

S'il y a des éléments dans la liste, nous retournerons le premier, sinon nous retournerons une erreur.
Nous n'avons pas la possibilité d'écrire un tel code, mais, en général, si vous regardez de près, il est très similaire à celui du modèle. Nous utiliserons également la fonction d'extension pour pouvoir plus tard utiliser cette méthode sur des listes et avoir un moyen un peu plus concis d'obtenir la valeur, sans les crochets à la fin, comme un appel de méthode.

 val <T> List<T>.head: T get() = when (this.isEmpty()) { true -> throw NoSuchElementException("List is empty.") false -> this[0] } 

Afin d'utiliser commodément la récursivité, nous aimerions également diviser la liste en premier élément + tous les autres. Essayons d'implémenter la fonction tail pour cela.

Voici à quoi cela ressemble sur haskell:

 tail (_:xs) = xs tail [] = errorEmptyList "tail" 

Malheureusement, Kotlin ne fournit pas un tel niveau de correspondance de modèles que les développeurs peuvent décrire dans le même style, nous devons donc écrire un peu quand.

 val <T> List<T>.tail: List<T> get() = drop(1) 

Il est un peu malhonnête d'utiliser une fonction de la bibliothèque de langues, mais d'un autre côté, dans tous les cas, il faudrait écrire du code pour cette méthode, il serait donc préférable d'utiliser des méthodes déjà opérationnelles.

Maintenant, nous pouvons diviser la liste en premier élément + le reste de la liste. Nous aurons également besoin de la fonction de concaténation de la liste et d'un élément, qui sera activement utilisé plus tard pour la conversion et d'autres opérations sur la liste.

 operator fun <T> List<T>.plus(x: T): List<T> = ArrayList(this).also { it.add(x) } 

Maintenant, nous pouvons ajouter une liste à l'élément à la fin, et notre implémentation de la fonction de carte devient opérationnelle et prête à l'emploi. Malheureusement, encore une fois, il n'y a aucun moyen d'ajouter un objet à la liste de manière plus pratique, nous utilisons donc la méthode add .

Pour le moment, nous avons presque tout ce dont nous avons besoin. La seule chose dont nous avons besoin maintenant est de pouvoir décrire la condition aux limites pour sortir de la récursivité. Pour ce faire, nous utiliserons la méthode standard isEmpty () . Arrêtons-nous et voyons ce que nous avons en ce moment:

• isEmpty () - y a-t-il des éléments dans la liste
• head - le premier élément de la liste
• tail - une liste sans le premier élément
• élément list + - on peut concaténer la liste avec un objet

En fait, c'est tout ce dont nous avons besoin pour obtenir toutes les méthodes dont nous avons besoin.
À mon goût, il serait plus pratique d'utiliser la comparaison de longueur de liste dans les instructions when . Kotlin nous fournit déjà la taille afin d'obtenir cette longueur de liste. Supposons cependant que nous voulons l'implémenter nous-mêmes. Avec nos fonctionnalités, ce sera assez simple:

 val <T> List<T>.size: Int get() = when (this.isEmpty()) { true -> 0 false -> 1 + this.tail.size } 

Application des fonctions de base

Prenons l'exemple le plus courant. Supposons que nous ayons une liste d'entiers, et que nous voulions les résumer, en oubliant l'existence de cycles. Tout ce que nous avons, ce sont les méthodes que nous avons dérivées ci-dessus et la récursivité. Pour ce faire, nous utiliserons la même approche que lors du calcul de la taille de la liste:

 fun sum(xs: List<Int>): Int = when (xs.size) { 0 -> 0 else -> xs.head + sum(xs.tail) } 

L'idée est très simple: s'il n'y a aucun élément dans la liste, alors la somme est 0; sinon, c'est la somme du premier élément et un appel récursif de la somme pour la queue.

Malgré le fait que nous ne nous soucions pas de la vitesse et des optimisations dans ce code, nous ne pouvons nous empêcher de rappeler les capacités du langage à utiliser la récursivité de queue. La récursivité de queue est un cas spécial de récursivité dans lequel un appel récursif est la dernière opération avant de revenir d'une fonction. Ce type de récursivité est remarquable car il est garanti pour vous permettre de reconstruire le code pour l'itération. Comme vous le savez, le principal problème de la récursivité est que pendant l'exécution de la fonction, il est nécessaire de stocker la pile d'appels de sorte que lorsque la condition aux limites est atteinte, vous pouvez revenir en arrière et recalculer le résultat final.

Il peut sembler que la fonction du montant que nous avons décrit est juste comme ça, car le dernier appel est sum (xs.tail) . Mais ce n'est pas vrai. Si vous décrivez le code un peu différemment, cela deviendra évident:

 fun sum(xs: List<Int>): Int = when (xs.size) { 0 -> 0 else -> { val head = xs.head val tailSum = sum(xs.tail) head + tailSum } } 

Maintenant, nous voyons qu'en fait, le dernier appel est la somme du premier élément et de la partie restante de la queue.

La bonne nouvelle est que si vous ajoutez le modificateur tailrec à une fonction, l'EDI vous dira que la fonction ne l'est pas. Cependant, résoudre ce problème est assez simple. Une astuce courante qui corrige une fonction consiste à utiliser une variable auxiliaire pour stocker les résultats. Cela ressemble à ceci:

 tailrec fun sum(xs: List<Int>, acum: Int): Int = when (xs.size) { 0 -> acum else -> sum(xs.tail, xs.head + acum) } 

Pour calculer la somme des éléments, il suffit de passer 0. comme 2ème paramètre pas nécessaire.

 fun sum(xs: List<Int>):Int { tailrec fun sumInner(xs: List<Int>, acum: Int): Int = when (xs.size) { 0 -> acum else -> sumInner(xs.tail, xs.head + acum) } return sumInner(xs, 0) } 

Ayant cette connaissance, vous pouvez voir que la fonction de taille que nous avons implémentée ci-dessus ne remplit pas les conditions nécessaires pour la récursivité de la queue.

Nous sommes maintenant prêts à implémenter la carte, filtrer, réduire à l'aide de Kotlin. Nous verrons plus tard qu'il suffisait de ne réaliser que ces derniers, et les autres, en général, en sont des dérivés. Mais tout d'abord.

Fonctions principales

CARTE

Une implémentation itérative de cette fonction implique un déplacement séquentiel dans la liste, en utilisant la fonction de conversion et en ajoutant tous les éléments reçus à la nouvelle collection. Nous utiliserons des appels récursifs où la condition aux limites est une liste vide. L'implémentation ressemblera alors à ceci:

 fun <T, R> List<T>.map(f: (T) -> R): List<R> = when (this.size) { 0 -> listOf() else -> f(head) + tail.map(f) } 

S'il n'y a aucun élément dans la liste d'origine, alors nous renvoyons une liste vide, sinon, nous appliquons la transformation au premier élément et ajoutons un appel récursif à la fin pour le reste de la liste.

Cependant, nous n'avons toujours pas de fonction pour concaténer un élément et une liste. Mais nous pouvons déjà le réaliser. Pour commencer, nous dérivons un cas plus général de concaténation d'une paire de listes et ensuite nous l'utilisons pour ajouter une autre liste à l'élément.

 operator fun <T> List<T>.plus(xs: List<T>): List<T> = when (xs.size) { 0 -> ArrayList(this) else -> (this + xs.head) + xs.tail } operator fun <T> T.plus(xs: List<T>): List<T> = listOf(this) + xs 

Filtrer

L'implémentation sera très similaire à la carte. La seule différence est que vous devez savoir si vous devez ajouter l'élément actuel au résultat. Pour ce faire, nous appellerons le lambda que nous avons reçu en paramètre. L'implémentation ressemblera à ceci:

 fun <T> List<T>.filter(f: (T) -> Boolean): List<T> = when (this.size) { 0 -> listOf() else -> if (f(head)) head + tail.filter(f) else tail.filter(f) } 

Si l'élément actuel satisfait la condition de filtre, ajoutez-le récursivement à la fin de la liste; sinon, nous continuons à travailler uniquement avec la fin de la liste.

RÉDUIRE

La fonction la plus difficile à comprendre et, en même temps, la plus puissante (dans le monde fonctionnel, elle est connue sous le nom de pli ). Le plus souvent, il est utilisé pour réduire une liste en un seul élément. Vous avez une certaine valeur de départ s0 , et il y a aussi une liste d'éléments a [] et une fonction f , qui renvoie une nouvelle pour la valeur de départ et l'élément suivant de la liste. f (s0, a [0]) = s1 . Et ainsi, nous parcourons séquentiellement toute la liste des éléments, obtenant une sorte de valeur unique à la sortie. Un exemple assez courant est la somme des éléments du tableau. Dans ce cas, la valeur de départ est 0 et la fonction renvoie la somme de deux éléments: f (s, a [i]) = s + a [i] . Considérez comment nous pouvons implémenter récursivement cette fonction.

 fun <T, R> reduce(s: T, xs: List<R>, f: (T, R) -> T): T = when (xs.size) { 0 -> s else -> reduce(f(s, xs.head), xs.tail, f) } 

En principe, la mise en œuvre est exactement la même que celle que nous avons examinée ci-dessus. S'il n'y a aucun élément dans la liste, nous renvoyons la valeur actuelle, sinon, nous calculons le nouveau premier élément et appelons à nouveau la fonction de réduction pour lui et la queue de la liste.

Notez que nous pouvons également créer des modifications à cette fonction. Par exemple, ne transmettez pas la valeur de départ, mais utilisez le premier élément de la liste pour cela. Pour comprendre que réduire ne s'arrête pas là, imaginez que nous utilisons une liste différente comme valeur de départ. Dans ce cas, à chaque itération, nous ne stockerons pas une valeur, mais une liste, grâce à laquelle nos capacités augmenteront considérablement. Par exemple, essayons d'appliquer la fonction de réduction de manière à obtenir la liste d'origine à la sortie:

 fun <T> reduceSame(xs: List<T>) = reduce(listOf<T>(), xs) { ys, s -> ys + s } 

Maintenant, je pense que vous devinez que nous pourrions utiliser réduire, pour une implémentation alternative de la carte, filtre. Puisque nous avons appris à retourner exactement la même liste avec réduire, nous devons apporter très peu de modifications pour pouvoir convertir chaque élément. Pour le filtre, tout est très similaire.

 fun <T, R> List<T>.map2(f: (T) -> R): List<R> = reduce(mutableListOf(), this) { xs, s -> (xs + f(s)).toMutableList() } fun <T> List<T>.filter2(f: (T) -> Boolean): List<T> = reduce(mutableListOf(), this) { ys, s -> if (f(s)) return@reduce (ys + s).toMutableList() else ys } 

De plus, ils oublient souvent que nous pouvons également utiliser réduire non pas depuis le début de la liste, mais depuis la fin. Bien sûr, nous pouvons simplement élargir la liste, puis appliquer réduire, mais ce n'est pas intéressant. Essayons d'écrire et de comprendre comment réduire fonctionne pour réduire la liste dans l'ordre inverse.

 fun <T, R> reduceRight(s: T, xs: List<R>, f: (T, R) -> T): T = when (xs.size) { 0 -> s else -> f(reduceRight(s, xs.tail, f), xs.head) } 

Si la liste n'est pas vide, alors nous appliquons la fonction f au résultat du pliage de la queue de la liste et du début de la liste. Ainsi, le premier élément sera traité en dernier; avant-dernier - 2e et ainsi de suite. Pour cette option, vous pouvez également ajouter des modifications qui utiliseront le dernier élément de la liste comme valeur de départ, etc.

Presque toujours, lorsque vous travaillez avec des listes, vous pouvez utiliser une combinaison de ces 3 fonctions pour obtenir le résultat qui vous intéresse.

Implémentons également la fonction zip , qui nous permettra de combiner 2 listes.
A l'entrée, nous obtenons 2 listes. Et nous voulons retourner une liste de paires dont la longueur est égale au minimum des listes originales.

Comme d'habitude, vous devez penser à quitter la récursivité et écrire une fonction.

 fun <T, R> zip(xs: List<T>, ys: List<R>): List<Pair<T, R>> { return when (xs.isEmpty() || ys.isEmpty()) { true -> listOf() false -> Pair(xs.head, ys.head) + zip(xs.tail, ys.tail) } } 

Vous pouvez ajouter vos propres modifications, ce qui vous permettra, au lieu de renvoyer une paire d'éléments, d'appliquer une certaine fonction à deux éléments. Dans Haskell, cette fonction est appelée zipWith . Et il est implémenté avec la fonctionnalité que nous avons réussi à écrire très simplement:

 fun <T, R, C> zipWith(xs: List<T>, ys: List<R>, f: (T, R) -> C): List<C> = zip(xs, ys).map { f(it.first, it.second) } 

Très souvent, lorsque vous utilisez l'approche fonctionnelle, des problèmes surviennent lorsque vous devez effectuer des manipulations basées non pas sur des objets dans des listes, mais sur la base d'indices. Par exemple, nous devons additionner tous les éléments pairs d'une liste. Vous pouvez essayer d'atteindre cet objectif en réduisant, en conservant Pair <Int, Boolean> comme valeur actuelle et en ajoutant une valeur si flag == true, et en prenant chaque fois la négation de l'indicateur pour l'étape suivante. Cependant, cela n'a pas l'air trop joli, et le lecteur devra trouver ce que vous voulez exprimer avec ce code. Kotlin a des séquences infinies, et elles sont parfaites pour résoudre ce problème. Si nous analysons ce que nous voulons faire, il s'avère que nous voulons filtrer tous les éléments avec des indices impairs et additionner les autres. Et pour pouvoir obtenir des index, il suffit d'appeler zip pour la liste et la séquence [0,1,2 ..]

 fun sumWithEvenIndexes(xs: List<Int>) = zip(xs, generateSequence(0) { it + 1 }.take(xs.size).toList()) .filter { it.second % 2 == 0 } .map { it.first } .sum() 

Dans la bibliothèque standard de Kotlin, vous pouvez trouver la fonction zip pour la paire de séquences.

Maintenant, regardons un puzzle simple qui m'a inspiré pour écrire ce guide, et à quoi ressemble son implémentation dans un langage impératif dans Kotlin et à la fin dans Haskell.

Il est nécessaire de calculer la quantité maximale parmi les paires de nombres adjacents dans un tableau d'entiers. La longueur du tableau est supérieure à 1, et vous n'avez pas à vous soucier du débordement lors de la sommation des éléments.

Approche Java impérative:

 public Integer maxSum(List<Integer> array) { Integer max = array.get(0) + array.get(1); for (int i = 2; i < array.size(); i++) if (array.get(i) + array.get(i-1) > max) max = array.get(i) + array.get(i-1); return max; } 

Une approche fonctionnelle sur Kotlin utilisant des fonctions écrites (je propose d'implémenter la fonction max en tant que formation vous-même):

 fun maxSum(xs: List<Int>) = zipWith(xs, xs.tail, {a, b -> a + b}).max() 

Implémentation de Haskell:

 maxSum xs = maximum $ zipWith (+) xs (tail xs) 

Comme nous pouvons le voir, ce que nous avons implémenté sur Kotlin (soit dit en passant, nous pourrions utiliser réduire pour résoudre ce problème) est très similaire à ce qui peut être écrit en Haskell.

Conclusion

Sans aucun doute, cela ne devrait pas être utilisé dans le développement, car tout a été mis en œuvre de manière non optimale uniquement afin de démontrer une approche fonctionnelle. De plus, presque tout ce qui a été écrit se trouve dans la bibliothèque standard de Kotlin, donc peut-être qu'à l'avenir, au lieu d'en écrire une autre pour la boucle, vous utiliserez le style fonctionnel que Kotlin nous fournit.

Le plus difficile dans le style fonctionnel est probablement que le problème peut être résolu de différentes manières. Le plus évident peut être lourd et difficile à comprendre à l'avenir, et écrire le plus compréhensible peut prendre du temps et réfléchir sérieusement. La seule chose qui peut aider à maîtriser est une pratique et une formation constantes.

PS: Comme mentionné ci-dessus, vous pouvez voir le référentiel avec tous les exemples qui sont dans l'article. Exécutez les tests et voyez comment cela fonctionne!

PPS: vous pouvez également envisager une approche alternative qui implémente des fonctionnalités similaires.

Et assurez-vous de voir plus tard https://arrow-kt.io/ . À mon avis, vous ne devriez pas y regarder tout de suite, car tout semble assez effrayant, mais plus tard, lorsque les foncteurs et les monades ne vous feront pas peur, assurez-vous de l'étudier.