Programmation fonctionnelle - Pourquoi insister beaucoup sur la récursivité?

Question

Je me suis présenté à la Programmation Fonctionnelle [FP] (à l'aide de la Scala). Une chose qui est en train de sortir de mon premier apprentissages, c'est que les FPs s'appuient fortement sur la récursivité. Et aussi, il semble que, dans la pure FPs la seule façon itérative choses est d'écrire des fonctions récursives.

Et en raison de la forte utilisation de la récursivité semble que la prochaine chose que FPs eu à se soucier de ont été StackoverflowExceptions généralement en raison de la longue remontage des appels récursifs. Cela a été abordée par l'introduction de certaines optimisations (queue de récursivité des optimisations dans le maintien de structures de pile et de l' @tailrec d'annotation à partir d'Scala v2.8,

Quelqu'un peut-il svp m'éclairer pourquoi la récursivité est donc important de paradigme de la programmation fonctionnelle? Est-il quelque chose dans les spécifications des langages de programmation fonctionnels qui se "violé" si nous faire des trucs de manière itérative? Si oui, alors je suis curieux de savoir qui.

PS: Notez que je suis débutant à la programmation fonctionnelle, donc n'hésitez pas à m'indiquer les ressources existantes, si elles expliquer et répondre à ma question. Aussi je comprends que la Scala, en particulier, fournit un support pour faire itératif.

Answer 1

L'église de Turing thèse met en évidence l'équivalence entre les différents compilation de modèles.

En utilisant la récursivité nous n'avons pas besoin d'une mutable état lors de la résolution de certains problème, ce qui rend possible de spécifier une sémantique en termes plus simples. Ainsi, des solutions peuvent être plus simples, dans un sens formel.

Je pense que le Prologue montre mieux que les langages fonctionnels de l'efficacité de la récursivité (il n'a pas d'itération), et les limites pratiques nous rencontrer lors de l'utilisation.

Answer 2

Pure programmation fonctionnelle des moyens de programmation sans effets secondaires. Ce qui signifie, si vous écrivez une boucle par exemple, le corps de la boucle ne peut pas produire d'effets secondaires. Donc, si vous voulez que votre boucle à faire quelque chose, il a pour réutiliser le résultat de l'itération précédente et de produire quelque chose pour la prochaine itération. Ainsi, le corps de la boucle est une fonction prenant en paramètre le résultat de l'exécution précédente et s'appelant elle-même pour la prochaine itération avec son propre résultat. Ce n'est pas avoir un énorme avantage sur directement écrire une fonction récursive pour la boucle.

Un programme qui ne fait pas quelque chose de trivial aura pour itérer sur quelque chose à un certain point. Pour la programmation fonctionnelle, cela signifie que le programme a utiliser des fonctions récursives.

Answer 3

La fonctionnalité qui apporte l' exigence que vous faire des choses de manière récursive est immuable variables.

Considérons une fonction simple pour le calcul de la somme d'une liste (en pseudo-code):

fun calculateSum(list):
    sum = 0
    for each element in list: # dubious
        sum = sum + element # impossible!
    return sum

Maintenant, l' element dans chaque itération de la liste est différente, mais nous pouvons réécrire cette utilisation d'un foreach fonction avec un lambda argument pour se débarrasser de ce problème:

fun calculateSum(list):
    sum = 0
    foreach(list, lambda element:
        sum = sum + element # impossible!
    )
    return sum

Encore, la valeur de l' sum variable doit être modifié à chaque exécution de la lambda. Ce qui est illégal dans une langue immuable variables, de sorte que vous avez à réécrire d'une façon qui n'est pas muter état:

fun calculateSum([H|T]):
    return H + calculateSum(T)

fun calculateSum([]):
    return 0

Maintenant, cette mise en œuvre nécessitera de force à partir de la pile d'appel à beaucoup de choses, et un programme où toutes les petites opérations ne ce ne serait pas courir très vite. Par conséquent, nous réécrire à queue récursive, de sorte que le compilateur peut faire appel tail optimisation:

fun calculateSum([H|T], partialSum):
    return calculateSum(T, H + partialSum)

fun calculateSum([], partialSum):
    return partialSum

fun calculateSum(list):
    return calculateSum(list, 0)

Bien sûr, si vous voulez en boucle indéfiniment, vous avez absolument besoin d'une queue appel récursif, ou bien il serait de débordement de pile.

L' @tailrec d'annotation dans la Scala est un outil pour vous aider à analyser les fonctions de la queue récursive. Vous prétendez "Cette fonction est la queue récursive" et puis, le compilateur peut vous dire si vous vous trompez. Ceci est particulièrement important dans Scala par rapport à d'autres langages fonctionnels parce que la machine sur laquelle il tourne sur la JVM, ne prend pas en charge la queue d'appel d'optimisation, donc il n'est pas possible d'obtenir de la queue d'appel d'optimisation de la Scala dans toutes les même circonstances, vous l'obtenir dans d'autres langages fonctionnels.

Answer 4

La récursivité est naturel, quand vous travaillez sur des niveaux plus élevés de l'abstraction. La programmation fonctionnelle n'est pas seulement au sujet de l'encodage de fonctions; il est à propos d'exploitation à des niveaux plus élevés de l'abstraction, où vous naturellement utiliser des fonctions. Utilisation de fonctions, il est naturel de réutiliser les même fonction (appel à nouveau), à partir de quel que soit le contexte où il fait sens.

Le monde est construit par la répétition de semblables ou de même des blocs de construction. Si vous coupez un morceau de tissu en deux, vous avez deux morceaux de tissu. Induction mathématique est au cœur des mathématiques. Nous, les humains, count ( 1,2,3...). De toute façon inductive défini chose (comme, {les nombres au-dessus de 1} sont {2, et les numéros ci-dessus 2}) est naturel à gérer par une fonction récursive, selon le même cas, par laquelle la chose est définie/construit.

La récursivité est partout. Toute boucle itérative est une récursivité dans le déguisement de toute façon, parce que quand vous entrez cette boucle, vous entrez à nouveau la même boucle à nouveau (juste avec peut-être des différentes variables de boucle). Il n'est donc pas comme inventer de nouveaux concepts à l'informatique, c'est plus de découvrir les fondations, et de la rendre explicite.

---

Ainsi, la récursivité est naturel. Nous venons d'écrire quelques lois à propos de notre problème, certaines équations impliquant la fonction nous sommes à la définition qui permettent de préserver certains invariants (sous l'hypothèse que la fonction est cohérente définie), re-précisant le problème en termes simplifiés, et le tour est joué! Nous avons la solution.

Un exemple, une fonction pour calculer la longueur de la liste (une inductif défini récursif de type de données). Supposons qu'il est défini, et renvoie la liste de la longueur, de la non-surprise. Quelles sont les lois qu'il doit obéir? Ce que l'invariant est préservé dans ce simplification d'un problème?

Le plus immédiat est de prendre la liste, en dehors de son élément de tête, et le reste - un.k.un. la liste de la queue (en fonction de la façon dont une liste est définie/construit). La loi est,

length (x:xs) = 1 + length (xs)

D'uh! Mais que dire de la liste vide? Il faut que

length [] = 0

Donc comment peut-on écrire une telle fonction?... Attendez... Nous l'avons écrit déjà! (En Haskell, si vous vous demandez).

Tous nous avons besoin d'une langue pour permettre un tel style de programmation, c'est qu'il a coût total de possession (et peut-être, un peu luxueusement, TRMCO), donc il n'y a pas de pile de blow-up, et nous sommes ensemble.

---

Une autre chose est la pureté, l'immuabilité des variables de code et/ou de structure de données (dossiers champs, etc).

Ce qui fait, en plus de libérer nos esprits d'avoir à suivre ce qui change quand il prend le temps explicitement apparente dans notre code, au lieu de se cacher dans notre "évolution" mutable variables/données. On ne peut "changer" dans le code impératif la valeur d'une variable à partir de maintenant - nous ne pouvons pas changer sa valeur dans le passé, peut-on?

Et on se retrouve donc avec des listes de changement enregistré de l'histoire, avec une manière explicite le changement apparent dans le code: au lieu de x := x + 2 nous écrire let x2 = x1 + 2. Il fait de raisonner sur le code beaucoup plus facile.

---

À l'adresse de l'immuabilité dans le contexte de la queue de la récursivité avec TCO, considérer cette queue récursive ré-écrire la fonction ci-dessus length en vertu de l'accumulateur argument de paradigme:

length xs = length2 0 xs              -- the invariant: 
length2 a []     = a                  --     1st arg plus
length2 a (x:xs) = length2 (a+1) xs   --     length of 2nd arg

Ici, coût total de possession des moyens d'appel cadre de la réutilisation, en plus du saut direct, et donc, l'appel de la chaîne pour length [1,2,3] peut être considéré comme réellement la mutation du cadre de pile d'appel entrées correspondant à la fonction de paramètres:

length [1,2,3]
length2 0 [1,2,3]       -- a=0  (x:xs)=[1,2,3]
length2 1 [2,3]         -- a=1  (x:xs)=[2,3]
length2 2 [3]           -- a=2  (x:xs)=[3]
length2 3 []            -- a=3  (x:xs)=[]
3

Dans une langue pure, sans aucune valeur-la mutation de primitives, la seule façon d'exprimer le changement est de transmettre les valeurs mises à jour en tant qu'arguments à une fonction, à être transformées. Si la poursuite du traitement est le même qu'avant, que nous avons bien sûr d'appeler la même fonction pour que, en passant de la mise à jour des valeurs comme arguments. Et c'est la récursivité.

---

Et la suite rend l'ensemble de l'histoire de calcul de la longueur d'une liste d'arguments explicites (et disponible pour la réutilisation, si nécessaire):

length xs = last results
  where
     results = length3 0 xs
     length3 a []     = [a]
     length3 a (x:xs) = a : length3 (a+1) xs

En Haskell c'est variablement connu comme gardé la récursivité, ou corecursion (au moins je pense que c'est).

Answer 5

Il y a deux propriétés que je considère comme essentiel à la programmation fonctionnelle:

1. Les fonctions de première classe de membres (uniquement, parce que pour le rendre utile la deuxième propriété est nécessaire)

2. Les fonctions sont pures, c'est à dire une fonction appelée avec les mêmes arguments renvoie la même valeur.

Maintenant, si vous programmez dans un impératif de style, vous devez utiliser assignement.

Envisager une boucle for. Il a un index à chaque itération, l'indice a une valeur différente. Ainsi, vous pouvez définir une fonction qui retourne l'index. Si vous appelez cette fonction deux fois, vous pouvez obtenir des résultats différents. Rompant ainsi avec le principe n ° 2.

Si vous cassez principe n ° 2. en passant autour des fonctions (principe n ° 1), devient quelque chose d'extrêmement dangereux, parce que maintenant le résultat de la fonction peut dépendre de la date et de la façon dont souvent une fonction est appelée.