¿Cómo funciona la palabra clave haskell rec?

Question

En la notación de flecha, puede usar la palabra clave rec para escribir definiciones recursivas. Entonces, por ejemplo:

rec 
    name <- function -< input 
    input <- otherFunction -< name 

¿Cómo puede esto alguna vez evaluar? Parece que simplemente entraría en un ciclo infinito o algo así. Sé que evalúa el combinador de flecha de bucle, pero no entiendo cómo funciona eso tampoco.

EDITAR: ese ejemplo de poderes es realmente útil. Sin embargo, ¿cómo escribirías eso con la notación de hacer? Supongo que necesitarías usar rec.

Answer 1

Este poco de magia funciona debido a la pereza de Haskell. Como sabrá, Haskell evalúa un valor cuando es necesario, no cuando está definido. Por lo tanto, esto funciona si no necesita el valor ingresado directamente, o tal vez más tarde.

rec se implementa utilizando la función loop de . Se define como sigue:

class Arrow a => ArrowLoop a where 
     loop :: a (b,d) (c,d) -> a b c 

instance ArrowLoop (->) where 
     loop f b = let (c,d) = f (b,d) in c 

Puede ver: La salida simplemente se retroalimenta como entrada. Se calculará solo una vez, porque Haskell solo evaluará d cuando sea necesario.

Aquí hay un ejemplo real de cómo usar el combinador loop directamente. Esta función calcula todos los poderes de que el argumento de:

powers = loop $ \(x,l) -> (l,x:map(*x)l) 

(También podrían escribir como este en su lugar: powers x = fix $ (x :) . map (*x))

¿Cómo funciona? Bueno, la lista infinita de poderes está en el argumento l. La evaluación es el siguiente:

powers = loop $ \(x,l) -> (l,x:map(*x)l) ==> 
powers b = let (c,d) = (\(x,l) -> (l,x:map(*x)l)) (b,d) in c ==> 
powers b = let (c,d) = (d,b:map(*b)d) in d ==> -- Now we apply 2 as an argument 
powers 2 = let (c,d) = (d,2:map(*2)d) in d ==> 
     = let (c,(2:d)) = (d,2:map(*2)d) in c ==> 
     = let (c,(2:4:d)) = ((2:d),2:map(*2)(2:d)) in c ==> 
     = let (c,(2:4:8:d)) = ((2:4:d),2:map(*2)(2:4:d)) in ==> -- and so on 

Answer 2

Aquí es un ejemplo real ish:

loop f b = let (c,d) = f (b,d) in c 

f (b,d) = (drop (d-2) b, length b) 

main = print (loop f "Hello World") 

Este programa salidas "LD". La función 'loop f' toma una entrada 'b' y crea una salida 'c'. Lo que 'f' está haciendo es estudiar 'b' para producir 'length b' que se devuelve al loop y se enlaza con 'd'.

En 'loop', esta 'd = longitud b' se introduce en la 'f' donde se usa en el cálculo en drop.

Esto es útil para trucos como la construcción de una lista inmutable doblemente vinculada (que también puede ser circular). También es útil para atravesar 'b' una vez para producir alguna 'd' analítica (como la longitud o el elemento más grande) y para construir una nueva estructura 'c' que dependa de 'd'. La pereza evita tener que atravesar 'b' dos veces.