Programmation fonctionnelle pour les algorithmes de base

Question

Quelle est la qualité de la programmation fonctionnelle «pure» pour les implémentations de routine de base, par ex. liste de tri, correspondance de chaînes, etc.?

Il est courant d'implémenter de telles fonctions de base dans l'interpréteur de base de tout langage fonctionnel, ce qui signifie qu'elles seront écrites dans un langage impératif (c/C++). Bien qu'il existe de nombreuses exceptions ..

Au moins, je voudrais demander: Est-il difficile d'imiter un style impératif tout en codant dans un langage fonctionnel «pur»?

Answer 1

Comment bien est 'pur' la programmation fonctionnelle pour routine de base mises en œuvre, par exemple tri de la liste, string matching etc.

Très. Je ferai vos problèmes à Haskell, et je serai un peu bavard à ce sujet. Mon but n'est pas de vous convaincre que le problème peut se faire en 5 caractères (c'est probablement possible en J!), Mais plutôt de vous donner une idée des constructions.

import Data.List -- for `sort` 
stdlistsorter :: (Ord a) => [a] -> [a] 
stdlistsorter list = sort list 

Tri d'une liste à l'aide de la fonction sort de Data.List

import Data.List -- for `delete` 
selectionsort :: (Ord a) => [a] -> [a] 
selectionsort [] = [] 
selectionsort list = minimum list : (selectionsort . delete (minimum list) $ list) 

mise en œuvre de tri de sélection.

quicksort :: (Ord a) => [a] -> [a] 
quicksort [] = [] 
quicksort (x:xs) = 
    let smallerSorted = quicksort [a | a <- xs, a <= x] 
     biggerSorted = quicksort [a | a <- xs, a > x] 
    in smallerSorted ++ [x] ++ biggerSorted 

Implémentation de tri rapide.

import Data.List -- for `isInfixOf` 
stdstringmatch :: (Eq a) => [a] -> [a] -> Bool 
stdstringmatch list1 list2 = list1 `isInfixOf` list2 

correspondant à cordes en utilisant la fonction isInfixOf de Data.list

Il est commun de mettre en œuvre ces fonctions de base au sein de l'interpréteur de base d'une langue fonctionnelle, ce qui signifie qu'ils seront écrits dans un impératif langue (c/C++). Bien que il existe de nombreuses exceptions ..

Dépend. Certaines fonctions sont plus naturellement exprimées impérativement. Cependant, j'espère vous avoir convaincu que certains algorithmes s'expriment naturellement de manière fonctionnelle.

Au moins, je voudrais demander: Comment est difficile à imiter le style impératif tout codage dans « pur » langage fonctionnelle?

Cela dépend de la difficulté de trouver des Monades dans Haskell. Personnellement, je trouve cela assez difficile à saisir.

Answer 2

Cela marche plutôt bien dans le sens inverse de l'émulation fonctionnelle avec un style impératif. Rappelez-vous que l'interne d'un interpréteur ou VMware si proche du métal et des performances critiques que vous devriez même envisager d'aller au niveau des membres et compter les cycles d'horloge pour chaque instruction (comme Smalltalk Dophin est juste le faire et les résultats sont impressionnants). Les processeurs sont impératifs.

Mais il n'y a aucun problème à faire toute la mise en œuvre de l'algorithme de base - celui que vous mentionnez sont PAS bas niveau - ce sont des bases.

Answer 3

Presque tous les langages de programmation fonctionnels ont une construction permettant le codage impératif (comme do dans Haskell). Il existe de nombreux domaines de problèmes qui ne peuvent pas être résolus avec une programmation fonctionnelle "pure". L'un d'entre eux est les protocoles réseau, par exemple besoin une série de commandes dans le bon ordre. Et de telles choses ne se prêtent pas bien à la programmation purement fonctionnelle.

Je dois être d'accord avec Lothar, cependant, ce tri de liste et la correspondance de chaînes ne sont pas vraiment des exemples que vous devez résoudre impérativement. Il existe des algorithmes bien connus pour de telles choses et ils peuvent déjà être implémentés efficacement dans des langages fonctionnels.

Answer 4

Je pense que les «algorithmes» (par exemple, les corps de méthode et les structures de données de base) sont ceux où la programmation fonctionnelle est la meilleure. En supposant que rien ne soit complètement excentré, les programmes de programmation fonctionnels excèdent les algorithmes de création et les structures de données, ce qui donne souvent un code plus court/plus simple/plus propre que ce que vous obtiendriez avec une solution impérative. (Ne pas imiter le style impératif, le style FP est meilleur pour la plupart de ces types de tâches.)

Vous voulez parfois des choses impératives pour faire face à des E/S ou des performances de bas niveau, et vous voulez que la POO pour le partitionnement de haut niveau la conception et l'architecture d'un grand programme, mais "dans le petit" où vous écrivez la plupart de votre code, FP est une victoire.

Voir aussi

How does functional programming affect the structure of your code?

Answer 5

Je ne sais pas sur le tri de la liste, mais vous auriez du mal à bootstrapp une langue sans une sorte de correspondance de chaîne dans le compilateur ou l'exécution. Vous avez donc besoin de cette routine pour créer la langue. Comme il n'y a pas beaucoup de points à écrire deux fois le même code, lorsque vous créez la bibliothèque pour les chaînes correspondantes dans la langue, vous appelez le code écrit précédemment. La mesure dans laquelle cela se produira dans les versions successives dépendra de la façon dont l'hébergement de la langue est, mais à moins que ce soit un objectif de conception solide, il n'y aura aucune raison de le changer.

Answer 6

1) Bon à quelle norme? Quelles propriétés désires-tu?

Tri de la liste? Facile.Faisons Quicksort en Haskell:

sort [] = [] 
sort (x:xs) = sort (filter (< x) xs) ++ [x] ++ sort (filter (>= x) xs) 

Ce code a l'avantage d'être extrêmement facile à comprendre. Si la liste est vide, elle est triée. Sinon, appelez le premier élément x, trouvez les éléments inférieurs à x et triez-les, trouvez les éléments supérieurs à x et triez-les. Puis concaténez les listes triées avec x au milieu. Essayez de rendre cela compréhensible en C++.

Bien sûr, Mergesort est beaucoup plus rapide pour trier les listes chaînées, mais le code est également 6 fois plus long.

2) Il est extrêmement facile d'implémenter un style impératif tout en restant purement fonctionnel. L'essence du style impératif est le séquençage des actions. Les actions sont séquencées dans un cadre pur en utilisant des monades. L'essence de monades est la fonction de liaison:

(Monad m) => (>>=) :: m a -> (a -> m b) -> m b 

Cette fonction existe en C++, et il est appelé ;.

Une séquence d'actions dans Haskell, par exemple, est écrit ainsi:

putStrLn "What's your name?" >>= 
    const (getLine >>= \name -> putStrLn ("Hello, " ++ name)) 

Certains sucre de syntaxe est disponible pour ce look plus impératif (mais notez que c'est la exacte même code):

do { 
    putStrLn "What's your name?"; 
    name <- getLine; 
    putStrLn ("Hello, " ++ name); 
}