en cuenta la (Haskell) siguiente código:¿Es esta función de secuencia de Fibonacci recursiva?
fib=0:1:zipWith (+) fib (tail fib)
Un compañero de trabajo está tratando de afirmar que esto no es una función recursiva, ya fib es simplemente una lista que se define con ella misma y que es de alguna manera diferente a una función que hace lo mismo Creo que está fumando crack.
¿Qué opinas?
La definición de fibonacci con zipWith no es una función recursiva, de hecho no hay ninguna función involucrada, fib es una lista (datos) que se define de forma perezosa, utilizando la semántica perezosa de Haskell. En cierto sentido, puede llamarlo lista recursiva o datos recursivos; pero no es una función recursiva.
Puede ser difícil pensar en la lista recursiva ya que muy pocos lenguajes de programación tienen algo cercano, pero notará que en Haskell todas las funciones toman exactamente un parámetro. fib no toma ningún parámetro, porque no es una función. Como no hay ninguna función involucrada, no puede tener una función recursiva.
Su compañero de trabajo no está fumando crack, está iluminado (o fumando crack, si esa es su definición de iluminación).
Esto simplemente está mal: 'zipWith' es una función recursiva que define la secuencia.'fib' no es una lista recursiva: es una lista simple, no recursiva que se refiere al * resultado de evaluar la función recursiva' zipWith' *. (Sí, Haskell también admite datos recursivos, pero esto se refiere a definiciones como 'xs = 1: 2: 3: xs', no al ejemplo de la pregunta). –
@Piet Delport:' fib' aparece en el lado derecho de su propia definición ... ¿qué palabra usas para eso? Yo llamo a eso "recursivo". Ni la recursividad ni la funcionalidad (¿funcionalidad?) De 'zipWith' se está cuestionando aquí. –
pelotom: en Haskell, existe una diferencia fundamental entre las funciones * recursivas * y las * recursivas *. La información recursiva es cuando una estructura de datos se refiere concretamente a sus propios constructores, como ocurre cuando dices 'xs = 1: 2: 3: xs': los contras finales se refieren a la inicial, formando un ciclo. Hay muchas maneras diferentes de lograr este tipo de recursión de datos: ver [Atar el nudo] (http://www.haskell.org/haskellwiki/Tying_the_Knot). Las funciones recursivas, por otro lado, son como 'zipWith'. Pueden o no definir estructuras de datos recursivas, también, pero en este caso, 'fib' no lo es. –
El ejemplo que ha dado es recursivo. Pero la secuencia de Fibonacci por naturaleza no tiene que ser así. Hay iterative versions of the algorithm, e incluso explicit functions.
La iteración es solo un caso especial de recursión, y la generación de una secuencia siempre será recursiva en algún sentido, por razones obviamente obvias. Sin embargo, la fórmula para calcular términos individuales de forma independiente no es recursiva (aunque utiliza funciones que probablemente se calcularán recursivamente). –
Aparte de la implementación de Haskell aquí, los Números de Fibonacci son una secuencia definida por una relación de recurrencia. En términos matemáticos, cada término se define como una función de los términos anteriores. Derrótalo con semántica matemática.
Aunque la definición estándar es la relación de recurrencia, cualquier implementación dada podría usar la forma cerrada (aunque esta no), por lo que este no sería un argumento sólido para las preguntas de implementación. –
Es recursivo. Puede saberlo porque el nombre en el LHS del = también aparece en el RHS.
Sin embargo, es no una función. Puede ver porque el tipo de fib no contiene un ->.
Ha pasado mucho tiempo desde la última vez que utilicé Haskell. ¿Usar el constructor de funciones es un requisito difícil para hacer una función? No puedo encontrar una declaración definida en el informe Haskell pero el tipo de función está definido léxicamente como 'tipo :: = tipo b [-> tipo]', es decir, el constructor de función seguido de otro tipo es opcional. Sin embargo, más adelante dice que "Un tipo de función tiene la forma' t1 -> t2' ... ". [[fuente] (http://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-620004)] –
'fib' no es la función,' zipWith' es. –
@Piet: Pero esa no era la pregunta. El OP dice específicamente "esta función de secuencia de Fibonacci", por lo que claramente no está preguntando sobre zipWith (a menos que esté diciendo que zipWith es "función de secuencia de Fibonacci"). – sepp2k
Para que esta función sea recursiva, debe ser recursiva y funcionar. Como señala sepp2k, es claramente recursivo porque el nombre fib aparece en ambos lados del =. Es decir, fib se define en términos de sí mismo.
¿Es una función? No de acuerdo a su tipo. En haskell, llamamos a una función de 0 argumentos "datos". Entonces, esta definición de fib crea una estructura de datos recursiva, pero no una función recursiva.
'fib' es una * no * una estructura de datos recursiva en este caso:" estructura de datos recursiva "significa algo completamente diferente en Haskell. 'fib' es una estructura de datos infinita, no repetitiva (y por lo tanto no recursiva) generada por una función recursiva (' zipWith'). –
Mi, qué nido de sutiles distinciones terminológicas. Que es esto"?
fib=0:1:zipWith (+) fib (tail fib)
No es una función recursiva. No es datos recursivos. Es una definición recursiva.
¿Qué se está definiendo?
fib
¿Qué tipo de cosa es fib, de acuerdo con esta definición?
[Integer]
Una lista de enteros (o tal vez una lista de cualquier elemento numérico antiguo).
¿Es fib una función? No, es una lista. ¿Está fib recursivamente definido? Sí. ¿Se definiría recursivamente fib si reemplazamos zipWith por una función no recursiva del mismo tipo (por ejemplo, \ f xs ys -> xs)? Sí, aunque sería una lista diferente definida recursivamente.
¿fib es una lista cíclica? No. ¿La "estructura de datos recursiva" significa "estructura de datos cíclica"? No según el documento de Hoare, "Estructuras de datos recursivas": http://portal.acm.org/book_gateway.cfm?id=63445&type=pdf&bookpath=%2F70000%2F63445%2Fcb-p217-hoare.pdf&coll=&dl=&CFID=15151515&CFTOKEN=6184618
En una configuración tipeada, "estructura de datos recursiva" significa no más ni menos que "habitante de un tipo definido recursivamente". De manera correspondiente, "fred" es una estructura de datos recursiva, aunque no se define recursivamente, y de hecho puede actuar sobre ella mediante funciones recursivas tales como ++.
La frase "función recursiva" significa "función definida recursivamente". La frase "valor recursivo" significa "valor definido recursivamente", como existe en idiomas no limitados: los lenguajes estrictos tienen el problema de "recursión de valor".
Y si usted piensa que es pedante, tratar de definir fib de esa manera en un total idioma programación , y descubrirá que la noción de "definición recursiva" se divide en "definición por recursión estructural" (consumo de datos en una manera que se detiene) y "definición por corecursion guardado" (produciendo datos de una manera que va), y que fib es de la última variedad. En ese contexto, la productividad de fib depende crucialmente de la pereza de zipWith. En el entorno de Haskell, por supuesto, no necesita preocuparse por nada de eso para descubrir qué tipo de definición es algo, solo para descubrir si tiene la mitad de posibilidades de funcionar realmente.
Como la mayoría de las respuestas apoyan su compañero de trabajo con respecto a la función parte de: "fib es no una función recursiva." Me gustaría profundizar en la parte recursiva que Conor McBride insinuó en su respuesta.
La definición dada por fib es no recursivo, es co-recursivo.
Co-recursión se parece mucho a la recursividad en que, como muchos carteles han señalado, el LHS de la definición también aparece en el RHS. Pero no hay un caso base. Recursion y corecursion "corren en direcciones opuestas".
La definición anterior de fib comienza desde los valores iniciales 0 y 1 y se mueve "hacia arriba" desde allí y continúa. Por otro lado una definición recursiva de, por ejemplo (un cálculo de función) el número de Fibonacci enésima
fib' 0 = 0
fib' 1 = 1
fib' n = fib' (n-1) + fib' (n-2)
camina "hacia abajo" de la serie n-ésimo hasta que llega a los casos base y no se detiene.
supongo que esto reivindica el adicto al crack en ambos puntos :-)
Para la lectura adicional consulte el artículo de Wikipedia sobre Corecursion y los enlaces allí. Si puede conseguirlo, puede interesarle el Capítulo 10 de The Haskell Road to Logic, Maths and Programming de Kees Doets y Jan van Eijck.
Aunque muchas personas en los comentarios discuten si la definición es o no una función, pero todos parecen estar de acuerdo en que es recursiva.
En cuanto al argumento de función/no función, en Haskell, desde el punto de vista del programador, ¡NO IMPORTA! Debido a que ambas funciones y estructuras de datos se evalúan de forma diferida, un valor y una función de ningún argumento que devuelva un valor son indistinguibles. Lo que tienes es una lista de enteros, evaluada de forma perezosa y recursiva. fib es simultáneamente una "lista de enteros", una "función de ningún argumento que devuelve una lista de enteros", una "lista de funciones de ningún argumento que devuelve enteros" y "una función de ningún argumento que devuelve una lista de funciones de ningún argumento" retornando enteros ".
Honestamente, no importa. El lenguaje no hace distinción entre los cuatro. La teoría de tipos no hace distinción entre los cuatro (y un sinnúmero de otros: una función de ningún argumento que devuelva ninguno de ellos es igualmente válida, ya que es una función de ningún argumento que devuelva eso, ad infinitum). Honestamente, no importa si llamas o no al fib como una "función" o no.
Pero es recursivo.
printf "¡Oh, no, una función con cero argumentos, no podemos tener eso!" o morir; –
Un 'fib' de hecho. – Ani
'zipWith' es la función recursiva, y' fib' se refiere a su resultado. No hay nada mágico o no recursivo al respecto. (Las respuestas a continuación que afirman que "no hay función" son tan confusas como su compañero de trabajo.) –