Haskell: Listy kontra strumienie

Question

Zauważyłem, że streams wydaje się działać bardzo podobnie do list, z wyjątkiem ciągłego dodawania czasu. Oczywiście dodawanie ciągłego dodawania czasu do list nie jest zbyt skomplikowane, a właśnie to robi DList.

Załóżmy, że do końca dyskusji, że obie listy mają stały czas dołączenia lub że po prostu nie jesteśmy nimi zainteresowani.

Uważam, że listy Haskella powinny być po prostu implementowane jako strumienie. Na to nie być przypadek, zakładam, że następująca musiałby posiadać:

1. Istnieją przypadki, w których listy są lepsze niż strumieni I
2. Istnieją przypadki, gdzie strumienie są lepsze niż list.

Moje pytanie brzmi: jakie są przykłady dwóch powyższych przypadków?

Uwaga: Dla celów tego pytania, proszę zignorować łatwe do naprawienia pominięcia w konkretnych implementacjach, które omówiłem. W tym miejscu szukam podstawowych różnic strukturalnych.

Dodatkowe informacje:

Chyba część tego, co mi chodzi tutaj jest powiedzieć, czy piszemy [1..1000000], czy kompilator Haskell (powiedzmy GHC) zrobić:

1. dokonać lista LUB
2. Utwórz obiekt z dwoma wzorcami: 1 i 1000000, który w pełni opisuje listę.

Jeśli to sprawa (1), dlaczego tak jest, ponieważ tworzenie list pośrednich wydaje się być niepotrzebną karą za wyniki?

A jeśli to sprawa (2), to dlaczego potrzebujemy strumieni?

Answer 1

Zaletą strumieni jest ich większa moc. Interfejs:

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

pozwala robić wiele rzeczy, których normalne listy nie mogą. Np:

• Tor wielkość (np nieznane, Max 34, Exact 12)
• Wykonaj czynności monadycznego dostać następny element. Listy mogą częściowo to zrobić z leniwym IO, ale technika ta okazała się podatna na błędy i zwykle jest używana tylko przez początkujących lub proste małe skrypty.

Jednak mają one duży minus w porównaniu do list - złożoność! Dla początkujących programistów, aby zrozumieć strumienie, musisz być na szczycie typów egzystencjalnych i monadycznych działań. Byłoby bardzo trudno nauczyć się haskell, jeśli chcesz użyć podstawowego typu listy, musisz nauczyć się tych dwóch złożonych tematów.

Porównaj to do list, które mają interfejs:

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

To jest bardzo proste, a coś, co można łatwo nauczył się nowego programatora.

Kolejną zaletą list jest to, że można je łatwo dopasować do siebie. Na przykład:

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

Jest to zarówno użyteczny do doświadczonych programistów (I nadal korzystać z listy wzór pasujący na wiele sposobów), oraz dla początkujących programistów, którzy jeszcze nie nauczyli średnia funkcja wyższego rzędu, które mogą być używane do manipulowania listy.

Efektywność to kolejna potencjalna zaleta list, ponieważ ghc spędził dużo czasu pracując nad listą połączeń. W wielu kodach listy pośrednie nigdy nie są generowane. To może być o wiele trudniejsze do zoptymalizowania ze strumieniami.

Sądzę, że wybór opcji strumieniami byłby złym wyborem. Obecna sytuacja jest lepsza, gdy można ją wprowadzić, jeśli jej potrzebujesz, ale początkujący nie są skazani na złożoność, a wykwalifikowani użytkownicy nie muszą tracić dopasowania do wzorca.

Edycja: około [1..1000000]:

Odpowiada to enumFromTo 1 1000000, który leniwie oceniane, i pod warunkiem topnienia (co pozwala na bardzo wydajne). Np. sum [1..1000000] nie generuje żadnych list (i używa stałej pamięci) z włączoną optymalizacją. A więc przypadek (2) jest poprawny, sytuacja ta nie jest korzystna dla strumieni ze względu na leniwą ocenę. Jak zauważono powyżej, strumienie mają jednak inne zalety niż listy.

Answer 2

Podczas pisania [1..1000000], GHC naprawdę robi obiekt zawierający 1 i 1000000, który opisuje, w jaki sposób zbudować listę zainteresowania; ten obiekt nazywa się "thunk". Lista jest tworzona tylko w razie potrzeby, aby spełnić wymagania kontrolerów sprawy; Na przykład, można napisać:

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

main = printList [1..1000000] 

która ocenia tak:

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) 

Wtedy okaże się, że 1 został wydrukowany do konsoli, a chcielibyśmy zacząć od blisko szczytu z enumFromTo 2 1000000 zamiast enumFromTo 1 1000000. W końcu wszystkie numery zostaną wydrukowane, a nadejdzie czas na oszacowanie wartości i ocena będzie zakończona.

Powód, dla którego potrzebujemy strumieni, jest nieco subtelny. Oryginalny dokument, Stream fusion: From lists to streams to nothing at all, prawdopodobnie zawiera najbardziej kompletne wyjaśnienie. Krótka wersja jest taka, że ​​gdy masz długi rurociąg:

concatMap foo . map bar . filter pred . break isSpecial 

... to nie jest tak oczywiste, jak dostać kompilator do kompilacji z dala wszystkich list pośrednich. Można zauważyć, że możemy myśleć o listach jako o "stanie", który jest iterowany, i że każda z tych funkcji, zamiast przechodzić przez listę, zmienia tylko sposób, w jaki stan jest modyfikowany w każdej iteracji. Typ Stream próbuje uczynić to wyraźnym, a wynikiem jest fuzja strumieniowa.Oto jak to wygląda: najpierw przekonwertować wszystkie te funkcje w wersji strumieniowe:

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

następnie zauważyć, że zawsze możemy unicestwić fromList . toList:

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

... a potem dzieje się magia ponieważ łańcucha S.concatMap foo . S.map bar . S.filter pred . S.break tworzy iterator jawnie, zamiast budować go niejawnie, wewnętrznie budując, a następnie natychmiastowo niszcząc rzeczywiste listy.

Answer 3

Krótka odpowiedź: listy i strumienie są nieporównywalne pod względem mocy. Strumienie zezwalają na monadyczne akcje, ale nie zezwalają na udostępnianie, podczas gdy listy są odwrotnie.

Dłuższa odpowiedź:

1) Zobacz @nanothief na kontrprzykład, które nie mogą być realizowane z list 2) Poniżej jest kontrprzykład, które nie mogą być łatwo realizowane ze strumieniami

Problemem jest to, że lista zabawka przykłady zazwyczaj nie korzystają z funkcji udostępniania list. Oto kod:

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

Z listami obliczasz ciężką funkcję tylko raz. Kod do obliczenia baz i quux strumieniami bez dodatkowych obliczeń będzie trudny do utrzymania.