Czy ghc przekształca listę używaną tylko raz w generator ze względu na wydajność?

Question

Jeśli tak, czy jest to część standardowej lub specjalnej optymalizacji ghc, na której możemy polegać? Lub po prostu optymalizacja, na którą nie zawsze możemy polegać.

P.S .: Kiedy próbowałem próbki do badań, wydawało się wskazywać, że było to miejsce/

Prelude> let isOdd x = x `mod` 2 == 1 
Prelude> let isEven x = x `mod` 2 == 0 
Prelude> ((filter isOdd).(filter isEven)) [1..] 

Chews górę CPU ale nie zużywa dużo pamięci.

Answer 1

Zależy od tego, co rozumiemy przez generator. Lista jest generowana leniwie, a ponieważ nic innego nie wskazuje na to, zużyte części są prawie natychmiast zbierane. Ponieważ wynik powyższego obliczenia nie wzrasta, całe obliczenie przebiega w stałej przestrzeni. Nie jest to wymagane przez normę, ale ponieważ trudniej jest zaimplementować nieistotną semantykę o różnych zachowaniach przestrzennych dla tego przykładu (i wiele niejasno podobnych), w praktyce można na niej polegać.

Ale zwykle lista jest nadal generowana jako lista, więc powstało dużo śmieci. W sprzyjających warunkach ghc eliminuje listę [1 .. ] i tworzy pętlę dla realokacji:

result :: [Int] 
result = filter odd . filter even $ [1 .. ] 

(z wykorzystaniem funkcji Prelude OUT lenistwo), utworzonych z -O2 generuje rdzeń

List.result_go = 
    \ (x_ayH :: GHC.Prim.Int#) -> 
    case GHC.Prim.remInt# x_ayH 2 of _ { 
     __DEFAULT -> 
     case x_ayH of wild_Xa { 
      __DEFAULT -> List.result_go (GHC.Prim.+# wild_Xa 1); 
      9223372036854775807 -> GHC.Types.[] @ GHC.Types.Int 
     }; 
     0 -> 
     case x_ayH of wild_Xa { 
      __DEFAULT -> List.result_go (GHC.Prim.+# wild_Xa 1); 
      9223372036854775807 -> GHC.Types.[] @ GHC.Types.Int 
     } 
    } 

zwykły pętli , działa od 1 do maxBound :: Int, nie produkując niczego po drodze i [] na końcu. Jest prawie na tyle sprytny, aby powrócić do zwykłego powrotu: []. Zauważ, że istnieje tylko jeden podział o 2, GHC wie, że jeśli Int jest równy, nie może być nieparzysty, więc kontrola została wyeliminowana, aw żadnym oddziale nie jest tworzona niepusta lista (tj. Nieosiągalne gałęzie mają zostały usunięte przez kompilator).

Answer 2

Ściśle mówiąc, Haskell nie określa żadnego konkretnego modelu oceny, więc implementacje mogą dowolnie implementować semantykę języka, tak jak chcą. Jednak w każdym rozsądnym wykonaniu, w tym GHC, możesz polegać na tym działaniu w stałej przestrzeni.

W GHC obliczenia takie jak te prowadzą do pojedynczo połączonej listy kończącej się odskokiem reprezentującym pozostałą część listy, która nie została jeszcze oceniona. Podczas oceny tej listy więcej list będzie generowanych na żądanie, ale od początku listy nie jest nigdzie indziej, wcześniejsze części są natychmiast kwalifikujące się do zbierania śmieci, więc otrzymujesz stałe zachowanie przestrzeni.

Po włączeniu optymalizacji GHC najprawdopodobniej przeprowadzi wylesianie w tym miejscu, optymalizując potrzebę posiadania listy, a wynikiem będzie prosta pętla bez przeprowadzonej alokacji.