Riffując doskonałą odpowiedź jbapple na temat replicate, ale zamiast tego używając replicateA(który replicatejest wbudowany), wymyśliłem:
--Unlike fromList, one needs the length explicitly.
myFromList :: Int -> [b] -> Seq b
myFromList l xs = flip evalState xs $ Seq.replicateA l go
where go = do
(y:ys) <- get
put ys
return y
myFromList(w nieco bardziej wydajnej wersji) jest już zdefiniowany i stosowany wewnętrznie w Data.Sequencekonstruowania drzewa palców, które są wyniki rodzaju.
Ogólnie intuicja dotycząca replicateAjest prosta. replicateAjest zbudowany na funkcji aplikacji drzewko aplikacyjne . applicativeTreebierze kawałek drzewa wielkości mi tworzy dobrze zrównoważone drzewo zawierające jego nkopie. Obudowy dla nmaksymalnie 8 (jednego Deeppalca) są na stałe zakodowane. Wszystko powyżej tego, a rekursywnie się przywołuje. Element „aplikacyjny” polega po prostu na tym, że przeplata on konstrukcję drzewa z efektami gwintowania, takimi jak w przypadku powyższego kodu, stan.
goFunkcji, które są replikowane, jest po prostu działaniem, które dostaje aktualny stan, element pojawia się na górze, a zastępuje resztę. Przy każdym wywołaniu przesuwa się ona w dół listy podanej jako dane wejściowe.
Kilka bardziej konkretnych notatek
main = print (length (show (Seq.fromList [1..10000000::Int])))
W niektórych prostych testach przyniosło to interesujący kompromis w zakresie wydajności. Główna funkcja powyżej działała prawie o 1/3 niżej z myFromList niż z fromList. Z drugiej strony myFromListużywano stałej sterty 2 MB, podczas gdy standard fromListzużywał do 926 MB. To 926 MB wynika z konieczności jednoczesnego przechowywania całej listy w pamięci. Tymczasem rozwiązanie myFromListjest w stanie leniwie korzystać ze struktury. Problem prędkości wynika z faktu, że myFromListmusi wykonać około dwa razy więcej przydziałów (w wyniku budowy pary / zniszczenia monady państwowej) niżfromList. Możemy wyeliminować te przydziały, przechodząc do monady stanu przekształconej przez CPS, ale skutkuje to utrzymaniem o wiele większej pamięci w danym momencie, ponieważ utrata lenistwa wymaga przemierzania listy w sposób nieprzesyłający.
Z drugiej strony, zamiast wymuszać całą sekwencję pokazu, przechodzę do wyodrębnienia głowy lub ostatniego elementu, myFromListnatychmiast przynosi większą wygraną - wyodrębnienie elementu głowy jest niemal natychmiastowe, a wyodrębnienie ostatniego elementu wynosi 0,8 s . Tymczasem przy standardzie fromListwyjęcie głowy lub ostatniego elementu kosztuje ~ 2,3 sekundy.
To są wszystkie szczegóły i są konsekwencją czystości i lenistwa. W sytuacji mutacji i losowego dostępu wyobrażam sobie, że replicaterozwiązanie jest zdecydowanie lepsze.
Rodzi to jednak pytanie, czy istnieje sposób na przepisanie applicativeTree, który myFromListjest zdecydowanie bardziej wydajny. Wydaje mi się, że problem polega na tym, że działania aplikacyjne są wykonywane w innej kolejności niż drzewo jest naturalnie przechodzone, ale nie w pełni pracowałem nad tym, jak to działa lub czy istnieje sposób, aby to rozwiązać.