opciones - imprimir en haskell

¿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. Así por ejemplo:

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

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

EDIT: ese ejemplo de poderes es realmente útil. ¿Cómo escribirías eso con notación do, sin embargo? Supongo que necesitarías usar rec.

Answer 1

Aquí hay un ejemplo real:

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 produce "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 ''longitud b'' que se devuelve al bucle y se une a ''d''.

En ''loop'', esta ''d = longitud b'' se alimenta a la ''f'' donde se usa en el cálculo en caída.

Esto es útil para trucos como construir una lista inmutable con doble enlace (que también puede ser circular). También es útil para atravesar ''b'' una vez, tanto para producir algo ''d'' analítico (como la longitud o el elemento más grande) como para construir una nueva estructura ''c'' que depende de ''d''. La pereza evita tener que atravesar ''b'' dos veces.

Answer 2

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

rec se implementa utilizando la función de loop de ArrowLoop . 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

Se puede ver: La salida simplemente se realimenta como la 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 de loop directamente. Esta función calcula todos los poderes de su argumento:

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

(También podrías escribirlo así: powers x = fix $ (x :) . map (*x) )

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

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