Évaluation paresseuse non triviale

Question

Je suis en train de digérer la belle présentation Pourquoi apprendre Haskell ? par Keegan McAllister. Il y utilise le bout de phrase

minimum = head . sort

comme une illustration de l'évaluation paresseuse de Haskell en déclarant que minimum a temps-complexité O(n) en Haskell. Cependant, je pense que l'exemple est un peu académique par nature. Je demande donc un exemple plus pratique où il n'est pas trivialement évident que la plupart des fonctions de l'application intermédiaire les calculs sont jetés.

Answer 1

• Avez-vous déjà écrit une IA ? N'est-il pas ennuyeux de devoir transmettre des informations sur l'élagage (par exemple, la profondeur maximale, le coût minimal d'une branche adjacente ou d'autres informations de ce type) à travers la fonction de traversée de l'arbre ? Cela signifie que vous devez écrire un nouveau parcours d'arbre chaque fois que vous voulez améliorer votre IA. C'est stupide. Avec l'évaluation paresseuse, ce n'est plus un problème : écrivez votre fonction de traversée d'arbre une fois, pour produire un arbre de jeu énorme (peut-être même infini !), et laissez votre consommateur décider de la quantité à consommer.

• Écrire une interface graphique qui montre beaucoup d'informations ? Vous voulez quand même qu'elle fonctionne rapidement ? Dans d'autres langages, vous pourriez avoir à écrire du code qui ne rend que les scènes visibles. En Haskell, vous pouvez écrire du code qui rend la scène entière, puis choisir plus tard les pixels à observer. De même, le rendu d'une scène compliquée ? Pourquoi ne pas calculer une séquence infinie de scènes à différents niveaux de détail, et choisir la plus appropriée au fur et à mesure de l'exécution du programme ?

• Vous écrivez une fonction coûteuse, et vous décidez de la mémoriser pour plus de rapidité. Dans d'autres langages, cela nécessite de construire une structure de données qui suit les entrées de la fonction dont vous connaissez la réponse, et de mettre à jour la structure lorsque vous voyez de nouvelles entrées. N'oubliez pas de la rendre thread safe - si nous avons vraiment besoin de vitesse, nous avons aussi besoin de parallélisme ! En Haskell, vous construisez une structure de données infinie, avec une entrée pour chaque entrée possible, et vous évaluez les parties de la structure de données qui correspondent aux entrées qui vous intéressent. La sécurité des threads est fournie gratuitement avec la pureté.

• En voici un qui est peut-être un peu plus prosaïque que les précédents. Avez-vous déjà trouvé un moment où && y || n'étaient pas les seules choses que vous vouliez court-circuiter ? Moi, si ! Par exemple, j'adore le <|> fonction permettant de combiner Maybe valeurs : il prend le premier de ses arguments qui a effectivement une valeur. Ainsi, Just 3 <|> Nothing = Just 3 ; Nothing <|> Just 7 = Just 7 ; et Nothing <|> Nothing = Nothing . De plus, il est court-circuitant : s'il s'avère que son premier argument est un Just il ne prendra pas la peine d'effectuer les calculs nécessaires pour déterminer quel est son deuxième argument.

  Et <|> n'est pas intégrée au langage ; elle est ajoutée par une bibliothèque. C'est-à-dire que la paresse vous permet d'écrire tout nouveau des formes de court-circuitage. (En effet, en Haskell, même le comportement de court-circuitage de (&&) y (||) ne sont pas de la magie intégrée au compilateur : ils découlent naturellement de la sémantique du langage et de leurs définitions dans les bibliothèques standard).

En général, le thème commun ici est que l'on peut séparer la production de valeurs de la détermination de ces valeurs. intéressant à regarder . Cela rend les choses plus composables, car le choix de ce qui est intéressant à regarder ne doit pas être connu par le producteur.

Answer 2

Voici un exemple bien connu que j'ai posté sur un autre fil hier. Les nombres de Hamming sont des nombres qui n'ont pas de facteurs premiers supérieurs à 5. C'est-à-dire qu'ils ont la forme 2^i*3^j*5^k. Les 20 premiers d'entre eux sont :

[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]

Le 500000ème est :

1962938367679548095642112423564462631020433036610484123229980468750

Le programme qui a imprimé le 500000ème (après un bref moment de calcul) est :

merge xxs@(x:xs) yys@(y:ys) =
  case (x`compare`y) of
    LT -> x:merge xs yys
    EQ -> x:merge xs ys
    GT -> y:merge xxs ys

hamming = 1 : m 2 `merge` m 3 `merge` m 5
  where
    m k = map (k *) hamming

main = print (hamming !! 499999)

Le calcul de ce nombre à une vitesse raisonnable dans un langage non fastidieux nécessite un peu plus de code et de réflexion. Il y a beaucoup de exemples ici

Answer 3

Envisagez de générer et de consommer le premier n éléments d'un infini séquence. Sans évaluation paresseuse, l'encodage naïf s'exécuterait indéfiniment dans l'étape de génération, et ne consommerait jamais rien. Avec l'évaluation paresseuse, on génère seulement autant d'éléments que le code essaie de consommer.