La programmation fonctionnelle (pure) est-elle antagoniste avec les "classiques d'algorithmes"?

Question

L'algorithme classique des livres (TAOCP, CLR) (et pas de manière classique, comme l' fxtbook)sont pleins de impératif des algorithmes. Cela est encore plus évident avec des algorithmes dont la mise en œuvre est fortement basée sur les tableaux, comme la combinatoire génération (où les deux index de tableau et tableau de valeur sont utilisés dans l'algorithme) ou de l'union-find algorithme.

Le pire des cas, l'analyse de la complexité de ces algorithmes dépend de l'accès à des tableaux être O(1). Si vous remplacez des tableaux avec des array-ish persistante des structures, telles que Clojure, l'accès à des tableaux ne sont plus O(1), et l'analyse de la complexité de ces algorithmes n'est plus valide.

Ce qui m'amène aux questions suivantes: est de la pure programmation fonctionnelle incompatible avec les algorithmes classiques de la littérature?

Answer 1

La réponse courte est que, tant que l'algorithme n'a pas d'effets qui peuvent être observées après avoir fini de (autre que de quoi il en retourne), alors il est pur. Cela vaut même lorsque vous faites des choses comme destructrice tableau des mises à jour ou d'une mutation.

Si vous aviez un algorithme comme le disent:

function zero(array):
    ix <- 0
    while(ix < length(array)):
       array[ix] <- 0
       ix <- ix+1
    return array

En supposant que notre pseudo-code ci-dessus est lexicalement étendue, tant que le paramètre de tableau est d'abord copié et le tableau retourné est une tout autre chose, cet algorithme représente une fonction pure (dans ce cas, le Haskell fonction fmap (const 0) serait probablement de travail). La plupart des "impératif" algorithmes vus dans des livres sont vraiment de pures fonctions, et il est parfaitement bien de l'écrire de cette façon dans un but purement fonctionnel en utilisant quelque chose comme SAINT.

Je recommande de regarder le Mercure ou le Disciple Disciplinée Compilateur pour voir pur langues qui prospèrent encore sur la destruction.

Answer 2

À l'égard des structures de données, Chris Okasaki a fait des recherches considérables en adoptant classique des structures de données dans un purement fonctionnel, comme de nombreux de la norme les structures de données de plus de travail lors de l'utilisation destructrice des mises à jour. Son livre "Purement Fonctionnelle des Structures de Données", montre comment certaines structures, comme les tas binomial et rouge/noir des arbres, peuvent être mises en œuvre assez bien dans un paramètre fonctionnel, tandis que d'autres structures de base comme les tableaux et les files d'attente doit être mis en œuvre avec plus d'élaborer des concepts.

Si vous êtes intéressé dans la poursuite de cette branche des algorithmes de base, son livre serait un excellent point de départ.

Answer 3

Vous pouvez être intéressé par cette question connexe: efficacité de la programmation purement fonctionnelle .

y a-t-il un problème pour lequel le meilleur algorithme non destructif connu est asymptotiquement pire que le meilleur algorithme destructif connu, et si oui de combien?

Answer 4

Il n'est pas. Mais il est vrai que l'on peut voir dans beaucoup de livres pour les algorithmes qui regardent comme ils ne sont utilisables que dans des langages impératifs. La raison principale est que pure programmation fonctionnelle a été retenue pour l'usage scolaire pendant une longue période. Ensuite, les auteurs de ces algorithmes dépendait fortement impératif de fonctionnalités pour être dans la norme. Maintenant, considérons deux répandue algorithmes: rapide tri et la fusion de tri. Tri rapide est plus "impératif" de fusion et de tri; l'un de ses avantages est d'être en place. Fusion de tri est plus "pur" que le tri rapide (en quelque sorte) car il a besoin de copier et conserver ses données persistantes. En fait beaucoup de l'algorithme peut être implémenté dans la pure programmation fonctionnelle, sans perdre trop d'efficacité. Cela est vrai pour de nombreux algorithmes dans le célèbre Dragon Book par exemple.