haskell - imprimir - ¿Crear una estructura de datos(no lista) a través de fromList realmente crea la lista?

string en haskell

Question

Esencialmente tengo curiosidad por el código como:

let myCollection = Data.SomeCollection.fromList [1, 2, foo]

¿En realidad está haciendo lo que parece en tiempo de ejecución y creando una lista enlazada como un paso intermedio para crear SomeCollection o si esto es solo una conveniencia sintáctica, y el compilador evita hacer una lista en el código compilado?

Disculpas si esta es una pregunta estúpida, pero he tenido la intención de averiguarlo desde que aprendí algo de Haskell.

Answer 1

Respuesta corta: Tal vez, en cierto modo, pero no realmente ...

Respuesta más larga:

Cuando dices lista enlazada estás pensando en términos imperativos. Haskell es perezoso y funcional, lo que hace que la pregunta sea difícil de responder.

[a,b,c] es una mano corta para a:(b:(c:[])) . Si evaluamos esto por completo (por ejemplo, intentamos imprimirlo), lo que termina en la memoria parece y se parece mucho a una lista enlazada en C, pero con muchos más cerebros. Pero eso no suele ser lo que sucede con una lista en un entorno funcional. La forma en que operan la mayoría de las funciones basadas en listas es haciendo algo con el encabezado de la lista y enviando la cola de la lista a otro lugar (quizás al mismo lugar). Eso significa que una lista realmente parece x:xs donde xs es solo una función que creará el resto de la lista. (un thunk en terminología de GHC)

La lista completa no se crea, luego se procesa como lo haría en un lenguaje imperativo. Se transmite a través de la función fromList una pieza a la vez.

Al menos esa es la forma en que funcionan la mayoría de fromList funciones fromList . Un fromList genérico para una colección podría verse así:

fromList    :: [a] -> Collection a
fromList    =  Data.List.foldl'' insert empty

Algunas colecciones pueden aprovechar el hecho de tener más de un elemento agregado a la vez. Esas colecciones (y no conozco ninguna, pero sé que existen) se acumularán en una lista de memoria más extensa.

Fuera de las optimizaciones del compilador, sin embargo, generalmente es el caso que

fromList [1, 2, foo]

es computacionalmente equivalente (dentro de un pequeño factor constante) de:

empty `insert` 1 `insert` 2 `insert` foo

Descargo de responsabilidad: no conozco lo interno de ninguna implementación de Haskell lo suficientemente bien como para decir con absoluta certeza cómo evalúan una lista constante en el código, pero esto no está muy lejos de la realidad. Espero la iluminación de los gurús de GHC si estoy fuera de la base.