Expliquez ce morceau de code haskell qui génère un flux de nombres premiers

StackOverflow https://stackoverflow.com/questions/1764163

  •  21-09-2019
  •  | 
  •  

Question

J'ai du mal à comprendre ce morceau de code: 

let
  sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)
in sieve [2 .. ]

Quelqu'un peut-il décomposer pour moi? Je crois comprendre qu'il ya récursivité dedans, mais c'est le problème que je ne peux pas comprendre comment la récursion dans cet exemple fonctionne.

Était-ce utile?

La solution

Il est en fait assez élégant.

Tout d'abord, nous définissons une sieve de fonction qui prend une liste d'éléments: 

sieve (p:xs) =

Dans le corps de sieve, nous prenons la tête de la liste (parce que nous transmettons la liste infinie [2..] et 2 est définie comme premier) et l'ajouter (paresseusement!) Au résultat de l'application sieve à la reste de la liste: 

p : sieve (filter (\ x -> x 'mod' p /= 0) xs)

Alors, regardons le code qui fait le travail sur le reste de la liste: 

sieve (filter (\ x -> x 'mod' p /= 0) xs)

Nous appliquons sieve à la liste filtrée. Décomposons ce que la partie filtre fait: 

filter (\ x -> x 'mod' p /= 0) xs

filter prend une fonction et une liste sur laquelle nous appliquons cette fonction et conserve les éléments qui répondent aux critères donnés par la fonction. Dans ce cas, filter prend une fonction anonyme: 

\ x -> x 'mod' p /= 0

Cette fonction anonyme prend un argument, x. Il vérifie la x de contre p (la tête de la liste, tous les sieve de temps est appelé) module : 

 x 'mod' p

Si le module n'est pas égal à 0: 

 x 'mod' p /= 0

Alors le x élément est conservé dans la liste. Si elle est égale à 0, il est filtré. Cela est logique. Si x est divisible par p, que x est divisible par plus que 1 et lui-même, et il est donc pas premier

Autres conseils

Contrairement à ce que d'autres ont déclaré ici, cette fonction n'a pas mettre en œuvre les véritables de Eratosthène. Il ne renvoie une séquence initiale des nombres premiers cependant, et de la même manière, il est donc normal de penser comme le tamis d'Eratosthène.

J'étais sur le fait d'expliquer le code lorsque mipadi posté sa réponse; Je pourrais le supprimer, mais depuis que je passé un peu de temps à ce sujet, et parce que nos réponses ne sont pas tout à fait identiques, je vais le laisser ici.

Firs de tous, notez qu'il ya des erreurs de syntaxe dans le code affiché. Le code est correct, 

let sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs) in sieve [2..]

  1. let x in y définit x et permet sa définition à utiliser dans y. Le résultat de cette expression est le résultat de y. Donc, dans ce cas, nous définissons une sieve de fonction et de retourner le résultat de l'application [2..] à sieve.

  2. Maintenant, laissez-nous regarder de plus près la partie let de cette expression: 

    sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs)
    1. Ceci définit une sieve fonction qui prend une liste comme premier argument.
    2. (p:xs) est modèle qui correspond p à la tête de ladite liste et xs avec la queue (tout sauf la tête).
    3. En général, p : xs est une liste dont le premier élément est p. xs est une liste contenant les éléments restants. Ainsi, sieve renvoie le premier élément de la liste qu'il reçoit.

    4. Ne pas regarder le reste de la liste: 

      sieve (filter (\x -> x `mod` p /= 0) xs)
      1. On peut voir que sieve est appelé récursive. Ainsi, l'expression filter renvoie une liste.
      2. filter prend une fonction de filtre et une liste. Elle renvoie uniquement les éléments dans la liste pour laquelle la fonction de filtre retourne true.

      3. Dans ce cas xs est la liste filtrée et 

        (\x -> x `mod` p /= 0)

        est la fonction de filtre.

      4. La fonction de filtre prend un seul argument, x et renvoie vrai si et seulement si il est pas un multiple de p.

  3. Maintenant que sieve est définie, nous transmettons [2 .. ], la liste de tous les nombres naturels à partir de 2. Ainsi,

    1. Le numéro 2 sera retourné. Tous les autres nombre naturel qui sont un multiple de 2 sera mis au rebut.
    2. Le deuxième numéro est donc 3. Il sera retourné. Tous les autres multiples de 3 seront mis au rebut.
    3. Ainsi, le prochain numéro sera 5. Etc.

Il définit un générateur - un transformateur de courant appelé "tamis" 

Sieve s = 
  while( True ):
      p := s.head
      s := s.tail
      yield p                             -- produce this
      s := Filter (nomultsof p) s         -- go next

primes := Sieve (Nums 2)

qui utilise une forme de cari une fonction anonyme équivalent à 

nomultsof p x = (mod x p) /= 0

Les deux Sieve et Filter sont les opérations de construction de données avec l'état interne et les arguments par valeur sémantique qui passe.

Ici, nous pouvons voir que le problème le plus flagrant de ce code est pas , répétition pas que utilise division d'essai pour filtrer les multiples de la séquence de travail, alors qu'il pourrait les trouver directement , comptage par incréments de p. Si nous devions remplacer l'ancien avec celui-ci, le code résultant aurait encore la complexité d'exécution abyssale.

Non, le problème le plus flagrant est qu'il met un Filter au-dessus de sa séquence de travail trop tôt , quand il devrait vraiment faire seulement après est vu sur la place du premier dans l'entrée. En conséquence, il crée une quadratique nombre de Filters par rapport à ce qui est vraiment nécessaire. La chaîne de Filters qu'il crée est trop long, et la plupart d'entre eux ne sont même pas besoin du tout.

La version corrigée, avec la création de filtre reporté jusqu'à ce que le bon moment est 

Sieve ps s = 
  while( True ):
      x := s.head
      s := s.tail
      yield x                             -- produce this
      p := ps.head
      q := p*p
      while( (s.head) < q ):
          yield (s.head)                  --    and these
          s := s.tail
      ps := ps.tail                       -- go next
      s  := Filter (nomultsof p) s

primes := Sieve primes (Nums 2)

ou Haskell, 

primes = sieve primes [2..] 
sieve ps (x:xs) = x : h ++ sieve pt [x | x <- t, rem x p /= 0]
     where (p:pt) = ps
           (h,t)  = span (< p*p) xs

rem est utilisé ici au lieu de mod car il peut être beaucoup plus rapide dans certains interprètes, et les chiffres sont tous positifs ici de toute façon.

Mesure de la commandes locales de croissance d'un algorithme en prenant son temps d'exécution t1,t2 aux points de la taille du problème n1,n2, comme logBase (n2/n1) (t2/t1), nous obtenons O(n^2) pour le premier, et juste au-dessus O(n^1.4) pour la deuxième (en nombres premiers n produit).

Juste pour clarifier, les parties manquantes pourraient être définies dans cette langue (imaginaire) simplement comme 

Nums x =            -- numbers from x
  while( True ):
      yield x
      x := x+1

Filter pred s =     -- filter a stream by a predicate
  while( True ):
      if pred (s.head) then yield (s.head)
      s := s.tail

voir aussi .

Mise à jour: Curieusement, la première instance de ce code en 1976 manuel SASL de David Turner selon A.J.T. 1992 livre Haskell Davie, 

    primes = sieve [2..]

    sieve (p:nos) = p : sieve (remove (multsof p) nos)

admet en fait deux paires de mises en œuvre pour remove et multsof vont ensemble - une paire pour le tamis de la division de première instance dans cette question, et l'autre pour l'élimination ordonnée des multiples de chaque prime généré directement par comptage, alias véritable crible d'Eratosthène (les deux seraient non-remise, bien sûr). Dans Haskell, 

    multsof p n = rem n p==0            remove m xs = filter (not . m) xs

    multsof p = [p*p, p*p+p..]          remove m xs = diff xs m

(Si seulement il avait reporté choisir la mise en œuvre réelle ...)

En ce qui concerne le code reporté, dans un pseudocode avec "motifs de liste", il aurait pu être 

    primes = [2, ...sieve primes [3..]]

    sieve [p, ...ps] [...h, p*p, ...nos] =
                     [...h, ...sieve ps (remove (multsof p) nos)]

Il est l'application de la d'Eratosthène Sieve

Fondamentalement, commencer par un premier (2), et un filtrage du reste des entiers, tous les multiples de deux. Le numéro suivant dans la liste filtrée doit aussi être un premier, et donc filtrer tous ses multiples du reste, et ainsi de suite.

Il dit: « le tamis d'une liste est le premier élément de la liste (que nous appellerons p) et le tamis du reste de la liste, filtrée de telle sorte que seuls les éléments non divisible par p sont autorisées par ». Il obtient alors les choses ont commencé par en retournant le tamis de tous les entiers de 2 à l'infini (qui est 2 suivie par le tamis de tous les entiers non divisible par 2, etc.).

Je recommande Le Petit Schemer avant de vous attaquer Haskell.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top