«Se souvenir» des valeurs dans la programmation fonctionnelle

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?

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.

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.

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.

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.