La création d'une structure de données (hors liste) via fromList crée-t-elle réellement la liste?

Question

Essentiellement, je suis curieux de savoir si le code comme:

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

est en train de faire ce qu'il ressemble comme lors de l'exécution, et la création d'une liste chaînée comme une étape intermédiaire dans la création d'un SomeCollection -ou si cela est juste un commodité syntaxique, et le compilateur eschews faisant une liste dans le code compilé? Excuses si c'est une question stupide, mais je voulais savoir depuis l'apprentissage de Haskell.

Answer 1

Réponse courte: Peut-être, en quelque sorte, mais pas vraiment ...

Longer Réponse:

Lorsque vous dites liste chaînée vous pensez en termes impératifs. Haskell est paresseux et fonctionnel, ce qui rend la question difficile à répondre.

[a,b,c] est la main courte pour a:(b:(c:[])). Si nous évaluons complètement cela (par exemple, essayons de l'imprimer) ce qui finit dans la mémoire ressemble beaucoup à une liste chaînée en C, mais avec beaucoup plus de cerveaux. Mais ce n'est généralement pas ce qui arrive à une liste dans un contexte fonctionnel. La façon dont fonctionnent la plupart des fonctions basées sur les listes est de faire quelque chose avec la tête de la liste et d'envoyer la queue de la liste ailleurs (peut-être au même endroit). Cela signifie qu'une liste ressemble vraiment à x:xs où xs est juste une fonction qui va créer le reste de la liste. (thunk dans la terminologie GHC)

La liste entière n'est pas créée, puis traitée comme vous le feriez dans un langage impératif. Il est en streaming grâce à la fonction fromList une seule pièce à la fois.

Au moins, c'est ainsi que fonctionnent la plupart des fonctions fromList. Un fromList générique pour une collection pourrait ressembler à:

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

Certaines collections peuvent profiter d'avoir plus d'un élément supplémentaire à la fois. Ces collections (et je n'en connais aucune, mais je sais qu'elles existent) constitueront une liste de mémoire plus étendue.

En dehors des optimisations du compilateur, cependant, il est généralement le cas que

est équivalent informatiquement (dans un petit facteur constant) de:

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

Avertissement: Je ne connaître les internes de toutes les implémentations Haskell assez bien pour dire avec une certitude absolue comment ils évaluent une liste constante dans le code, mais ce n'est pas trop loin de la réalité. J'attends l'illumination des gourous GHC si je suis loin de la base.