haskell - recursivas - recursividad de cola ejemplos

¿Bajo qué circunstancias los cálculos monádicos son recursivos a la cola?

Question

En la Recursión de Haskell Wiki en una mónada hay un ejemplo que se dice que es tail-recursive :

f 0 acc = return (reverse acc)
f n acc = do
v <- getLine
f (n-1) (v : acc)

Mientras que la notación imperativa nos lleva a creer que es recursivo, no es tan obvio (al menos para mí). Si nos deshacemos de azúcar conseguimos

f 0 acc = return (reverse acc)
f n acc = getLine >>= /v -> f (n-1) (v : acc)

y reescribir la segunda línea lleva a

f n acc = (>>=) getLine (/v -> f (n-1) (v : acc))

Entonces vemos que f ocurre dentro del segundo argumento de >>= , no en una posición recursiva de cola. Tendríamos que examinar IO ''s >>= para obtener una respuesta. Claramente, tener la llamada recursiva como la última línea en un bloque do no es una condición suficiente para que una función sea recursiva.

Digamos que una mónada es recursiva por la cola si cada función recursiva en esta mónada se define como

f = do
...
f ...

o equivalente

f ... = (...) >>= /x -> f ...

Es la cola recursiva. Mi pregunta es:

1. ¿Qué mónadas son de cola recursiva?
2. ¿Hay alguna regla general que podamos usar para distinguir de inmediato las mónadas recursivas de la cola?

Actualización: Permítame hacer un contraejemplo específico: la mónada [] no es recursiva de acuerdo con la definición anterior. Si lo fuera, entonces

f 0 acc = acc
f n acc = do
r <- acc
f (n - 1) (map (r +) acc)

Tendría que ser la cola recursiva. Sin embargo, desugaring la segunda línea conduce a

f n acc = acc >>= /r -> f (n - 1) (map (r +) acc)
= (flip concatMap) acc (/r -> f (n - 1) (map (r +) acc))

Claramente, esto no es una cola recursiva, y no se puede hacer el IMHO. La razón es que la llamada recursiva no es el final del cálculo. Se realiza varias veces y los resultados se combinan para obtener el resultado final.

Answer 1

Lo que realmente importa es el espacio de pila constante. Su primer ejemplo es la cola recursiva modulo contras , gracias a la pereza.

Se (getLine >>=) y se evaporará, dejándonos nuevamente con la llamada a f . Lo que importa es que esto sucede en una cantidad constante de pasos: no hay acumulación de procesador.

Tu segundo ejemplo,

f 0 acc = acc
f n acc = concat [ f (n - 1) $ map (r +) acc | r <- acc]

será solo lineal (en n ) en su acumulación de procesador, ya que se accede a la lista de resultados desde la izquierda (nuevamente debido a la pereza, ya que concat no es estricto). Si se consume en la cabecera, se puede ejecutar en el espacio O (1) (sin contar el espacio lineal thunk, f(0), f(1), ..., f(n-1) en el borde izquierdo).

Mucho peor seria

f n acc = concat [ f (n-1) $ map (r +) $ f (n-1) acc | r <- acc]

o en do notation,

f n acc = do
r <- acc
f (n-1) $ map (r+) $ f (n-1) acc

Porque hay forzamiento adicional debido a la dependencia de la información. Del mismo modo, si el enlace para una mónada dada fuera una operación estricta.

Answer 2

Una computación monádica que se refiere a sí misma nunca es recursiva. Sin embargo, en Haskell tienes pereza y corecursión, y eso es lo que cuenta. Usemos este sencillo ejemplo:

forever :: (Monad m) => m a -> m b
forever c'' = let c = c'' >> c in c

Tal cálculo se ejecuta en un espacio constante si y solo si (>>) es estricto en su segundo argumento. Esto es realmente muy similar a las listas y repeat :

repeat :: a -> [a]
repeat x = let xs = x : xs in xs

Como el constructor (:) es no estricto en su segundo argumento, esto funciona y la lista se puede recorrer, porque tiene una forma normal finita de cabeza débil (WHNF). Siempre que el consumidor (por ejemplo, un pliegue de la lista) solo solicite el WHNF, esto funciona y se ejecuta en un espacio constante.

El consumidor en el caso de forever es lo que interpreta la computación monádica. Si la mónada es [] , entonces (>>) no es estricto en su segundo argumento, cuando su primer argumento es la lista vacía. Entonces forever [] resultará en [] , mientras que forever [1] divergirá. En el caso de la mónada IO el intérprete es el mismo sistema de tiempo de ejecución, y allí se puede pensar que (>>) siempre es no estricto en su segundo argumento.