Czy tworzenie (nie-listowej) struktury danych za pośrednictwem fromList faktycznie tworzy listę?

Question

Zasadniczo jestem ciekawy, czy kod jak:

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

faktycznie robi to, co wygląda jak w czasie wykonywania i tworzenia połączonej listy jako etap pośredni w tworzeniu SomeCollection -lub jeśli jest to tylko wygoda składniowa i kompilator unika tworzenia listy w skompilowanym kodzie?

Przepraszam, jeśli to głupie pytanie, ale od czasu do czasu dowiedziałem się czegoś o Haskellowi.

Answer 1

Krótka odpowiedź: Być może, w pewnym sensie, ale nie bardzo ...

Dłuższe Odpowiedź:

Kiedy mówisz listy myślisz w kategoriach nadrzędnych powiązane. Haskell jest leniwy i funkcjonalny, co sprawia, że ​​trudno jest odpowiedzieć na to pytanie.

[a,b,c] jest krótką ręką dla a:(b:(c:[])). Jeśli w pełni to oceniamy (na przykład spróbujmy go wydrukować), to co kończy się w pamięci wygląda i działa podobnie jak lista połączona w C, ale o wiele więcej mózgów. Ale to nie jest zwykle to, co dzieje się z listą w ustawieniu funkcjonalnym. Funkcjonalność większości funkcji opartych na listach polega na tym, że robimy coś z szefem listy i wysyłamy ogon listy w inne miejsce (być może w to samo miejsce). Oznacza to, że lista naprawdę wygląda x:xs gdzie xs to tylko niektóre funkcje, które utworzą resztę listy. (thunk w terminologii GHC)

Cała lista nie jest tworzona, a następnie przetwarzana tak, jak w imperatywnym języku. Jest on przesłany za pomocą funkcji poprzez jedną część na raz.

Przynajmniej tak działają większość funkcji fromList. Ogólny fromList dla kolekcji może wyglądać tak:

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

Niektóre zbiory mogą skorzystać z posiadania więcej niż jednego elementu dodanego naraz. Te kolekcje (i nie znam żadnych, ale wiem, że istnieją) zbudują obszerniejszą listę pamięci.

Poza optymalizacje kompilatora, jednak jest to na ogół tak, że

jest obliczeniowo równoważne (w maleńkim stały współczynnik) od:

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

Zastrzeżenie: ja nie znać wewnętrzne elementy każdej implementacji Haskella na tyle dobrze, by z absolutną pewnością powiedzieć, jak oceniają stałą listy w kodzie, ale nie jest to zbyt daleko od rzeczywistości. Oczekuję oświecenia od guru GHC, jeśli znajdę się poza bazą.