Este es un buen ejercicio para ser más fluido en ese lenguaje de programación que has querido aprender, pero que solo has jugado ligeramente. Esto implica trabajar con objetos, usar o simular cierres y estirar el sistema de tipos.
Su tarea es escribir código para administrar listas perezosas, luego usarlo para implementar este algoritmo para generar números de Fibonacci:
Los ejemplos de código están en Haskell
let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
in take 40 fibs
Resultado:
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986]
La implementación de su lista perezosa debe cumplir con estas pautas:
- Un nodo Lista es una de tres cosas:
- Nil: lista vacía.
[]
- Contras: un solo elemento, junto con una Lista de los elementos restantes:
1 : [2,3,4,5]
(:
es el operador de contras en Haskell) - Thunk: un cálculo diferido que produce un nodo Lista cuando es necesario.
- Nil: lista vacía.
- Es compatible con las siguientes operaciones:
- nil: construye una lista vacía.
- contras - Construye una celda contras.
- thunk: construye un Thunk, dada una función que no toma argumentos y devuelve Nil o Cons.
- force - Dado un nodo Lista:
- Si es Nil o Contras, simplemente devuélvalo.
- Si es un Thunk, llame a su función para obtener un Nil o Contras. Reemplace el golpe con ese Nil o Contras, y devuélvalo.
Nota: Reemplazar el thunk con su valor forzado es una parte importante de la definición de "perezoso" . Si se omite este paso, el algoritmo de Fibonacci anterior será demasiado lento.
- vacío: comprueba si un nodo Lista es Nulo (después de forzarlo).
- head (también conocido como "auto"): obtén el primer elemento de una lista (o haz un ataque si es Nil).
- tail (también conocido como "cdr"): obtenga los elementos después del encabezado de una lista (o haga un ajuste si es Nil).
- zipWith: dada una función binaria (p
(+)
. ej. ) y dos listas (posiblemente infinitas), aplique la función a los elementos correspondientes de las listas. Ejemplo:
zipWith (+) [1,2,3] [1,1,10] == [2,3,13]
- take: dado un número N y una lista (posiblemente infinita), tome los primeros N elementos de la lista.
- print: imprime todos los elementos de una lista. Esto debería funcionar de forma incremental cuando se le da una lista larga o infinita.
fibs
se utiliza en su propia definición. Configurar la recursividad perezosa es un poco complicado; deberás hacer algo como esto:- Asignar un golpe para
fibs
. Déjalo en un estado ficticio por ahora. - Defina la función thunk, que depende de una referencia a
fibs
. - Actualiza el thunk con su función.
Es posible que desee ocultar esta tubería definiendo una función
fix
que llame a una función de retorno de Lista con su propio valor de retorno. Considera tomar una siesta corta para que esta idea pueda surgir.- Asignar un golpe para
No se requiere el polimorfismo (la capacidad de trabajar con listas de cualquier tipo de elemento), pero vea si puede encontrar una manera de hacerlo que sea idiomática en su idioma.
- No te preocupes por la gestión de la memoria. Incluso los idiomas con recolección de basura tienden a transportar objetos que nunca volverá a usar (por ejemplo, en la pila de llamadas), así que no se sorprenda si su programa pierde memoria mientras recorre una lista infinita.
Siéntase libre de desviarse ligeramente de estas pautas para acomodar los detalles de su idioma, o explorar enfoques alternativos para listas perezosas.
Reglas:
- Elige un idioma que no conozcas bien. No puedo "exigir" esto, de ahí la etiqueta "sistema de honor". Sin embargo, los votantes pueden revisar su historial para ver en qué idiomas ha estado publicando.
No use el soporte integrado de la lista diferida de su idioma para hacer todo. Publicar algo sustancial o al menos interesante.
Haskell está prácticamente fuera. Es decir, a menos que haga algo como esto:
data List a = IORef (ListNode a) data ListNode a = Nil | Cons !a !(List a) | Thunk !(IO (ListNode a))
Nota: La evaluación no estricta de Haskell no está prohibida, pero la implementación de su lista perezosa no debería derivar su capacidad directamente de allí. De hecho, sería interesante ver una solución eficiente y puramente funcional que no requiera pereza.
Pitón:
- No utilices itertools.
- Los generadores están bien, pero si los usa, tendrá que encontrar alguna forma de memorizar valores forzados.
fuente
zipWith
dos listas de diferentes longitudes?zipWith (+) [1,2,3,4,5] [0,0,0] == [1,2,3]
. Sin embargo, esto no importa para el algoritmo de Fibonacci anterior, ya que ambos argumentos para zipWith son listas infinitas.fibs
correctamente, ya que depende de sí mismo. Actualicé la pregunta para elaborar sobre la recursión perezosa. FUZxxl lo descubrió por sí mismo.Respuestas:
Posdata
He jugado con PostScript antes , pero no diría que lo sé particularmente bien (de hecho, supongo que puedes contar la cantidad de personas en el mundo que realmente conocen PostScript con una mano).
Me desvié de su especificación en que la función que se usa para crear un thunk puede devolver otro thunk;
force
seguirá evaluando hasta que el resultado sea anil
o acons
.Las listas se implementan como diccionarios:
El código sigue. Tenga en cuenta que estamos sobrescribiendo algunos operadores incorporados (en particular
print
; no he verificado si hay más); en el uso en el mundo real, esto debería ser vigilado. Por supuesto, no habrá uso en el mundo real, así que está bien.Los comentarios antes de los procedimientos deben leerse como
es decir, mostrar el contenido esperado de la pila antes de la llamada y el contenido resultante de la pila después de la llamada. Los comentarios dentro de los procedimientos muestran el contenido de la pila después de que se haya ejecutado la línea particular.
Cargue esto en Ghostscript, ignorando la página mostrada; solo estamos trabajando con el intérprete. Aquí está el algoritmo de Fibonacci:
Dos funciones interesantes adicionales:
Comience a contar en 5, multiplique cada elemento de la lista resultante con 3 y muestre los primeros diez valores:
Con respecto al polimorfismo: aunque PostScript está fuertemente tipado, permite tipos arbitrarios como valores de diccionario, por lo que puede agregar lo que quiera:
Tenga en cuenta que los errores de tipo, por ejemplo, al intentar agregar cadenas a los números, solo sucederán en el momento de la evaluación:
fuente
force
memoriza los valores devueltos?copy
operador copia el contenido de la versión evaluada en el original, sobrescribiendo/type
y posiblemente estableciendo otros valores. Después de la evaluación de forma recursiva hasta que tengamos unanil
ocons
, también (a través deundef
) elimina/func
y, en su caso,/data
. El último paso no es estrictamente necesario (/func
y/data
simplemente sería ignorado), pero dejar este paso fuera perdería aún más memoria :)do
Soy un principiante total en C, este código es en realidad el primer elemento real que codifiqué en C. Se compila sin advertencias y funciona bien en mi sistema.
Cómo construir
Primero, obtenga el tarball de mi servidor . Incluye un archivo MAKE, así que solo ejecuta
make
para construirlo y luegomake run
para ejecutarlo. Luego, el programa imprime una lista de los primeros 93 números de Fibonacci. (Después del número 94, se desborda un entero de 64 bits sin signo)Explicación
El núcleo de los programas es el archivo
lazy-list.c
. En el archivo de encabezado correspondiente, defino una estructuralist
, esa es nuestra lista perezosa. Se parece a esto:El miembro
kind
es una especie de etiqueta. Marca, si buscamos las listas end (NIL
), una celda que ya está evaluada (CONS
) o un thunk (THUNK
). Luego, sigue una unión. EsEl contenido de la unión es afirmado por la etiqueta. Si la etiqueta es
NIL
, el contenido de la unión no está definido.Al definir las funciones auxiliares mencionadas en la especificación anterior, generalmente se puede abstraer la definición de listas de su uso, por ejemplo. simplemente puede llamar
nil()
para obtener una lista vacía en lugar de crearla usted mismo.Las tres funciones más interesantes son
zipWith
,take
yfibonaccis
. Pero no quiero explicartake
, ya que es muy similar azipWith
. Todas las funciones, que operan perezosamente, tienen tres componentes:En caso de
zipWith
, estos sonzipWith
,__zipWith
y__zipArgs
. Solo los muestro aquí sin más explicaciones, su función debería ser bastante clara:La otra función interesante es
fibonaccis()
. El problema es que necesitamos pasar un puntero de la primera y segunda celda al thunk de la tercera, pero para crear esas celdas también necesitamos un puntero al thunk. Para resolver ese problema, llené el puntero al thunk con unNULL
primero y lo cambié al thunk, después de que se creó. Aquí está la escucha:Posibles mejoras.
content_t
, que puede cambiar a lo que sea apropiado.fuente
void*
como tipo decontent_t
.void*
también, pero pensé que eso evitaría el sistema de tipos demasiado. ¿No es posible usar plantillas?void*
y amigos.kind
es una especie de etiqueta". Podrías llamarlotag
, ya que es un término bastante aceptado para el concepto (por ejemplo , unión etiquetada , máquina G sin etiqueta de Spineless . Por otro lado, "amable" tiene un significado diferente en un Contexto de Haskell: el tipo de un tipo.Int
Tiene amable*
,[]
tiene amable* -> *
y(,)
tiene amable* -> * -> *
.C ++
Esta es la cosa más grande que he escrito en C ++. Normalmente uso Objective-C.
Es polimórfico pero nunca libera nada.
Mi
main
función (y laadd
función paraZipWith
) terminó luciendo así:Esto da
Las clases funcionan así:
Fuente completa: aquí . Es un desastre, principalmente porque está en un archivo grande.
Editar: cambió el enlace (el anterior estaba muerto).
fuente
()
operador) y usar la herencia para evitar tener que usarlavoid*
. Vea aquí un ejemplo trivial de hacer eso.Pitón
No utiliza generadores para implementar la lista, solo para implementar el
__iter__
método para usar confor
.La lista de Fibonacci se crea así:
fuente
self.__class__ = node.__class__
. Tenga en cuenta que esto golpea una excepción NotImplemented cuando llega a 2971215073 (largo), que aparentemente es un argumento no válido para int .__ add__. Para admitir enteros grandes, hazlofib.append(fib.zip_with(lambda a,b: a+b, fib.tail()))
Rubí
Mi primer programa Ruby. Representamos todos los nodos como matrices, donde la longitud de la matriz determina el tipo:
El código es bastante sencillo, con un truco para restablecer la función thunk para configurar la fibra recursiva.
fuente
[...]
lugar deArray[...]
.Google Go
Relativamente un nuevo idioma, y lo aprendí por
CTRL+F
ing del Spec .El problema se solucionó al tratar con thunk-inside-a-thunks. Sin embargo, parece que el compilador en línea no puede tomar 40 elementos, tal vez debido a la memoria. Lo probaré en mi Linux más tarde.
Probé el código con el compilador en línea , porque no puedo instalar Go en Windows fácilmente.
fuente
iota
generador constante. Vea un ejemplo en la Especificación del lenguaje de programación Go y una respuesta en StackOverflow .Fibs
función no funciona porque Go utiliza una evaluación estricta y seFibs
repite sin una condición de terminación.Fibs0
/Fibs1
utiliza un enfoque generador simple en lugar del algoritmo descrito en mi publicación, por lo que no cumple con los "requisitos". Actualicé mi publicación para elaborar sobre la recursividad perezosa, que es necesaria para implementarfibs = 0 : 1 : zipWith (+) fibs (tail fibs)
.Cons(0, Cons(1, ZipWith(Plus, Thunk(Fibs), Tail(Thunk(Fibs)))))
, se queda sin memoriaCons(0, Cons(1, Thunk(func() List { return ZipWith(Plus, Thunk(Fibs), Thunk(func() List { return Tail(Fibs()) })) })))
y recibo un error de dirección de memoria no válidaCristal
A pesar de seguir el repositorio de GitHub, nunca he usado Crystal hasta ahora. Crystal es una variante Ruby de tipo estático con inferencia de tipo completo. Aunque ya hay una respuesta de Ruby, el tipeo estático de Crystal me llevó a usar el polimorfismo, en lugar de una matriz, para representar los nodos. Debido a que Crystal no permite la modificación de
self
, creé una clase de contenedor, llamadaNode
, que envolvería todo lo demás y administraría los thunks.Junto con las clases, he creado las funciones constructoras
lnil
,cons
ythunk
. Nunca antes he usado Ruby para más de un guión de 20 líneas, por lo que las cosas del bloque me desconcertaron bastante.Basé la
fib
función en la respuesta Go .fuente
Doblé un poco las reglas porque todavía no hay una solución .NET aquí, o más generalmente una solución OOP, excepto la de Python que usa la herencia, pero es lo suficientemente diferente de mi solución para hacer que ambas sean interesantes (en particular desde Python permite modificar el
self
instancia, haciendo que la implementación de thunk sea sencilla).Entonces esto es C # . Divulgación completa: no estoy cerca de un principiante en C #, pero no he tocado el idioma desde hace tiempo, ya que actualmente no lo uso en el trabajo.
Los puntos más destacados:
Todas las clases (
Nil
,Cons
,Thunk
) se derivan de una clase base abstracta comúnList
.La
Thunk
clase usa el patrón Envelope-Letter . Básicamente, esto emula laself.__class__ = node.__class__
asignación en la fuente de Python, ya que lathis
referencia no se puede modificar en C #.IsEmpty
,Head
yTail
son propiedades.Todas las funciones apropiadas se implementan de forma recursiva y perezosa (a excepción de
Print
, que no puede ser perezosa) devolviendo thunks. Por ejemplo, esto esNil<T>.ZipWith
:... y esto es
Cons<T>.ZipWith
:Desafortunadamente, C # no tiene envío múltiple, de lo contrario también podría deshacerme de la
if
declaración. Por desgracia, no hay dados.Ahora, no estoy muy contento con mi implementación. Estoy feliz hasta ahora porque todo lo anterior es totalmente sencillo. Pero . Siento que la definición de
Fib
es innecesariamente complicada ya que necesito envolver los argumentos en thunks para que funcione:(Aquí
List.Cons
,List.Thunk
yList.ZipWith
son envolturas de conveniencia).Me gustaría entender por qué la siguiente definición mucho más fácil no funciona:
dada una definición apropiada de
Concat
, por supuesto. Esto es esencialmente lo que hace el código Python, pero no funciona (= lanzar un ajuste)./ EDITAR: Joey ha señalado la falla obvia en esta solución. Sin embargo, reemplazar la segunda línea con un thunk también produce un error (Mono segfaults; sospecho que se desborda una pila que Mono no maneja bien):
El código fuente completo se puede encontrar como una esencia en GitHub .
fuente
fib.ZipWith
yfib.Tail
usa lo viejofib
, que permanece[0,1]
y no cambia. Por lo tanto, obtienes[0,1,1]
(creo), y tuTake
función no te permite tomar de nulo (sin embargo, la toma de Haskell sí). Intente envolver el valor de la segunda línea en un thunk, para que se refiera al nuevo enfib
lugar del antiguo.Pico
Para el registro, esta solución utiliza una traducción de la fuerza de retardo del esquema como se define en srfi-45 . y crea listas perezosas además de eso.
las miradas de salida como esta: (pero dependiendo de cómo
tpico
. parcheado se podría tener más comillas dobles en elladisplay
. normalmente imprime cadenas con comillas es decir, todas las apariciones de[
,,
,]
tendría comillas alrededor de ellos como"["
.)debido a los límites del tipo de datos entero en tpico, esto falla al calcular el 45º (o 46º desplazamiento) número de Fibonacci.
tenga en cuenta que tpico 2.0pl11 se divide en eso
begin(a,b)
(que comúnmente se escribe como{a;b}
) y laif
función no es recursiva de cola. sin mencionar que me llevó 5 años descubrir por québegin
no era recursiva la cola. También en ese momento escribí la traducción de srfi-45 en Pico. resultó ser quebegin
estaba esperando el valor deb
antes de regresar cuando no necesitaba esperar. y una vez que lo conseguí, también pude arreglarloif
ya que tenía el mismo problema. y hubo este otro error que hizo que el constructor de nivel metamake
no funcionara.Pico permite que una función controle si sus argumentos se evalúan antes de que se llame a la función o simplemente se empaquetan como thunks. para este código, puedo elipsis sobre las rarezas de la llamada por función .
Pico no tiene inferencia de tipo. Pensé en esto por un tiempo, pero me encontré con un problema debido a las rarezas de call by function . Se me ocurrió la afirmación de que los tipos deben codificar la existencia de nombres de variables enlazadas . pero estaba pensando principalmente en cómo adaptar la inferencia de tipo Hindley-Milner a un subconjunto de Pico sin mutación. La idea principal era que el verificador de tipos devuelve múltiples esquemas posibles si hay más de un enlace posible y el verificador de tipos tiene éxito si hay al menos un esquema de tipos posible . un posible esquema es aquel en el que ninguna asignación de tipo entra en conflicto.
fuente