Uso adecuado de la recursión de la cola al formar una lista -- functional-programming campo con scheme camp codereview Relacionados El problema

Proper use of tail recursion while forming a list


1
vote

problema

Español

Como proyecto para desarrollar mejor mi comprensión de la programación funcional, estoy escribiendo un generador de números primarios en el esquema. Estoy usando un simple algoritmo de fuerza bruta para detectar si un número es primo y sé que hay mejores algoritmos. Lo que estoy interesado es si mi intento en el algoritmo de la fuerza bruta se puede escribir mejor y si estoy usando la recursión de la cola de manera adecuada y formando la lista de manera eficiente. El objetivo es tener una lista de números al final que pueda usar para alguna tarea o imprimir. Tal vez incluso escribirlo como generador donde puedo preguntarlo continuamente por el próximo primo. Aquí está mi código actual:

  (define is_prime1  (lambda(num div)   (if (= num div)    #t    (if (= (remainder num div) 0)     #f     (is_prime1 num (+ div 1))    )   )  ) )  (define is_prime  (lambda(num)   (if (< num 2) #f (is_prime1 num 2))  ) )  (define list_primes1  (lambda(idx num)   (if (<= idx num)    (if (not (is_prime idx))     (list_primes1 (+ idx 1) num)     (cons idx      (list_primes1 (+ idx 1) num)     )    )    '()   )  ) )  (define list_primes  (lambda(num)   (list_primes1 0 num)  ) )  (define print_primes  (lambda(primes)   (if (null? primes)    '()    (list     (display (car primes))     (newline)     (print_primes (cdr primes))    )   )  ) )  (print_primes (list_primes 4095))   
Original en ingles

As a project to better develop my understanding of functional programming, I am writing a prime number generator in Scheme. I am using a simple brute-force algorithm to detect whether a number is prime and I know there are better algorithms. What I'm interested is whether my attempt at the brute-force algorithm can be better written and whether I am using tail recursion appropriately and forming the list efficiently. The goal is to have a list of numbers at the end I can use for some task or print out. Maybe even write it as a generator where I can continually ask it for the next prime. Here is my current code:

(define is_prime1  (lambda(num div)   (if (= num div)    #t    (if (= (remainder num div) 0)     #f     (is_prime1 num (+ div 1))    )   )  ) )  (define is_prime  (lambda(num)   (if (< num 2) #f (is_prime1 num 2))  ) )  (define list_primes1  (lambda(idx num)   (if (<= idx num)    (if (not (is_prime idx))     (list_primes1 (+ idx 1) num)     (cons idx      (list_primes1 (+ idx 1) num)     )    )    '()   )  ) )  (define list_primes  (lambda(num)   (list_primes1 0 num)  ) )  (define print_primes  (lambda(primes)   (if (null? primes)    '()    (list     (display (car primes))     (newline)     (print_primes (cdr primes))    )   )  ) )  (print_primes (list_primes 4095)) 
     
 
 

Lista de respuestas

4
 
vote
vote
La mejor respuesta
 

Su algoritmo está bien, pero el problema real con este código es que su estilo de código es atroz, bordeando en forma ilegible. Su estilo exhibe cuatro problemas principales:

  1. El esquema no es C, y los paréntesis no son frenos rizados. No coloque parentes cercanos en líneas separadas. El código del esquema está destinado a ser leído principalmente observando la sangría, lo que me lleva al siguiente punto.

  2. Tu sangría es incorrecta. Nuevamente, el esquema no es C, y las expresiones deben ser sangradas para alinear subexpresiones, no con un sangría constante de 1-, 2 o 4 espacios. Para una explicación de por qué esto es tan importante, consulte Esta pila de desbordamiento Respuesta .

  3. Este es un punto menos significativo, pero su uso explícito de lambda aquí es innecesario. Hay una forma de taquigrafía con define que es equivalente a define emparejado con lambda , y es más idiomático y más fácil de analizar visualmente.

  4. Los identificadores en el esquema deben ser guiones ( lisp-case4 ), no separados por los subrosos ( 99887776655544335 ).

Sólo siguiendo los cambios de formato anterior, su código se vuelve mucho más legible para un Schemer:

  (define (is-prime1 num div)   (if (= num div)       #t       (if (= (remainder num div) 0)           #f           (is-prime1 num (+ div 1)))))  (define (is-prime num)   (if (< num 2) #f (is-prime1 num 2)))  (define (list-primes1 idx num)   (if (<= idx num)       (if (not (is-prime idx))           (list-primes1 (+ idx 1) num)           (cons idx                 (list-primes1 (+ idx 1) num)))       '()))  (define (list-primes num)   (list-primes1 0 num))  (define (print-primes primes)   (if (null? primes)       '()       (list (display (car primes))             (newline)             (print-primes (cdr primes)))))  (print-primes (list-primes 4095))   

Ahora podemos enfocarnos en algunas mejoras de código más sustantivas. En primer lugar, print-primes es un candidato fácil para la eliminación. No solo produce innecesariamente una lista, puede implementarse trivialmente utilizando la función 9988776665544338 de orden superior. El nombre también es tonto, ya que no imprime números primos, imprime cada elemento de una lista . No hay razón para incluir la palabra "primos" en el nombre.

En su lugar, simplemente reemplace toda la función con un simple uso de for-each :

  define0  

A continuación, veamos la mayor parte del código. Ha definido define1 En términos de funciones de ayuda, define2 . Dado que todo su función está haciendo es llamar define4 con algunos argumentos establecidos, puede reemplazar la función de ayuda con un uso de " nombrado 99887776655443315 ":

  define6  

También tiene un par de 99887766555443317 99887766655443318 :

  define9  

Echando un vistazo a define0 define1 , podemos reemplazar una vez más define2 Con el uso de nombre define3 :

  define4  

Sin embargo, esto sigue siendo mucho más complicado de lo que debe ser. Debido a la forma en que el esquema define5 define6655443326 son "sinceridad", donde todos los valores no 99887776555443327 son veraces, podemos Reemplace la mayoría de los usos de define8 con define9 o lambda0 :

  lambda1  

TAMBIENTE, PODEMOS REEMPLAZAR lambda2 CON EL lambda33 Predicado para mejorar la legibilidad:

  lambda4  

Ahora, vale la pena señalar que lambda5 no es Caall Recursive, ya que en el segundo lambda6 , una llamada a lambda7 está en la posición de la cola, no 99887776655443338 . Una forma de hacer esta función la cola recursiva es construir una lista iterativamente, luego 99887776655443339 al final:

  lisp-case0  

Esto nos deja con el programa final, completamente recursivo de la cola:

  lisp-case1  
 

Your algorithm is okay, but the real issue with this code is that your code style is atrocious, bordering on unreadable. Your style exhibits four main problems:

  1. Scheme is not C, and parentheses are not curly braces. Do not put close parens on separate lines. Scheme code is intended to be read primarily by observing indentation, which brings me to the next point.

  2. Your indentation is wrong. Again, Scheme is not C, and expressions should be indented to align subexpressions, not with a consistent 1-, 2- or 4-space indent. For an explanation of why this is so important, see this Stack Overflow answer.

  3. This is a less significant point, but your explicit use of lambda here is unnecessary. There is a shorthand form with define that is equivalent to define paired with lambda, and itxe2x80x99s more idiomatic and easier to visually parse.

  4. Identifiers in Scheme should be hyphenated (lisp-case), not separated by underscores (snake_case).

Just following the above formatting changes, your code becomes much more readable to a Schemer:

(define (is-prime1 num div)   (if (= num div)       #t       (if (= (remainder num div) 0)           #f           (is-prime1 num (+ div 1)))))  (define (is-prime num)   (if (< num 2) #f (is-prime1 num 2)))  (define (list-primes1 idx num)   (if (<= idx num)       (if (not (is-prime idx))           (list-primes1 (+ idx 1) num)           (cons idx                 (list-primes1 (+ idx 1) num)))       '()))  (define (list-primes num)   (list-primes1 0 num))  (define (print-primes primes)   (if (null? primes)       '()       (list (display (car primes))             (newline)             (print-primes (cdr primes)))))  (print-primes (list-primes 4095)) 

Now we can focus on some more substantive code improvements. First of all, print-primes is an easy candidate for elimination. Not only does it needlessly produce a list, it can be trivially implemented using the for-each higher-order function. The name is also silly, since it does not print primes, it prints each element of a list. There is no reason to include the word xe2x80x9cprimesxe2x80x9d in the name.

Instead, just replace the whole function with a simple use of for-each:

(define (displayln x) (display x) (newline)) (for-each displayln (list-primes 4095)) 

Next, letxe2x80x99s look at the bulk of the code. You have defined list-primes in terms of a helper functions, list-primes1. Since all your list-primes function is doing is calling list-primes1 with some arguments set, you can replace the helper function with a use of xe2x80x9cnamed letxe2x80x9d:

(define (list-primes num)   (let loop ((idx 0)              (num num))     (if (<= idx num)         (if (not (is-prime idx))             (loop (+ idx 1) num)             (cons idx                   (loop (+ idx 1) num)))         '()))) 

You also have a pair of nested ifs, which might be more readably represented with a cond:

(define (list-primes num)   (let loop ((idx 0)              (num num))     (cond       ((> idx num)        '())       ((is-prime idx)        (cons idx (loop (+ idx 1) num)))       (else        (loop (+ idx 1) num))))) 

Taking a look at is-prime and is-prime1, we can once again replace is-prime1 with a use of named let:

(define (is-prime num)   (if (< num 2)       #f       (let loop ((num num)                  (div 2))         (if (= num div)             #t             (if (= (remainder num div) 0)                 #f                 (loop num (+ div 1))))))) 

However, this is still much more complicated than it needs to be. Due to how Schemexe2x80x99s and and or are both short-circuiting and implement xe2x80x9ctruthinessxe2x80x9d, where all non-#f values are truthy, we can replace most of the uses of if with and or or:

(define (is-prime num)   (and (>= num 2)        (let loop ((num num)                   (div 2))          (or (= num div)              (and (not (= (remainder num div) 0))                   (loop num (+ div 1))))))) 

Also, we can replace (= x 0) with the zero? predicate to improve readability:

(define (is-prime num)   (and (>= num 2)        (let loop ((num num)                   (div 2))          (or (= num div)              (and (not (zero? (remainder num div)))                   (loop num (+ div 1))))))) 

Now, itxe2x80x99s worth noting that list-primes is not tail recursive, since in the second cond case, a call to cons is in tail position, not loop. A way to make this function tail recursive is to build up a list iteratively, then reverse it at the end:

(define (list-primes num)   (reverse    (let loop ((idx 0)               (num num)               (acc '()))      (cond        ((> idx num)         acc)        ((is-prime idx)         (loop (+ idx 1) num (cons idx acc)))        (else         (loop (+ idx 1) num acc)))))) 

This leaves us with the final, completely tail-recursive program:

(define (is-prime num)   (and (>= num 2)        (let loop ((num num)                   (div 2))          (or (= num div)              (and (not (zero? (remainder num div)))                   (loop num (+ div 1)))))))  (define (list-primes num)   (reverse    (let loop ((idx 0)               (num num)               (acc '()))      (cond        ((> idx num)         acc)        ((is-prime idx)         (loop (+ idx 1) num (cons idx acc)))        (else         (loop (+ idx 1) num acc))))))  (define (displayln x) (display x) (newline)) (for-each displayln (list-primes 4095)) 
 
 
 
 
2
 
vote

Primero, algunas convenciones útiles de notación:

  1. en LiSp Languages ​​ - se usa comúnmente en _ para formar sustantivos compuestos (por lo 9988777665544332 en lugar de is_prime , etc.).
  2. Los paréntesis cerrados no se escriben en una línea separada, sino al final de la línea que cierran.
  3. La sangría estándar es de dos caracteres, y los argumentos de una función en diferentes líneas están alineados a la misma distancia del primer argumento.

recursión de cola

Mientras is-prime1 es recursivo de la cola, list-primes15 y print-primes son no cola recursiva. La razón es que, en ambos casos, la llamada recursiva no es la última: en list-primes1 Se pasa el resultado de la llamada recursiva a cons , mientras que en print-primes < / Código> Se pasa a _0 .

Para definir _1 como recursivo de la cola, debe usar la técnica de pasar un nuevo parámetro a la función, el "acumulador", que recopila los elementos mientras se encuentran. Por ejemplo:

  _2  

Tenga en cuenta que el nuevo parámetro se inicializa con una lista vacía dentro de _3 , y se invierte al final de la recursión para producir la lista resultante en el orden creciente.

Aquí hay una posible definición de cola recursiva de _4 :

  _5  

Tenga en cuenta que el _6 desea realizar efectos secundarios (valores de impresión) y, dado que es un operador especial para la secuenciación, la llamada recursiva se puede compilar como la recursión de la cola. Tenga en cuenta también que, de esta manera, la lista fea de valores de vacío no se imprime al final de la llamada de la función, solo se imprimen los primos.

Uso de _7 y _8 en lugar de _9

Cuando una expresión condicional devuelve un valor booleano, en las lenguas Lisp es más idiomático para usar los operadores especiales is-prime0 99887766555443321 , ya que evalúan sus argumentos solo cuando sea necesario. Por ejemplo:

  is-prime2  

is-prime3 detiene la evaluación de sus argumentos tan pronto como uno de ellos es 99887766555443324 , devolviendo 99887776655443325 , de lo contrario devuelve el valor de la última argumento; is-prime6 detiene la evaluación de sus argumentos tan pronto como uno de los no es is-prime7 , de lo contrario, devuelve is-prime8 .

 

First, a few useful notation conventions:

  1. In Lisp languages - is commonly used instead of _ to form composite nouns (so is-prime instead of is_prime, etc.).
  2. Closed parentheses are not written on a separate line, but at the end of the line they close.
  3. Standard indentation is two characters, and the arguments of a function on different lines are aligned at the same distance of the first argument.

Tail recursion

While is-prime1 is tail-recursive, list-primes1 and print-primes are not tail recursive. The reason is that in both cases the recursive call is not the last one: in list-primes1 the result of the recursive call is passed to cons, while in print-primes it is passed to list.

To define list-primes1 as tail recursive, you should use the technique of passing a new parameter to the function, the xe2x80x9caccumulatorxe2x80x9d, which collects the elements while they are found. For instance:

(define list-primes1   (lambda (idx num acc)     (if (<= idx num)         (if (not (is-prime idx))             (list-primes1 (+ idx 1) num acc)             (list-primes1 (+ idx 1) num (cons idx acc)))         (reverse acc))))  (define list-primes   (lambda (num)     (list-primes1 0 num '()))) 

Note that the new parameter is initialized with an empty list inside list-primes, and it is reversed at the end of the recursion in order to produce the resulting list in increasing order.

Here is a possible tail-recursive definition of print-primes:

(define print-primes   (lambda (primes)     (if (null? primes)         '()         (begin           (display (car primes))           (newline)           (print-primes (cdr primes)))))) 

Note that the begin is needed since you want to perform side-effects (print values), and since it a special operator for sequencing, the recursive call can be compiled as tail recursion. Note also that, in this way, the ugly list of void values is not printed at the end of of the call of the function, only the primes are printed.

Use of and and or instead of if

When a conditional expression returns a boolean value, in Lisp languages is more idiomatic to use the special operators and and or, since they evaluate their arguments only when needed. For instance:

(define is-prime1   (lambda (num div)     (or (= num div)         (and (not (= (remainder num div) 0))              (is-prime1 num (+ div 1))))))  (define is-prime   (lambda (num)     (and (>= num 2) (is-prime1 num 2)))) 

and stops the evaluation of its arguments as soon as one of them is #f, returning #f, otherwise returns the value of the last argument; or stops the evaluation of its arguments as soon as one of the is not #f, returning its value, otherwise it returns #f.

 
 

Relacionados problema

6  Redefinir las hojas de recuento como una acumulación  ( Redefine count leaves as an accumulation ) 
Ejercicio 2.35. Redefinir hojas de recuento Desde la sección 2.2.2 como acumulación: (define (count-leaves t) (accumulate <??> <??> (map <??> <??>))) ...

5  Invertir en términos de pliegue derecho y plegable-izquierda  ( Reverse in terms of fold right and fold left ) 
Ejercicio 2.39 Completar las siguientes definiciones de reversa (Ejercicio 2.18) en términos de pliegue derecho y plegable-izquierda del ejercicio 2....

3  Marco de intérpretes para escribir intérpretes similares a esquema en <60 loc  ( Interpreter framework for writing scheme like interpreters in 60 loc ) 
Escribí este intérprete hace un tiempo y esperaba que pudiera conseguir Algunos comentarios / críticas. Es algo similar a los "idiomas como bibliotecas" con...

4  Función abstracta del mapa del árbol  ( Abstract tree map function ) 
Ejercicio 2.31. Resumen tu respuesta Para ejercer 2.30 para producir un Procedimiento Árbol - Mapa con la propiedad. ese árbol cuadrado podría definirs...

5  Multiplicación de matriz y producto de punto  ( Matrix multiplication and dot product ) 
Ejercicio 2.37. Supongamos que representamos vectores v = (vi) como secuencias de números, y matrices m = (MIJ) como secuencias de vectores (las filas ...

0  Valor numérico para una fecha, DataTado y Datediff  ( Numeric value for a date dateadd and datediff ) 
En MS Excel, una fecha también se representa como un valor numérico, con el 1-enero-1900 como el primer día. También en VBA hay funciones de DataLTD y Datedif...

6  Tamiz puramente funcional de eratóstenes  ( Purely functional sieve of eratosthenes ) 
Muchas implementaciones de tamiz de eratóstenes (usados ​​para encontrar números primos hasta un N) Use una matriz mutable temporal para realizar un seguimien...

8  Encuentra todos los triples distintos menos que n esa suma a s  ( Find all distinct triples less than n that sum to s ) 
Ejercicio 2.41. Escribe un procedimiento para Encuentra todos los triples pedidos de distintos. enteros positivos i, j, y k menos que o igual a un ente...

1  Definiendo un procedimiento único de pares  ( Defining a unique pairs procedure ) 
de la sección llamada asignaciones anidadas Ejercicio 2.40 Definir un procedimiento PAÍS ÚNICAS QUE, DADO UN INTEGER #pragma once #include <windo...

1  Árbol cuadrado con mapas y recursión  ( Square tree using maps and recursion ) 
Defina un procedimiento de árbol cuadrado análogo a la Procedimiento de la lista cuadrada del ejercicio. 2.21. Es decir, la lista cuadrada debe comportar...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos