Haskell: Listas vs Streams

Question

Me he dado cuenta streams parecen actuar como listas, excepto con la adición de tiempo constante. Por supuesto, agregar tiempo constante a las listas no es muy complicado, y DList hace exactamente eso.

Supongamos para el resto de la discusión que cualquiera de las listas tiene un apendice de tiempo constante, o que simplemente no estamos interesados ​​en ella.

Mi idea es que las listas de Haskell deberían simplemente implementarse como transmisiones. Para que esto no sea el caso, supongo que la siguiente necesitaría celebrar:

1. Hay casos en que las listas son mejores que las corrientes Y
2. Hay casos en que las corrientes son mejores que las listas.

Mi pregunta es: ¿cuáles son los ejemplos de los dos casos anteriores?

Nota: A los efectos de esta pregunta, ignore las omisiones fácilmente corregibles en las implementaciones particulares que he discutido. Estoy buscando más diferencias estructurales centrales aquí.

Otros detalles:

supongo que parte de lo que estoy haciendo aquí es decir si escribimos [1..1000000], hace un compilador de Haskell (digamos GHC) hacer:

1. Hacer una list O
2. Haga un objeto con dos entradas: 1 y 1000000 que describa completamente la lista.

Si es el caso (1), ¿por qué hacer esto, ya que crear listas intermedias parece ser una penalización de rendimiento innecesaria?

O si es el caso (2), entonces ¿por qué necesitamos flujos?

Answer 1

La ventaja de las transmisiones es que son más potentes. La interfaz:

data Stream m a = forall s . Stream (s -> m (Step s a)) s Size 

le permite hacer muchas cosas que las listas normales no pueden. Por ejemplo:

• pista el tamaño (por ejemplo, Desconocido, Max 34, Exact 12)
• realizar acciones monádicos para obtener el siguiente elemento. Las listas pueden hacer esto parcialmente con IO perezoso, pero esa técnica ha demostrado ser propensa a errores, y normalmente solo la utilizan los principiantes, o para pequeños scripts simples.

Sin embargo, tienen una gran desventaja en comparación con las listas: ¡la complejidad! Para un programador principiante, para comprender las transmisiones debe estar al tanto de los tipos existenciales y las acciones monádicas. Sería muy difícil aprender si utilizar el tipo de lista básica para aprender esos dos temas complejos.

que para comparar las listas, que tienen la interfaz:

data [] a = a : [a] | [] 

Esto es muy simple, y es algo que se puede enseñar fácilmente a un nuevo programador.

Otra ventaja de las listas es que puede emparejarlas simplemente con el patrón. Por ejemplo:

getTwo (a : b : _) = Just (a,b) 
getTwo _ = Nothing 

Esto es útil para los programadores experimentados (que todavía utilizan el patrón lista de coincidencias en muchos métodos), y para los programadores principiantes que aún no han aprendido las funciones de orden del estándar más alto que se pueden utilizar para manipular liza.

La eficiencia es también otra ventaja potencial de las listas, ya que ghc ha pasado mucho tiempo trabajando en la fusión de listas. En muchos códigos, las listas intermedias nunca se generan. Eso podría ser mucho más difícil de optimizar con transmisiones.

Así que creo que sería una mala elección intercambiar listas con Streams. La situación actual es mejor, donde puede traerlos si los necesita, pero los principiantes no se quedan con su complejidad y los usuarios expertos no tienen que perder la coincidencia de patrones.

EDIT: sobre [1..1000000]:

Esto es equivalente a enumFromTo 1 1000000, que se perezosamente evaluó, y sujeto a la fusión (lo que hace muy eficiente). Por ejemplo, sum [1..1000000] no generaría ninguna lista (y usaría memoria constante) con la optimización activada. Entonces el caso (2) es correcto, esta situación no es una ventaja para las transmisiones debido a la evaluación perezosa. Sin embargo, como se señaló anteriormente, las transmisiones tienen otras ventajas sobre las listas.

Answer 2

Cuando escribe [1..1000000], lo que realmente hace GHC es crear un objeto que contiene 1 y 1000000 que describe cómo crear la lista de interés; ese objeto se llama "thunk". La lista solo se crea según sea necesario para satisfacer escrutinios de casos; por ejemplo, puede escribir:

printList [] = putStrLn "" 
printList (x:xs) = putStrLn (show x) >> printList xs 

main = printList [1..1000000] 

que evalúa así:

main 
= { definition of main } 
printList [1..1000000] 
= { list syntax sugar } 
printList (enumFromTo 1 1000000) 
= { definition of printList } 
case enumFromTo 1 1000000 of 
    [] -> putStrLn "" 
    x:xs -> putStrLn (show x) >> printList xs 
= { we have a case, so must start evaluating enumFromTo; 
    I'm going to skip a few steps here involving unfolding 
    the definition of enumFromTo and doing some pattern 
    matching } 
case 1 : enumFromTo 2 1000000 of 
    [] -> putStrLn "" 
    x:xs -> putStrLn (show x) >> printList xs 
= { now we know which pattern to choose } 
putStrLn (show 1) >> printList (enumFromTo 2 1000000) 

Luego que iba a encontrar que 1 se imprimió a la consola, y nos gustaría empezar desde cerca de la parte superior con enumFromTo 2 1000000 en lugar de enumFromTo 1 1000000. Eventualmente, obtendría todos los números impresos y llegaría el momento de evaluar

printList (enumFromTo 1000000 1000000) 
= { definition of printList } 
case enumFromTo 1000000 1000000 of 
    [] -> putStrLn "" 
    x:xs -> putStrLn (show x) >> printList xs 
= { skipping steps again to evaluate enumFromTo } 
case [] of 
    [] -> putStrLn "" 
    x:xs -> putStrLn (show x) >> printList xs 
= { now we know which pattern to pick } 
putStrLn "" 

y la evaluación estaría terminada.

La razón por la que necesitamos transmisiones es un poco sutil. El documento original, Stream fusion: From lists to streams to nothing at all, probablemente tenga la explicación más completa. La versión corta es que cuando se tiene una tubería larga:

concatMap foo . map bar . filter pred . break isSpecial 

... no es tan obvio cómo conseguir el compilador para compilar listas de distancia todos los intermedios. Puede notar que podemos pensar que las listas tienen una especie de "estado" que se está iterando, y que cada una de estas funciones, en lugar de atravesar una lista, simplemente está cambiando la forma en que se modifica el estado en cada iteración. El tipo Stream intenta hacer esto explícito, y el resultado es la fusión de secuencias.Así es como se ve: primero convertimos todas estas funciones en versiones de flujo:

(toList . S.concatMap foo . fromList) . 
(toList . S.map bar . fromList) . 
(toList . S.filter pred . fromList) . 
(toList . S.break isSpecial . fromList) 

luego observar que siempre podemos aniquilar fromList . toList:

toList . S.concatMap foo . S.map bar . S.filter pred . S.break . fromList 

... y luego la magia sucede porque la cadena S.concatMap foo . S.map bar . S.filter pred . S.break construye un iterador explícitamente en lugar de construirlo implícitamente construyendo internamente y luego aniquilando listas reales.

Answer 3

Respuesta breve: las listas y los flujos son incomparables en potencia. Las transmisiones permiten acciones monádicas pero no permiten compartir, mientras que las listas son viceversa.

Una respuesta más larga:

1) Ver @nanothief para un contraejemplo que no puede ser implementado con listas 2) A continuación se muestra un contraejemplo que no puede ser fácilmente implementado con corrientes

El problema es que la lista de juguetes los ejemplos generalmente no usan la característica de compartir de las listas. Aquí está el código:

foo = map heavyFunction bar 
baz = take 5 foo 
quux = product foo 

Con las listas calcula la función pesada solo una vez. El código para calcular baz y quux con flujos sin cálculos adicionales de heavyFunction va a ser difícil de mantener.