¿Cómo es que en la línea de abajo en el lado derecho de la ecuación se podría utilizar 'mentiras' símbolo aunque aún no esta definied:el empleo del símbolo antes de que se definied
let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
El punto es que la definición de fibs
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
no se evalúa hasta que se utiliza en otro lugar. Luego la definición se desarrolla usando la parte ya conocida. Comenzamos con fibs = 0 : 1 : ???. Entonces, si el tercer elemento es siempre necesaria, la definición se evalúa un paso más allá,
fibs = 0 : 1 : zipWith (+) (0 : 1 : ???) (tail (0 : 1 : ???))
= 0 : 1 : zipWith (+) (0 : 1 : ???) (1 : ???)
= 0 : 1 : (0 + 1) : zipWith (+) (1 : ???) (???)
pero luego la parte desconocida ??? se ha convertido en parte conocido, se ha determinado que es ??? = 1 : ????, por lo que el despliegue puede seguir adelante,
= 0 : 1 : 1 : zipWith (+) (1 : 1 : ????) (1 : ????)
= 0 : 1 : 1 : 2 : zipWith (+) (1 : ????) (????)
-- now ???? is known to be 2:?????
= 0 : 1 : 1 : 2 : zipWith (+) (1 : 2 : ?????) (2 : ?????)
etc.
Gracias, a primera vista, parece más complicado que la recursión de funciones. ¿Hay algunas restricciones en la sintaxis que computa listas/valores recursivamente? En otras palabras, pero no precedentemente, ¿qué es la sintaxis permitida? – Trismegistos
No hay restricciones sintácticas, solo usa el valor que se define en la expresión que se define como 'valor = alguna expresión usando valor'. El punto a tener en cuenta es si el cálculo termina. Podría, por ejemplo, intentar definir 'ciclo xs = dejar resultado = resultado ++ xs en resultado'. Pero si intentas evaluarlo, primero debes averiguar si 'result' es no vacío, para saber qué ecuación usar para' (++) '. Entonces mira la definición de 'resultado',' resultado = resultado ++ xs', por lo que para saber si 'resultado' es no vacío, debe averiguar si' resultado' es no vacío ... –
Pero si lo definió 'cycle xs = let result = xs ++ result in result', ya sabes lo suficiente de' result' para no atascarse cuando surge la necesidad de inspeccionar 'result' en el cálculo de' result' (a menos que 'xs' esté vacío , eso te pondría en la situación 'let x = x in x'). Entonces, una definición de autorreferencia requiere que se pueda determinar una parte del 'valor 'antes de inspeccionarlo en la expresión de definición, y la siguiente parte necesaria siempre se puede determinar usando lo que ya se conoce. –
No va a tratar de realidad llame al fibs en su definición hasta que algo más use fibs más adelante en su programa, en cuyo punto fibs ha sido completamente definido.
Usted puede hacer esto en la mayoría de otros idiomas también:
int foo(int x)
{
if (x <= 0) return 0;
// will call foo when it gets there, at which point its been defined
foo(x - 1);
}
Entiendo recurence en idiomas imperativos y también en haskell cuando está dividido en pocas líneas. por ejemplo fib 0 = 0; fib 1 = 1; fib n = fib (n - 1) + fib (n - 2). No entiendo cómo se usa en el ejemplo que he dado en la pregunta principal. – Trismegistos
@Trismegistos: es exactamente lo mismo, Haskell no necesita ejecutar esta función hasta que se llame. Cuando llamas 'fibs' a otro lugar, y dentro de esa llamada alcanza' fibs', simplemente vuelve a registrar el proceso. Haskell no necesita llamarlo ni nada mientras se está definiendo/analizando. – GManNickG
Todos los enlaces de Haskell son recursivos. Esto es diferente a la mayoría de los idiomas, pero a menudo funciona correctamente debido a la pereza (la evaluación de Haskell no es estricta, a diferencia de la mayoría de los idiomas populares). Novatos se disparan a menudo hasta cuando intentan algo como:
main = do
let a = 3
let a = 3 + a
print a
Debido a que la segunda unión a a realidad ignora y sombras la primera, y define a en términos de sí mismo, lo que provoca un bucle infinito cuando intenta imprimir el resultado de 3 + 3 + 3 + 3 + ...
un ejemplo más sencillo de una lista infinita es ones: una lista infinita de 1 s
ones = 1 : ones
En este caso, los simplemente se refiere a sí mismo
_______
| |
v |
________ |
| ones | |
| 1 : ---|
--------
En Haskell, puede crear un árbol infinito de la misma manera que se puede crear una lista infinita:
data Tree a = Stub | Branch a (Tree a) (Tree a)
onesTree = Branch 1 onesTree onesTree
______ _______
| | | |
| v v |
| ____________ |
| | onesTree | |
|--- | 1 | ----|
------------
creo que el la pregunta real es: ¿por qué otros idiomas no admiten los valores recursivos tan convenientemente como Haskell?
Bueno, para entender esto, es bueno entender cómo se implementa la evaluación perezosa. Básicamente, las expresiones no evaluadas están representadas por thunks: una estructura de datos que representa toda la información necesaria para calcular el valor cuando realmente se necesita.Cuando sucede esto último (o como decimos, cuando el thunk es forzado), se ejecuta el código para calcular el valor y el contenido del thunk se reemplaza por el resultado, que puede tener punteros a otros thunk.
Entonces fibs comienza como un thunk. Este procesador contiene punteros al código que se usa para calcular su valor, y apunta a los procesos que este código toma como argumentos. Uno de estos últimos punteros es un puntero al propio fibs.
@NiklasB. Sé lo que es recursividad, pero no entiendo este trazador de líneas específico. Ver mi comentario bajo la respuesta de GManNickG. – Trismegistos
@NiklasB. Sin embargo, la mayoría de los lenguajes te hacen saltar un par de aros para usar un _valor_ en su propia definición. Pocos tienen pereza integrada. –
@Daniel: Sí, es cierto, la mayoría de los idiomas solo admiten recursividad para funciones, no para listas. –