«Se souvenir» des valeurs dans la programmation fonctionnelle

20

J'ai décidé de prendre sur moi la tâche d'apprendre la programmation fonctionnelle. Jusqu'à présent, ça a été une explosion, et j'ai «vu la lumière» pour ainsi dire. Malheureusement, je ne connais aucun programmeur fonctionnel sur lequel je pourrais rebondir. Présentation de Stack Exchange.

Je prends un cours de développement web / logiciel, mais mon instructeur n'est pas familier avec la programmation fonctionnelle. Il ne me dérange pas de l'utiliser, et il m'a juste demandé de l'aider à comprendre comment cela fonctionne afin qu'il puisse mieux lire mon code.

J'ai décidé que la meilleure façon de le faire serait d'illustrer une fonction mathématique simple, comme élever une valeur à une puissance. En théorie, je pourrais facilement le faire avec une fonction prédéfinie, mais cela irait à l'encontre du but d'un exemple.

Quoi qu'il en soit, j'ai du mal à trouver comment conserver une valeur. Comme il s'agit d'une programmation fonctionnelle, je ne peux pas changer de variable. Si je devais coder cela impérativement, cela ressemblerait à quelque chose comme ceci:

(Ce qui suit est tout pseudocode)

f(x,y) {
  int z = x;
  for(int i = 0, i < y; i++){
    x = x * z;
  }
  return x;
}

En programmation fonctionnelle, je n'étais pas sûr. Voici ce que j'ai trouvé:

f(x,y,z){
  if z == 'null',
    f(x,y,x);
  else if y > 1,
    f(x*z,y-1,z);
  else
    return x;
}

Est-ce correct? J'ai besoin de conserver une valeur, zdans les deux cas, mais je ne savais pas comment faire cela dans la programmation des fonctions. En théorie, la façon dont je l'ai fait fonctionne, mais je ne savais pas si c'était «bien». Y a-t-il une meilleure façon de le faire?

Ucenna
la source
32
Si vous voulez que votre exemple soit pris au sérieux, faites-le résoudre un problème pratique plutôt qu'un problème mathématique. C'est une sorte de cliché parmi les développeurs que "tout FP est bon pour résoudre les problèmes mathématiques", et si votre exemple est encore une autre fonction mathématique, vous ne faites que renforcer le stéréotype, au lieu de rendre utile ce que vous faites.
Mason Wheeler
12
Votre tentative est en fait assez bonne si vous tenez compte de considérations réelles. Tous vos appels récursifs sont des appels de queue , c'est-à-dire que la fonction ne fait rien d'autre après les avoir appelés. Cela signifie qu'un compilateur ou un interpréteur qui le prend en charge peut les optimiser afin que votre fonction récursive utilise une quantité fixe de mémoire de pile, plutôt qu'une quantité proportionnelle à y.
8bittree
1
Merci beaucoup pour le soutien! Je suis encore très nouveau dans ce domaine, donc mon pseudocode n'est pas parfait. @MasonWheeler Je suppose que dans ce cas, mon code n'est pas vraiment destiné à être pris au sérieux. J'apprends encore, et la raison pour laquelle j'aime FP est parce que c'est Math-y. L'intérêt de mon exemple est d'expliquer à mon professeur pourquoi j'utilise la PF. Il ne comprend pas vraiment ce que c'est, donc cela semblait être un bon moyen de lui montrer les avantages.
Ucenna
5
Dans quelle langue prévoyez-vous d'écrire le code? N'essayez pas d'utiliser un style qui ne convient pas à la langue que vous utilisez.
Carsten S
2
Peut-être utile: en.wikipedia.org/wiki/Memoization
Ethan Bolker

Réponses:

37

Tout d'abord, félicitations pour "voir la lumière". Vous avez fait du monde du logiciel un meilleur endroit en élargissant vos horizons.

Deuxièmement, il n'y a honnêtement aucun moyen qu'un professeur qui ne comprend pas la programmation fonctionnelle puisse dire quoi que ce soit d'utile à propos de votre code, à part des commentaires banals tels que "l'indentation semble". Ce n'est pas si surprenant dans un cours de développement Web, car la plupart du développement Web se fait en HTML / CSS / JavaScript. Selon la façon dont vous vous souciez réellement de l'apprentissage du développement Web, vous voudrez peut-être faire l'effort d'apprendre les outils que votre professeur enseigne (même si cela peut être douloureux - je sais par expérience).

Pour répondre à la question posée: si votre code impératif utilise une boucle, il est probable que votre code fonctionnel sera récursif.

(* raises x to the power of y *)
fun pow (x: real) (y: int) : real = 
    if y = 1 then x else x * (pow x (y-1))

Notez que cet algorithme est en fait plus ou moins identique au code impératif. En fait, on pourrait considérer la boucle ci-dessus comme un sucre syntaxique pour les processus récursifs itératifs.

En remarque, il n'y a pas besoin d'une valeur de zdans votre code impératif ou fonctionnel, en fait. Vous devriez avoir écrit votre fonction impérative comme ceci:

def pow(x, y):
    var ret = 1
    for (i = 0; i < y; i++)
         ret = ret * x
    return ret

plutôt que de changer la signification de la variable x.

gardenhead
la source
Votre récursif pown'est pas tout à fait correct. En l'état, pow 3 3renvoie 81, au lieu de 27. Cela devrait êtreelse x * pow x (y-1).
8bittree le
3
Oups, écrire du code correct est difficile :) Corrigé, et j'ai également ajouté des annotations de type. @Ucenna C'est censé être SML, mais je ne l'ai pas utilisé depuis un moment, donc je pourrais avoir une syntaxe légèrement erronée. Il y a trop de façons de déclarer une fonction, je ne me souviens jamais du bon mot-clé. Outre les changements de syntaxe, le code est identique en JavaScript.
gardenhead
2
@jwg Javascript a certains aspects fonctionnels: les fonctions peuvent définir des fonctions imbriquées, renvoyer des fonctions et accepter des fonctions comme paramètres; il prend en charge les fermetures à portée lexicale (mais pas de portée dynamique lisp) C'est à la discipline du programmeur de s'abstenir de changer d'état et de muter les données.
Kasper van den Berg,
1
@jwg Il n'y a pas de définition convenue du langage "fonctionnel" (ni pour "impératif", "orienté objet" ou "déclaratif"). J'essaie de ne pas utiliser ces termes autant que possible. Il y a trop de langues sous le soleil pour être classées en quatre groupes soignés.
gardenhead
1
La popularité est une métrique terrible, c'est pourquoi chaque fois que quelqu'un mentionne que le langage ou l'outil X doit être meilleur parce qu'il est si largement utilisé, je sais que continuer l'argument serait inutile. Je connais mieux la famille de langues ML que Haskell personnellement. Mais je ne sais pas non plus si c'est vrai; je suppose que la grande majorité des développeurs n'ont pas essayé Haskell en premier lieu.
gardenhead
33

Ce n'est vraiment qu'un addendum à la réponse de gardenhead, mais je voudrais souligner qu'il y a un nom pour le motif que vous voyez: le pliage.

En programmation fonctionnelle, un repli est un moyen de combiner une série de valeurs qui "se souvient" d'une valeur entre chaque opération. Pensez à ajouter impérativement une liste de nombres:

def sum_all(xs):
  total = 0
  for x in xs:
    total = total + x
  return total

Nous prenons une liste de valeurs xset un état initial de 0(représenté par totaldans ce cas). Ensuite, pour chaque xdans xs, nous associons cette valeur à l' état actuel selon une opération combinant (dans ce cas de plus), et d' utiliser le résultat comme nouvel état. En substance, sum_all([1, 2, 3])est équivalent à (3 + (2 + (1 + 0))). Ce modèle peut être extrait dans une fonction d'ordre supérieur , une fonction qui accepte les fonctions comme arguments:

def fold(items, initial_state, combiner_func):
  state = initial_state
  for item in items:
    state = combiner_func(item, state)
  return state

def sum_all(xs):
  return fold(xs, 0, lambda x y: x + y)

Cette implémentation de foldest toujours impérative, mais elle peut aussi se faire récursivement:

def fold_recursive(items, initial_state, combiner_func):
  if not is_empty(items):
    state = combiner_func(initial_state, first_item(items))
    return fold_recursive(rest_items(items), state, combiner_func)
  else:
    return initial_state

Exprimée en termes de pli, votre fonction est simplement:

def exponent(base, power):
  return fold(repeat(base, power), 1, lambda x y: x * y))

... où repeat(x, n)renvoie une liste de ncopies de x.

De nombreux langages, en particulier ceux orientés vers la programmation fonctionnelle, proposent le pliage dans leur bibliothèque standard. Même Javascript le fournit sous le nom reduce. En général, si vous vous retrouvez à utiliser la récursivité pour "mémoriser" une valeur à travers une boucle quelconque, vous voudrez probablement un pli.

Jack
la source
8
Apprenez certainement à repérer quand un problème peut être résolu par un pli ou une carte. En FP, presque toutes les boucles peuvent être exprimées sous forme de pli ou de carte; une récursivité explicite n'est donc généralement pas nécessaire.
Carcigenicate
1
Dans certaines langues, vous pouvez simplement écrirefold(repeat(base, power), 1, *)
user253751
4
Rico Kahler: scanest essentiellement un foldoù au lieu de simplement combiner la liste de valeurs en une seule valeur, il est combiné et chaque valeur intermédiaire est recrachée en cours de route, produisant une liste de tous les états intermédiaires créés par le pli au lieu de simplement produire le état final. Il est implémentable en termes de fold(chaque opération de boucle est).
Jack
4
@RicoKahler Et, pour autant que je sache, les réductions et les plis sont la même chose. Haskell utilise le terme "plier", tandis que Clojure préfère "réduire". Leur comportement me semble le même.
Carcigenicate
2
@Ucenna: C'est à la fois une variable et une fonction. Dans la programmation fonctionnelle, les fonctions sont des valeurs tout comme les nombres et les chaînes - vous pouvez les stocker dans des variables, les passer comme arguments à d'autres fonctions, les renvoyer des fonctions et généralement les traiter comme d'autres valeurs. Il en combiner_funcva de même pour un argument, et sum_alltransmet une fonction anonyme (c'est le lambdabit - il crée une valeur de fonction sans la nommer) qui définit comment il veut combiner deux éléments ensemble.
Jack
8

Il s'agit d'une réponse supplémentaire pour expliquer les cartes et les plis. Pour les exemples ci-dessous, je vais utiliser cette liste. N'oubliez pas que cette liste est immuable, elle ne changera donc jamais:

var numbers = [1, 2, 3, 4, 5]

Je vais utiliser des nombres dans mes exemples, car ils conduisent à un code facile à lire. N'oubliez pas cependant que les plis peuvent être utilisés pour tout ce à quoi une boucle impérative traditionnelle peut être utilisée.

Une carte prend une liste de quelque chose et une fonction et renvoie une liste qui a été modifiée à l'aide de la fonction. Chaque élément est passé à la fonction et devient tout ce que la fonction retourne.

L'exemple le plus simple consiste simplement à ajouter un numéro à chaque numéro d'une liste. Je vais utiliser le pseudocode pour le rendre indépendant du langage:

function add-two(n):
    return n + 2

var numbers2 =
    map(add-two, numbers) 

Si vous imprimiez numbers2, vous verriez [3, 4, 5, 6, 7]quelle est la première liste avec 2 ajoutés à chaque élément. Notez que la fonction a add-twoété donnée mapà utiliser.

Les plis sont similaires, sauf que la fonction que vous devez leur donner doit prendre 2 arguments. Le premier argument est généralement l'accumulateur (dans un pli gauche, qui sont les plus courants). L'accumulateur correspond aux données transmises lors de la boucle. Le deuxième argument est l'élément actuel de la liste; comme ci-dessus pour la mapfonction.

function add-together(n1, n2):
    return n1 + n2

var sum =
    fold(add-together, 0, numbers)

Si vous imprimiez, sumvous verriez la somme de la liste des nombres: 15.

Voici ce que les arguments à foldfaire:

  1. C'est la fonction que nous donnons au pli. Le pli passera la fonction de l'accumulateur actuel et l'élément actuel de la liste. Tout ce que la fonction retourne deviendra le nouvel accumulateur, qui sera transmis à la fonction la prochaine fois. C'est ainsi que vous vous "souvenez" des valeurs lorsque vous bouclez en FP. Je lui ai donné une fonction qui prend 2 nombres et les ajoute.

  2. Ceci est l'accumulateur initial; ce que l'accumulateur démarre comme avant que tous les éléments de la liste soient traités. Lorsque vous additionnez des nombres, quel est le total avant d'avoir ajouté des nombres ensemble? 0, que j'ai passé comme deuxième argument.

  3. Enfin, comme pour la carte, nous passons également la liste des nombres à traiter.

Si les plis n'ont toujours pas de sens, pensez à cela. Lorsque vous écrivez:

# Notice I passed the plus operator directly this time, 
#  instead of wrapping it in another function. 
fold(+, 0, numbers)

Vous placez essentiellement la fonction passée entre chaque élément de la liste et ajoutez l'accumulateur initial à gauche ou à droite (selon qu'il s'agit d'un pli gauche ou droit), donc:

[1, 2, 3, 4, 5]

Devient:

0 + 1 + 2 + 3 + 4 + 5
^ Note the initial accumulator being added onto the left (for a left fold).

Ce qui équivaut à 15.

Utilisez un maplorsque vous souhaitez transformer une liste en une autre liste, de même longueur.

Utilisez un foldlorsque vous souhaitez transformer une liste en une seule valeur, comme la somme d'une liste de nombres.

Comme l'a souligné @Jorg dans les commentaires, la "valeur unique" n'a pas besoin d'être quelque chose de simple comme un nombre; il peut s'agir de n'importe quel objet, y compris une liste ou un tuple! La façon dont j'ai fait cliquer les plis pour moi était de définir une carte en termes de pli. Notez comment l'accumulateur est une liste:

function map(f, list):
    fold(
        function(xs, x): # xs is the list that has been processed so far
            xs.add( f(x) ) # Add returns the list instead of mutating it
        , [] # Before any of the list has been processed, we have an empty list
        , list) 

Honnêtement, une fois que vous les comprendrez, vous réaliserez que presque toutes les boucles peuvent être remplacées par un pli ou une carte.

Carcigenicate
la source
1
@Ucenna @Ucenna Il y a quelques défauts avec votre code (comme ine jamais être défini), mais je pense que vous avez la bonne idée. Un problème avec votre exemple est: la fonction ( x) ne reçoit qu'un seul élément de la liste à la fois, pas la liste entière. La première fois xest appelée, elle passe votre accumulateur initial ( y) comme premier argument et le premier élément comme deuxième argument. La prochaine fois qu'il xsera exécuté, le nouvel accumulateur sera passé à gauche (celui qui sera xretourné la première fois) et le deuxième élément de la liste comme deuxième argument.
Carcigenicate
1
@Ucenna Maintenant que vous avez l'idée de base, regardez à nouveau l'implémentation de Jack.
Carcigenicate
1
@Ucenna: Différentes langues ont des préférences différentes pour savoir si la fonction donnée à fold prend l'accumulateur comme premier ou deuxième argument, malheureusement. L'une des raisons pour lesquelles il est agréable d'utiliser une opération commutative comme l'addition pour enseigner les plis.
Jack
3
"Utilisez un foldlorsque vous souhaitez transformer une liste en une seule valeur (comme la somme d'une liste de nombres)." - Je veux juste noter que cette "valeur unique" peut être arbitrairement complexe… y compris une liste! En fait, foldc'est une méthode générale d'itération, elle peut faire tout ce que l' itération peut faire. Par exemple, mappeut être exprimé trivialement comme func map(f, l) = fold((xs, x) => append(xs, f(x)), [], l)ici, la "valeur unique" calculée par foldest en fait une liste.
Jörg W Mittag
2
... peut-être vouloir faire avec une liste, peut être fait avec fold. Et il n'est pas nécessaire que ce soit une liste, chaque collection qui peut être exprimée comme vide / non vide fera l'affaire. Ce qui signifie essentiellement que tout itérateur fera l'affaire. (je suppose que jeter le mot "catamorphisme" là-dedans serait trop pour une introduction pour débutant, cependant :-D)
Jörg W Mittag
1

Il est difficile de trouver de bons problèmes qui ne peuvent pas être résolus avec une fonctionnalité intégrée. Et s'il est intégré, alors il devrait être utilisé pour être un exemple de bon style en langage x.

Dans haskell par exemple, vous avez déjà la fonction (^)dans Prelude.

Ou si vous voulez le faire par programmation product (replicate y x)

Ce que je dis, c'est qu'il est difficile de montrer les points forts d'un style / langage si vous n'utilisez pas les fonctionnalités qu'il propose. Cependant, cela pourrait être une bonne étape pour montrer comment cela fonctionne dans les coulisses, mais je pense que vous devriez coder la meilleure façon dans la langue que vous utilisez, puis aider la personne à partir de là à comprendre ce qui se passe si nécessaire.

Viktor Mellgren
la source
1
Afin de lier logiquement cette réponse aux autres, il convient de noter qu'il ne products'agit que d'une fonction de raccourci vers foldavec la multiplication comme fonction et 1 comme argument initial, et c'est replicateune fonction qui produit un itérateur (ou une liste; comme je l'ai noté au-dessus des deux sont essentiellement indiscernables en haskell) qui donne un nombre donné de sorties identiques. Il devrait être facile de comprendre maintenant comment cette implémentation fait la même chose que la réponse de @ Jack ci-dessus, en utilisant simplement des versions prédéfinies de cas spéciaux des mêmes fonctions pour la rendre plus succincte.
Periata Breatta