numeros - Explica este fragmento de código haskell que genera una secuencia de números primos

numeros primos en haskell

Question

Tengo problemas para entender este trozo de código:

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

¿Alguien puede desglosarlo por mí? Entiendo que hay recursividad, pero ese es el problema. No puedo entender cómo funciona la recursión en este ejemplo.

Answer 1

Dice "el tamiz de alguna lista es el primer elemento de la lista (que llamaremos p) y el tamiz del resto de la lista, filtrado de modo que solo los elementos no divisibles por p se permiten a través de". Luego inicia las cosas devolviendo el tamiz de todos los enteros de 2 a infinito (que es 2 seguido por el tamiz de todos los enteros no divisibles por 2, etc.).

Recomiendo The Little Schemer antes de atacar a Haskell.

Answer 2

Está implementando el Tamiz de Eratóstenes

Básicamente, comience con un primo (2) y filtre desde el resto de los enteros, todos los múltiplos de dos. El siguiente número en esa lista filtrada también debe ser un primo y, por lo tanto, debe filtrar todos sus múltiplos del resto, y así sucesivamente.

Answer 3

En realidad es bastante elegante.

Primero, definimos un sieve función que toma una lista de elementos:

sieve (p:xs)

En el cuerpo de sieve , tomamos el encabezado de la lista (porque estamos pasando la lista infinita [2..] , y 2 se define como principal) y lo agregamos al resultado de aplicar sieve al resto del lista:

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

Así que veamos el código que hace el trabajo en el resto de la lista:

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

Estamos aplicando sieve a una lista filtrada. Analicemos lo que hace la parte del filtro:

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

filter toma una función y una lista en la que aplicamos esa función, y conserva elementos que cumplen los criterios dados por la función. En este caso, el filter toma una función anónima:

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

Esta función anónima toma un argumento, x . Comprueba el módulo de x contra p (el encabezado de la lista, cada vez que se llama sieve ):

 x ''mod'' p

Si el módulo no es igual a 0:

 ''mod'' p /= 0

Entonces el elemento x se mantiene en la lista. Si es igual a 0, se filtra. Esto tiene sentido: si x es divisible por p , entonces x es divisible por más de 1 y por sí mismo, y por lo tanto no es primo.

Answer 4

Contrariamente a lo que otros han declarado aquí, esta función no implementa el verdadero tamiz de Eratóstenes . Sin embargo, devuelve una secuencia inicial de los números primos, y de manera similar, por lo que está bien pensar que es el tamiz de Eratóstenes.

Estaba a punto de explicar el código cuando mipadi publicó su respuesta; Podría borrarlo, pero ya que pasé un tiempo en él, y debido a que nuestras respuestas no son completamente idénticas, lo dejo aquí.

Primero que todo, tenga en cuenta que hay algunos errores de sintaxis en el código que ha publicado. El código correcto es,

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

1. let x in y define x y permite que su definición se use en y . El resultado de esta expresión es el resultado de y . Entonces en este caso definimos un sieve función y devolvemos el resultado de aplicar [2..] al sieve .

2. Ahora echemos un vistazo más de cerca a la parte let de esta expresión:

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

   1. Esto define un sieve función que toma una lista como su primer argumento.
   2. (p:xs) es un patrón que coincide con p con la cabeza de dicha lista y xs con la cola (todo menos la cabeza).
   3. En general, p : xs es una lista cuyo primer elemento es p . xs es una lista que contiene los elementos restantes. Por lo tanto, sieve devuelve el primer elemento de la lista que recibe.

   4. No mirar el resto de la lista:

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

      1. Podemos ver que el sieve se llama de forma recursiva. Por lo tanto, la expresión de filter devolverá una lista.
      2. filter toma una función de filtro y una lista. Devuelve solo aquellos elementos en la lista para los cuales la función de filtro devuelve verdadero.

      3. En este caso, xs es la lista que se filtra y

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

         es la función de filtro

      4. La función de filtro toma un solo argumento, x y devuelve verdadero si no es un múltiplo de p .

3. Ahora que el sieve está definido, lo pasamos [2 .. ] , la lista de todos los números naturales comenzando en 2. Por lo tanto,

   1. El número 2 será devuelto. Todos los demás números naturales que son múltiplos de 2 serán descartados.
   2. El segundo número es por lo tanto 3. Será devuelto. Todos los demás múltiplos de 3 serán descartados.
   3. Por lo tanto, el próximo número será 5. Etc.

Answer 5

Define un generador - un transformador de corriente llamado "tamiz" ,

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

primes := Sieve (Nums 2)

que usa una forma currificada de una función anónima equivalente a

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

Tanto Sieve como Filter son operaciones de construcción de datos con semántica de paso de argumento de estado interno y de valor por defecto.

Aquí podemos ver que el problema más evidente de este código no es, repita no que utilice la división de prueba para filtrar los múltiplos de la secuencia de trabajo, mientras que podría encontrarlos directamente, contando en incrementos de p . Si tuviéramos que reemplazar el primero con el último, el código resultante todavía tendría una complejidad abismal en tiempo de ejecución.

No, su problema más evidente es que pone un Filter en la parte superior de su secuencia de trabajo demasiado pronto , cuando realmente debería hacer eso solo después de que se vea el cuadrado de la prima en la entrada. Como resultado, la cadena de Filter que crea es demasiado larga , y la mayoría de ellos ni siquiera se necesitan.

La versión corregida, con la creación del filtro pospuesta hasta el momento adecuado, es

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 (notAMultipleOf p) s

primes := Sieve primes (Nums 2) 

o en 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 se usa aquí en lugar de mod ya que puede ser mucho más rápido en algunos intérpretes, y los números son todos positivos aquí de todos modos.

Midiendo las órdenes locales de crecimiento de un algoritmo tomando sus tiempos de ejecución t1,t2 en los puntos de tamaño de problema n1,n2 , como logBase (n2/n1) (t2/t1) , obtenemos O(n^2) para la primera uno, y justo por encima de O(n^1.4) para el segundo (en n primos producidos).

Solo para aclararlo, las partes faltantes podrían definirse en este lenguaje (imaginario) simplemente como

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

ver también