Pourquoi l'évaluation paresseuse est-elle utile?

Un exemple utile d'évaluation paresseuse est l'utilisation de quickSort:

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

Si nous voulons trouver le minimum de la liste, on peut définir

minimum ls = head (quickSort ls)

Qui trie d'abord la liste et prend ensuite le premier élément de la liste. Cependant, en raison d'une évaluation paresseuse, seule la tête est calculée. Par exemple, si nous prenons le minimum de la liste [2, 1, 3,] quickSort va d'abord filtrer tous les éléments qui sont plus petits que deux. Ensuite, il fait quickSort sur cela (renvoyant la liste singleton [1]) ce qui est déjà assez. En raison de l'évaluation paresseuse, le reste n'est jamais trié, économisant beaucoup de temps de calcul.

C'est bien sûr un exemple très simple, mais la paresse fonctionne de la même manière pour les programmes qui sont très grandes.

Il y a cependant un inconvénient à tout cela: il devient plus difficile de prédire la vitesse d'exécution et l'utilisation de la mémoire de votre programme. Cela ne signifie pas que les programmes paresseux sont plus lents ou prennent plus de mémoire, mais c'est bon à savoir.

Je trouve l'évaluation paresseuse utile pour un certain nombre de choses.

Tout d'abord, tous les langages paresseux existants sont purs, car il est très difficile de raisonner sur les effets secondaires dans un langage paresseux.

Les langages purs vous permettent de raisonner sur les définitions de fonctions en utilisant un raisonnement équationnel.

foo x = x + 3

Malheureusement, dans un paramètre non paresseux, plus d'instructions ne parviennent pas à retourner que dans un paramètre paresseux, ce qui est moins utile dans des langages comme ML. Mais dans une langue paresseuse, vous pouvez raisonner en toute sécurité égalité.

Deuxièmement, beaucoup de choses comme la 'restriction de valeur' dans ML ne sont pas nécessaires dans les langages paresseux comme Haskell. Cela conduit à un grand désencombrage de la syntaxe. ML comme les langues doivent utiliser des mots clés comme var ou fun. Dans Haskell, ces choses s'effondrent en une seule notion.

Troisièmement, la paresse vous permet d'écrire un code très fonctionnel qui peut être compris en morceaux. Dans Haskell, il est courant d'écrire un corps de fonction comme:

foo x y = if condition1
          then some (complicated set of combinators) (involving bigscaryexpression)
          else if condition2
          then bigscaryexpression
          else Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

Cela vous permet de travailler de haut en bas comprendre le corps d'une fonction. Les langages de type ML vous obligent à utiliser un let qui est évalué strictement. Par conséquent, vous n'osez pas "soulever" la clause let sur le corps principal de la fonction, car si elle est coûteuse (ou a des effets secondaires), vous ne voulez pas qu'elle soit toujours évaluée. Haskell peut "pousser" explicitement les détails de la clause where car il sait que le contenu de cette clause ne sera évalué que si nécessaire.

En pratique, nous avons tendance à utiliser des gardes et à nous effondrer cela suite à:

foo x y 
  | condition1 = some (complicated set of combinators) (involving bigscaryexpression)
  | condition2 = bigscaryexpression
  | otherwise  = Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

Quatrièmement, la paresse offre parfois une expression beaucoup plus élégante de certains algorithmes. Un "tri rapide" paresseux dans Haskell est un one-liner et a l'avantage que si vous ne regardez que les premiers éléments, vous ne payez que des coûts proportionnels au coût de la sélection de ces éléments. Rien ne vous empêche de le faire strictement, mais vous devrez probablement recoder l'algorithme à chaque fois pour obtenir les mêmes performances asymptotiques.

Cinquièmement, la paresse vous permet de définir de nouvelles structures de contrôle dans le langage. Vous ne pouvez pas écrire un nouveau si .. puis .. autre .."comme construire dans un langage strict. Si vous essayez de définir une fonction comme:

if' True x y = x
if' False x y = y

Dans un langage strict, les deux branches seraient évaluées indépendamment de la valeur de la condition. Cela empire quand on considère les boucles. Toutes les solutions strictes nécessitent la langue pour vous fournir une sorte de citation ou de construction lambda explicite.

Enfin, dans la même veine, certains des meilleurs les mécanismes de traitement des effets secondaires dans le système de type, tels que les monades, ne peuvent vraiment être exprimés efficacement que dans un cadre paresseux. Cela peut être constaté en comparant la complexité des flux de travail de F#aux monades Haskell. (Vous pouvez définir une monade dans un langage strict, mais malheureusement, vous échouerez souvent une loi de monade ou deux en raison du manque de paresse et des flux de travail par comparaison ramasser une tonne de bagages stricts.)

Il y a une différence entre une évaluation d'ordre normal et une évaluation paresseuse (comme dans Haskell).

square x = x * x

Évaluer l'expression suivante...

square (square (square 2))

... avec une évaluation avide:

> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256

... avec l'évaluation de l'ordre normal:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256

... avec évaluation paresseuse:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256

C'est parce que l'évaluation paresseuse regarde l'arbre de syntaxe et fait des transformations d'arbre...

square (square (square 2))

           ||
           \/

           *
          / \
          \ /
    square (square 2)

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
        square 2

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
           *
          / \
          \ /
           2

... alors que l'évaluation de l'ordre normal ne fait que textuel expansion.

C'est pourquoi nous, en utilisant l'évaluation paresseuse, devenons plus puissants (l'évaluation se termine plus souvent que les autres stratégies) alors que la performance est équivalente à l'évaluation avide (au moins en notation O).

Si vous croyez Simon Peyton Jones, l'évaluation paresseuse n'est pas importante en soi {[2] } mais seulement comme une "chemise de cheveux" qui a forcé les concepteurs à garder le langage pur. Je me trouve sympathique à ce point de vue.

Richard Bird, John Hughes et, dans une moindre mesure, Ralf Hinze sont capables de faire des choses étonnantes avec une évaluation paresseuse. Lire leur travail vous aidera à l'apprécier. Les bons points de départ sont le magnifique SudokuBird solver et le papier de Hughes sur Pourquoi La Programmation Fonctionnelle Compte .

Évaluation paresseuse liée à la CPU de la même manière que la récupération de place liée à la RAM. GC vous permet de prétendre que vous avez une quantité illimitée de mémoire et donc demander autant d'objets en mémoire que vous avez besoin. Runtime récupère automatiquement les objets inutilisables. LE vous permet de prétendre que vous avez des ressources de calcul illimitées - vous pouvez faire autant de calculs que vous avez besoin. Runtime n'exécutera tout simplement pas de calculs inutiles (pour un cas donné).

Quelle est la pratique avantage de ces modèles "prétendant"? Il libère le développeur (dans une certaine mesure) de la gestion des ressources et supprime du code standard de vos sources. Mais le plus important est que vous pouvez réutiliser efficacement votre solution dans un ensemble plus large de contextes.

Imaginez que vous avez une liste de nombres S et un nombre N. vous devez trouver le plus proche du nombre n Numéro M de la liste S. Vous pouvez avoir deux contextes: unique n et une liste L de Ns (par exemple pour chaque N dans L vous recherchez le M le plus proche Dans S). Si vous utilisez l'évaluation paresseuse, vous pouvez trier S et appliquer la recherche binaire pour trouver le plus proche M à N. Pour un bon tri paresseux, il faudra o(Taille(S)) étapes pour n unique et O(ln(Taille(S))*(Taille(S) + Taille (L))) étapes pour L. également distribué si vous n'avez pas d'évaluation paresseuse pour atteindre l'efficacité optimale, vous devez implémenter un algorithme pour chaque contexte.

Considérons un programme tic-tac-toe. Cela a quatre fonctions:

• une fonction de génération de mouvement qui prend une carte en cours et génère une liste de nouvelles cartes chacune avec un mouvement appliqué.
• Ensuite, il y a une fonction "move tree" qui applique la fonction de génération de mouvement pour dériver toutes les positions possibles du tableau qui pourraient découler de celui-ci.
• Il y a une fonction minimax qui parcourt l'arbre (ou peut-être seulement une partie de celui-ci) pour trouver le meilleur mouvement suivant.
• voilà est une fonction d'évaluation du Conseil d'administration qui détermine si l'un des joueurs a gagné.

Cela crée une belle séparation claire des préoccupations. En particulier, la fonction move-generation et les fonctions d'évaluation du board sont les seules à comprendre les règles du jeu: les fonctions move tree et minimax sont entièrement réutilisables.

Essayons maintenant d'implémenter chess au lieu de tic-tac-toe. Dans un langage" avide " (c'est-à-dire conventionnel) cela ne fonctionnera pas parce que le mouvement l'arbre ne rentre pas dans la mémoire. Alors maintenant, les fonctions d'évaluation du Conseil et de génération de mouvement doivent être mélangées avec l'arbre de déplacement et la logique minimax car la logique minimax doit être utilisée pour décider quels mouvements générer. Notre belle structure modulaire propre disparaît.

Cependant, dans un langage paresseux, les éléments de l'arbre de déplacement ne sont générés qu'en réponse aux demandes de la fonction minimax: l'arbre de déplacement entier n'a pas besoin d'être généré avant de laisser minimax se détacher sur le dessus élément. Donc, notre structure modulaire propre fonctionne toujours dans un vrai jeu.

Voici deux autres points qui, à mon avis, n'ont pas encore été soulevés dans la discussion.

1. La Paresse est un mécanisme de synchronisation dans un tel environnement. Il est léger et facile de créer une référence à un calcul, et de partager ses résultats entre plusieurs threads. Si plusieurs threads tentent d'accéder à une valeur non évaluée, un seul d'entre eux l'exécutera, et les autres bloqueront en conséquence, recevant la valeur une fois qu'elle deviendra disponible.

2. La paresse est fondamentale pour amortir les structures de données dans un cadre pur. Ceci est décrit par Okasaki dans structures de données purement fonctionnelles en détail, mais l'idée de base est que l'évaluation paresseuse est une forme contrôlée de mutation critique pour nous permettre de mettre en œuvre certains types de structures de données efficacement. Alors que nous parlons souvent de la paresse nous forçant à porter la pureté hairshirt, l'autre sens s'applique aussi: ils sont une paire de langage synergique caractéristique.

Lorsque vous allumez votre ordinateur et que Windows s'abstient d'ouvrir TOUS les répertoires de votre disque dur dans L'Explorateur Windows et de lancer tous les programmes installés sur votre ordinateur, jusqu'à ce que vous indiquiez qu'un certain répertoire est nécessaire ou qu'un certain programme est nécessaire, c'est-à-dire une évaluation" paresseuse".

L'évaluation "paresseuse" effectue des opérations quand et comme elles sont nécessaires. Il est utile lorsqu'il s'agit d'une fonctionnalité d'un langage de programmation ou d'une bibliothèque, car généralement plus difficile à mettre en œuvre l'évaluation paresseuse par vous-même que simplement de tout précalculer à l'avance.

1. Il peut augmenter l'efficacité. C'est l'aspect évident, mais ce n'est pas vraiment le plus important. (Notez également que la paresse peut tuer efficacité aussi-ce fait n'est pas immédiatement évident. Toutefois, en stockant beaucoup de résultats temporaires plutôt que de calculer immédiatement, vous pouvez utiliser une énorme quantité de RAM.)

2. Il vous permet de définir des constructions de contrôle de flux dans du code de niveau utilisateur normal, plutôt que d'être codé en dur dans la langue. (E. g., Java a des boucles for; Haskell a une fonction for. Java a une gestion des exceptions; Haskell a différents types de monade d'exceptions. C # A goto; Haskell a la monade de continuation...)

3. Il vous permet de dissocier l'algorithme de génération de données à partir de l'algorithme pour décider combien données à générer. Vous pouvez écrire une fonction qui génère une liste de résultats théoriquement infinie, et une autre fonction qui traite autant de cette liste qu'elle en décide. Plus de le point, vous pouvez avoir Cinq fonctions de générateur et Cinq fonctions de consommation, et vous pouvez produire efficacement n'importe quelle combinaison - au lieu de coder manuellement 5 x 5 = 25 fonctions qui combinent les deux actions à la fois. (! Nous savons tous découplage est une bonne chose.

4. Cela vous oblige plus ou moins à concevoir un langage fonctionnel pur . Il est toujours tentant de prendre des raccourcis, mais dans un langage paresseux, la moindre impureté rend votre code sauvagement imprévisible, ce qui milite fortement contre la prise de raccourcis.

Considérez ceci:

if (conditionOne && conditionTwo) {
  doSomething();
}

La méthode doSomething() ne sera exécutée que si conditionOne est true et conditionTwo est true. Dans le cas où conditionOne est false, pourquoi avez-vous besoin de calculer le résultat de la conditiondeux? L'évaluation de la conditiondeux sera une perte de temps dans ce cas, surtout si votre état est le résultat d'un processus de méthode.

C'est un exemple de l'intérêt d'évaluation paresseux...

Un énorme avantage de la paresse est la capacité d'écrire des structures de données immuables avec des limites amorties raisonnables. Un exemple simple est une pile immuable (en utilisant F#):

type 'a stack =
    | EmptyStack
    | StackNode of 'a * 'a stack

let rec append x y =
    match x with
    | EmptyStack -> y
    | StackNode(hd, tl) -> StackNode(hd, append tl y)

Le code est raisonnable, mais l'ajout de deux piles x et y prend du temps O (longueur de x) dans les cas meilleurs, pires et moyens. L'ajout de deux piles est une opération monolithique, elle touche tous les nœuds de la pile X.

Nous pouvons réécrire la structure de données en tant que pile paresseuse:

type 'a lazyStack =
    | StackNode of Lazy<'a * 'a lazyStack>
    | EmptyStack

let rec append x y =
    match x with
    | StackNode(item) -> Node(lazy(let hd, tl = item.Force(); hd, append tl y))
    | Empty -> y

lazy œuvres de suspendre l'évaluation du code dans son constructeur. Une fois évaluée à l'aide de .Force(), la valeur de retour est mise en cache et réutilisée sur chaque .Force() suivant.

Avec la version lazy, les appends sont une opération O(1): elle renvoie 1 nœud et suspend la reconstruction réelle de la liste. Lorsque vous obtenez la tête de cette liste, il évaluera le contenu du nœud, le forçant à retourner la tête et à créer une suspension avec les éléments restants, donc prendre la tête de la liste est un O (1) opération.

Donc, notre liste paresseuse est dans un état constant de reconstruction, vous ne payez pas le coût de la reconstruction de cette liste tant que vous n'avez pas traversé tous ses éléments. En utilisant la paresse, cette liste prend en charge O(1) consing et appending. Fait intéressant, puisque nous n'évaluons pas les nœuds jusqu'à leur accès, il est tout à fait possible de construire une liste avec des éléments potentiellement infinis.

La structure de données ci-dessus ne nécessite pas de recalculer les nœuds à chaque traversée, ils sont donc distinctement différent de la vanille IEnumerables dans. NET.

L'évaluation paresseuse est très utile avec les structures de données. Vous pouvez définir un tableau ou un vecteur de manière inductive en spécifiant uniquement certains points de la structure et en exprimant tous les autres en termes de tableau entier. Cela vous permet de générer des structures de données de manière très concise et avec des performances d'exécution élevées.

Pour voir cela en action, vous pouvez jeter un oeil à ma bibliothèque de réseau neuronal appelée instinct. Il fait un usage intensif de l'évaluation paresseuse pour l'élégance et la haute performance. Exemple Je me débarrasse totalement du calcul d'activation traditionnellement impératif. Une simple expression paresseuse fait tout pour moi.

Ceci est utilisé par exemple dans la fonction d'activation et aussi dans l'algorithme d'apprentissage de la rétropropagation (Je ne peux poster que deux liens, vous devrez donc rechercher vous-même la fonction learnPat dans le module AI.Instinct.Train.Delta). Traditionnellement, les deux nécessitent des algorithmes itératifs beaucoup plus compliqués.

Cet extrait montre la différence entre l'évaluation paresseuse et non paresseuse. Bien sûr, cette fonction de fibonacci pourrait elle-même être optimisée et utiliser une évaluation paresseuse au lieu de la récursivité, mais cela gâcherait l'exemple.

Supposons que nous puissions {[6] } Utiliser les 20 premiers nombres pour quelque chose, avec une évaluation Non paresseuse, tous les 20 nombres doivent être générés dès le départ, mais, avec une évaluation paresseuse, ils seront générés au besoin seulement. Ainsi vous ne paierez que le prix de calcul lorsque nécessaire.

Exemple de sortie

Not lazy generation: 0.023373
Lazy generation: 0.000009
Not lazy output: 0.000921
Lazy output: 0.024205

import time

def now(): return time.time()

def fibonacci(n): #Recursion for fibonacci (not-lazy)
 if n < 2:
  return n
 else:
  return fibonacci(n-1)+fibonacci(n-2)

before1 = now()
notlazy = [fibonacci(x) for x in range(20)]
after1 = now()
before2 = now()
lazy = (fibonacci(x) for x in range(20))
after2 = now()


before3 = now()
for i in notlazy:
  print i
after3 = now()

before4 = now()
for i in lazy:
  print i
after4 = now()

print "Not lazy generation: %f" % (after1-before1)
print "Lazy generation: %f" % (after2-before2)
print "Not lazy output: %f" % (after3-before3)
print "Lazy output: %f" % (after4-before4)

D'autres personnes ont déjà donné toutes les grandes raisons, mais je pense qu'un exercice utile pour aider à comprendre pourquoi la paresse compte est d'essayer d'écrire une fonction à point fixe dans un langage strict.

Dans Haskell, une fonction à point fixe est super facile:

fix f = f (fix f)

Cela s'étend à

f (f (f ....

Mais comme Haskell est paresseux, cette chaîne infinie de calcul ne pose aucun problème; l'évaluation se fait "de l'extérieur vers l'intérieur", et tout fonctionne merveilleusement:

fact = fix $ \f n -> if n == 0 then 1 else n * f (n-1)

Ce qui importe, ce n'est pas que fix soit paresseux, mais que f sois paresseux. Une fois que vous avez déjà reçu un f strict, vous pouvez soit jeter vos mains en l'air et abandonner, ou ETA l'étendre et encombrer les choses. (C'est un peu comme ce que Noah disait à propos de la bibliothèque qui est stricte / paresseuse, pas la langue).

Imaginez maintenant écrire la même fonction en Scala strict:

def fix[A](f: A => A): A = f(fix(f))

val fact = fix[Int=>Int] { f => n =>
    if (n == 0) 1
    else n*f(n-1)
}

Vous obtenez bien sûr une pile débordement. Si vous voulez que cela fonctionne, vous avez besoin de faire le f argument en appel par nécessité:

def fix[A](f: (=>A) => A): A = f(fix(f))

def fact1(f: =>Int=>Int) = (n: Int) =>
    if (n == 0) 1
    else n*f(n-1)

val fact = fix(fact1)

Je ne sais pas comment vous pensez actuellement des choses, mais je trouve utile de penser à l'évaluation paresseuse comme un problème de bibliothèque plutôt qu'une fonctionnalité de langue.

Je veux dire que dans les langages stricts, je peux implémenter une évaluation paresseuse en construisant quelques structures de données, et dans les langages paresseux (au moins Haskell), je peux demander la rigueur quand je le veux. Par conséquent, le choix de la langue ne rend pas vraiment vos programmes paresseux ou non paresseux, mais affecte simplement ce que vous obtenez par défaut.

Une fois que vous pensez-y comme ça, puis pensez à tous les endroits où vous écrivez une structure de données que vous pouvez utiliser plus tard pour générer des données (sans trop la regarder avant), et vous verrez beaucoup d'utilisations pour l'évaluation paresseuse.

L'exploitation la plus utile de l'évaluation paresseuse que j'ai utilisée était une fonction qui appelait une série de sous-fonctions dans un ordre particulier. Si l'une de ces sous-fonctions échoue (retournée false), la fonction appelante doit retourner immédiatement. J'aurais donc pu le faire de cette façon:

bool Function(void) {
  if (!SubFunction1())
    return false;
  if (!SubFunction2())
    return false;
  if (!SubFunction3())
    return false;

(etc)

  return true;
}

Ou, la solution la plus élégante:

bool Function(void) {
  if (!SubFunction1() || !SubFunction2() || !SubFunction3() || (etc) )
    return false;
  return true;
}

Une fois que vous commencez à l'utiliser, vous verrez des occasions de l'utiliser de plus en plus souvent.

Sans évaluation paresseuse, vous ne serez pas autorisé à écrire quelque chose comme ceci:

  if( obj != null  &&  obj.Value == correctValue )
  {
    // do smth
  }

Entre autres choses, les langages paresseux permettent des structures de données infinies multidimensionnelles.

Alors que scheme, python, etc permettent des structures de données infinies unidimensionnelles avec des flux, vous ne pouvez traverser que le long d'une dimension.

La paresse est utile pour le même problème de frange , mais il convient de noter la connexion coroutines mentionnée dans ce lien.

L'évaluation paresseuse est le raisonnement équationnel du pauvre homme (qui pourrait idéalement déduire les propriétés du code des propriétés des types et des opérations impliqués).

Exemple où cela fonctionne assez bien: sum . take 10 $ [1..10000000000]. Ce qui ne nous dérange pas d'être réduit à une somme de 10 nombres, au lieu d'un seul calcul numérique direct et simple. Sans l'évaluation paresseuse bien sûr, cela créerait une liste gigantesque en mémoire juste pour utiliser ses 10 premiers éléments. Ce serait certainement très lent, et peut provoquer une erreur de mémoire insuffisante.

Exemple où ce n'est pas aussi génial que nous le souhaiterions: sum . take 1000000 . drop 500 $ cycle [1..20]. Ce qui va en fait additionner les 1 000 000 nombres, même si dans une boucle au lieu d'une liste; encore devrait être réduit à un seul calcul numérique direct, avec peu de conditions et peu de formules. Ce qui serait beaucoup mieux que de résumer les numéros 1 000 000. Même si dans une boucle, et non dans une liste (c'est-à-dire après l'optimisation de la déforestation).

Autre chose est, il permet de coder dans Tail recursion modulo cons style, et il fonctionne juste .

Cf. réponse connexe .

Si par "évaluation paresseuse" vous voulez dire comme dans les booléens combound, comme dans

   if (ConditionA && ConditionB) ... 

Alors la réponse est simplement que moins le programme consomme de cycles CPU, plus il s'exécutera rapidement... et si un morceau d'instructions de traitement n'a aucun impact sur le résultat du programme, il n'est pas nécessaire (et donc une perte de temps) de les exécuter de toute façon...

Si otoh, vous voulez dire ce que j'ai connu comme "initialiseurs paresseux", comme dans:

class Employee
{
    private int supervisorId;
    private Employee supervisor;

    public Employee(int employeeId)
    {
        // code to call database and fetch employee record, and 
        //  populate all private data fields, EXCEPT supervisor
    }
    public Employee Supervisor
    { 
       get 
          { 
              return supervisor?? (supervisor = new Employee(supervisorId)); 
          } 
    }
}

Eh bien, cette technique permet code client utilisant la classe pour éviter d'appeler la base de données pour L'enregistrement de données du superviseur, sauf lorsque le client utilisant L'objet Employee nécessite l'accès aux données du superviseur... cela rend le processus d'instanciation d'un employé plus rapide, et pourtant, lorsque vous avez besoin du superviseur, le premier appel à la propriété Supervisor déclenchera l'appel de base de données et les données seront récupérées et disponibles...

Extrait de des fonctions d'ordre Supérieur

Trouvons le plus grand nombre inférieur à 100 000 divisible par 3829. Pour ce faire, nous allons simplement filtrer un ensemble de possibilités dans lesquelles nous savons la solution réside.

largestDivisible :: (Integral a) => a  
largestDivisible = head (filter p [100000,99999..])  
    where p x = x `mod` 3829 == 0 

Nous faisons d'abord une liste de tous les nombres inférieurs à 100 000, décroissant. Ensuite nous le filtrons par notre prédicat et parce que les nombres sont triés d'une manière descendante, le plus grand nombre qui satisfait notre le prédicat est le premier élément de la liste filtrée. Nous n'avons même pas besoin d'utiliser une liste finie pour notre ensemble de départ. C'est la paresse dans action à nouveau. Parce que nous finissons seulement par utiliser la tête du filtre liste, peu importe si la liste filtrée est finie ou infinie. L'évaluation s'arrête lorsque la première solution adéquate soit trouvée.