Czy ktoś może wyjaśnić funkcję trawersu w Haskell?

Próbuję i nie udaje mi się zrozumieć traversefunkcji 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.

traversejest taki sam, jak fmap, z wyjątkiem tego, że umożliwia również uruchamianie efektów podczas odbudowywania struktury danych.

Spójrz na przykład z Data.Traversabledokumentacji.

 data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

FunctorInstancja Treebędzie:

instance Functor Tree where
  fmap f Empty        = Empty
  fmap f (Leaf x)     = Leaf (f x)
  fmap f (Node l k r) = Node (fmap f l) (f k) (fmap f r)

Odbudowuje całe drzewo, stosując się fdo każdej wartości.

instance Traversable Tree where
    traverse f Empty        = pure Empty
    traverse f (Leaf x)     = Leaf <$> f x
    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

TraversableInstancja 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 Traversableklasa zawiera również monadyczną wersję traversetzw mapM. Pod każdym względem mapMjest to samo co traverse- istnieje jako odrębna metoda, bo Applicativedopiero później stała się nadklasą Monad.

Jeśli zaimplementowałbyś to w nieczystym języku, fmapbyłoby to samo co traverse, 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:

Node.prototype.traverse = function (f) {
  return new Node(this.l.traverse(f), f(this.k), this.r.traverse(f));
}

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.

traversezamienia rzeczy wewnątrz a Traversablew Traversablerzeczy „wewnątrz” an Applicative, biorąc pod uwagę funkcję, która tworzy Applicatives z rzeczy.

Użyjmy Maybejako Applicativei wypiszmy jako Traversable. Najpierw potrzebujemy funkcji transformacji:

half x = if even x then Just (x `div` 2) else Nothing

Więc jeśli liczba jest parzysta, otrzymujemy jej połowę (wewnątrz a Just), w przeciwnym razie otrzymamy Nothing. Jeśli wszystko idzie „dobrze”, wygląda to tak:

traverse half [2,4..10]
--Just [1,2,3,4,5]

Ale...

traverse half [1..10]
-- Nothing

Powodem jest to, że <*>funkcja jest używana do budowania wyniku, a gdy jeden z argumentów jest Nothing, otrzymujemy z Nothingpowrotem.

Inny przykład:

rep x = replicate x x

Ta funkcja generuje listę długości xz zawartością x, np . rep 3= [3,3,3]. Jaki jest skutek traverse rep [1..3]?

Otrzymujemy częściowe rezultaty [1], [2,2]a [3,3,3]przy użyciu rep. Teraz semantyka list typu Applicatives„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:

traverse rep [1..3]
--[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]

Myślę, że najłatwiej jest to zrozumieć w kategoriach sequenceA, co traversemożna zdefiniować następująco.

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f

sequenceA sekwencjonuje razem elementy struktury od lewej do prawej, zwracając strukturę o tym samym kształcie zawierającą wyniki.

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
sequenceA = traverse id

Możesz również pomyśleć o sequenceAodwróceniu kolejności dwóch funktorów, np. Przejściu z listy akcji do akcji zwracającej listę wyników.

Tak więc traverseprzyjmuje pewną strukturę i stosuje się fdo 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_.

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()

Widać więc, że kluczowa różnica między Foldablei Traversablepolega 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 IOaplikacji:

λ> import Data.Traversable
λ> let qs = ["name", "quest", "favorite color"]
λ> traverse (\thing -> putStrLn ("What is your " ++ thing ++ "?") *> getLine) qs
What is your name?
Sir Lancelot
What is your quest?
to seek the holy grail
What is your favorite color?
blue
["Sir Lancelot","to seek the holy grail","blue"]

Chociaż ten przykład jest raczej mało ekscytujący, rzeczy stają się bardziej interesujące, gdy traversejest używany na innych typach pojemników lub przy użyciu innych aplikacji.

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, aby fmapte identyfikatory użytkowników były nazwami użytkowników, nie możesz użyć tradycyjnego fmap, 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ą IOmonady).

Podpis traverse:

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

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:

mapUserIDsToUsernames :: (Num -> IO String) -> [Num] -> IO [String]
mapUserIDsToUsernames fn ids = traverse fn ids

Jest też funkcja o nazwie mapM:

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

Każde użycie mapMmoże zostać zastąpione traverse, ale nie odwrotnie. mapMdziała tylko dla monad, podczas gdy traversejest bardziej ogólny.

Jeśli chcesz tylko uzyskać efekt i nie zwracać żadnej użytecznej wartości, istnieją traverse_i mapM_wersje tych funkcji, z których obie ignorują wartość zwracaną przez funkcję i są nieco szybsze.

traverse jest pętlą. Jego implementacja zależy od struktury danych, przez którą przechodzimy. To może być lista, drzewo Maybe, 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 Traversabletypeklasie prawdopodobnie mógłbyś napisać swoje algorytmy bardziej niezależne i wszechstronne. Ale moje doświadczenie mówi, że Traversablejest 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.