Próbuję i nie udaje mi się zrozumieć traverse
funkcji z Data.Traversable
. Nie widzę sensu. Ponieważ pochodzę z imperatywnego środowiska, czy ktoś mógłby mi to wyjaśnić za pomocą imperatywnej pętli? Pseudokod byłby bardzo mile widziany. Dzięki.
99
Odpowiedzi:
traverse
jest taki sam, jakfmap
, z wyjątkiem tego, że umożliwia również uruchamianie efektów podczas odbudowywania struktury danych.Spójrz na przykład z
Data.Traversable
dokumentacji.Functor
InstancjaTree
będzie:Odbudowuje całe drzewo, stosując się
f
do każdej wartości.Traversable
Instancja jest prawie taka sama, z wyjątkiem konstruktorzy są nazywane w aplikacyjnej stylu. Oznacza to, że przy odbudowie drzewa możemy mieć (uboczne) efekty. Applicative jest prawie taki sam jak monady, z tym wyjątkiem, że efekty nie mogą zależeć od poprzednich wyników. W tym przykładzie oznacza to, że nie można było zrobić czegoś innego z prawą gałęzią węzła w zależności od wyników przebudowy na przykład lewej gałęzi.Ze względów historycznych
Traversable
klasa zawiera również monadyczną wersjętraverse
tzwmapM
. Pod każdym względemmapM
jest to samo cotraverse
- istnieje jako odrębna metoda, boApplicative
dopiero później stała się nadklasąMonad
.Jeśli zaimplementowałbyś to w nieczystym języku,
fmap
byłoby to samo cotraverse
, ponieważ nie ma sposobu, aby zapobiec efektom ubocznym. Nie możesz zaimplementować go jako pętli, ponieważ musisz rekurencyjnie przechodzić przez strukturę danych. Oto mały przykład, jak zrobiłbym to w JavaScript:Implementacja tego w ten sposób ogranicza cię do efektów, na które pozwala język. Jeśli wolisz niedeterminizm (który jest listą instancji modeli aplikacyjnych), a Twój język nie ma go wbudowanego, nie masz szczęścia.
źródło
Functor
części, która nie jest parametryczna. Wartość stanu wState
, awariaMaybe
iEither
, liczba elementów w[]
i oczywiście dowolne zewnętrzne skutki uboczne wIO
. Nie obchodzi mnie to jako termin ogólny (podobnie jakMonoid
funkcje używające „pustego” i „dołączania”, koncepcja jest bardziej ogólna, niż sugeruje termin na początku), ale jest dość powszechna i wystarczająco dobrze służy celowi.ap
poprzednich wyników. Odpowiednio przeredagowałem tę uwagę.traverse
zamienia rzeczy wewnątrz aTraversable
wTraversable
rzeczy „wewnątrz” anApplicative
, biorąc pod uwagę funkcję, która tworzyApplicative
s z rzeczy.Użyjmy
Maybe
jakoApplicative
i wypiszmy jakoTraversable
. Najpierw potrzebujemy funkcji transformacji:Więc jeśli liczba jest parzysta, otrzymujemy jej połowę (wewnątrz a
Just
), w przeciwnym razie otrzymamyNothing
. Jeśli wszystko idzie „dobrze”, wygląda to tak:Ale...
Powodem jest to, że
<*>
funkcja jest używana do budowania wyniku, a gdy jeden z argumentów jestNothing
, otrzymujemy zNothing
powrotem.Inny przykład:
Ta funkcja generuje listę długości
x
z zawartościąx
, np .rep 3
=[3,3,3]
. Jaki jest skutektraverse rep [1..3]
?Otrzymujemy częściowe rezultaty
[1]
,[2,2]
a[3,3,3]
przy użyciurep
. Teraz semantyka list typuApplicatives
„weź wszystkie kombinacje”, np .(+) <$> [10,20] <*> [3,4]
Jest[13,14,23,24]
.„Wszystkie kombinacje”
[1]
i[2,2]
są dwa razy[1,2]
. Wszystkie kombinacje dwa razy[1,2]
i[3,3,3]
sześć razy[1,2,3]
. Więc mamy:źródło
fac n = length $ traverse rep [1..n]
liftA2 (,)
niż bardziej ogólny formularztraverse
.Myślę, że najłatwiej jest to zrozumieć w kategoriach
sequenceA
, cotraverse
można zdefiniować następująco.sequenceA
sekwencjonuje razem elementy struktury od lewej do prawej, zwracając strukturę o tym samym kształcie zawierającą wyniki.Możesz również pomyśleć o
sequenceA
odwróceniu kolejności dwóch funktorów, np. Przejściu z listy akcji do akcji zwracającej listę wyników.Tak więc
traverse
przyjmuje pewną strukturę i stosuje sięf
do przekształcenia każdego elementu w strukturze w jakąś aplikację, a następnie sekwencjonuje efekty tych aplikacji od lewej do prawej, zwracając strukturę o tym samym kształcie zawierającą wyniki.Możesz również porównać to z
Foldable
, które definiuje powiązaną funkcjętraverse_
.Widać więc, że kluczowa różnica między
Foldable
iTraversable
polega na tym, że ta ostatnia pozwala zachować kształt konstrukcji, podczas gdy pierwsza wymaga złożenia wyniku w inną wartość.Prostym przykładem jego użycia jest użycie listy jako przejezdnej struktury i
IO
aplikacji:Chociaż ten przykład jest raczej mało ekscytujący, rzeczy stają się bardziej interesujące, gdy
traverse
jest używany na innych typach pojemników lub przy użyciu innych aplikacji.źródło
sequenceA . fmap
ponieważ listy jest równoważne,sequence . map
prawda?IO
Typ może być użyty do wyrażenia efektów ubocznych; (2)IO
jest monadą, co okazuje się bardzo wygodne. Monady nie są zasadniczo powiązane z efektami ubocznymi. Należy również zauważyć, że istnieje znaczenie „skutku”, które jest szersze niż „efekt uboczny” w jego zwykłym znaczeniu - obejmującym czyste obliczenia. W tym ostatnim punkcie zobacz także Co dokładnie oznacza „skuteczny” .To trochę tak
fmap
, z wyjątkiem tego, że możesz uruchamiać efekty wewnątrz funkcji mapper, która również zmienia typ wyniku.Wyobraźmy sobie listę liczb całkowitych reprezentujących identyfikatory użytkowników w bazie danych:
[1, 2, 3]
. Jeśli chcesz, abyfmap
te identyfikatory użytkowników były nazwami użytkowników, nie możesz użyć tradycyjnegofmap
, ponieważ wewnątrz funkcji musisz uzyskać dostęp do bazy danych, aby odczytać nazwy użytkowników (co wymaga efektu - w tym przypadku za pomocąIO
monady).Podpis
traverse
:Dzięki
traverse
, możesz robić efekty, dlatego twój kod do mapowania identyfikatorów użytkowników na nazwy użytkowników wygląda następująco:Jest też funkcja o nazwie
mapM
:Każde użycie
mapM
może zostać zastąpionetraverse
, ale nie odwrotnie.mapM
działa tylko dla monad, podczas gdytraverse
jest bardziej ogólny.Jeśli chcesz tylko uzyskać efekt i nie zwracać żadnej użytecznej wartości, istnieją
traverse_
imapM_
wersje tych funkcji, z których obie ignorują wartość zwracaną przez funkcję i są nieco szybsze.źródło
traverse
jest pętlą. Jego implementacja zależy od struktury danych, przez którą przechodzimy. To może być lista, drzewoMaybe
,Seq
(uence), lub cokolwiek, co ma ogólny sposób przejeżdżającego przez coś jak dla pętli lub funkcji rekurencyjnej. Tablica zawierałaby pętlę for, listę pętlę while, drzewo albo coś rekurencyjnego, albo połączenie stosu z pętlą while; ale w językach funkcyjnych nie potrzebujesz tych uciążliwych poleceń pętli: łączysz wewnętrzną część pętli (w kształcie funkcji) ze strukturą danych w sposób bardziej bezpośredni i mniej rozwlekły.Dzięki
Traversable
typeklasie prawdopodobnie mógłbyś napisać swoje algorytmy bardziej niezależne i wszechstronne. Ale moje doświadczenie mówi, żeTraversable
jest to zwykle używane tylko do prostego przyklejenia algorytmów do istniejących struktur danych. Miło jest nie pisać podobnych funkcji dla różnych kwalifikowanych typów danych.źródło