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

99

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.

Konan
źródło
1
Artykuł The Essence of the Iterator Pattern może być pomocny, ponieważ buduje pojęcie trawersu krok po kroku. Istnieją jednak pewne zaawansowane koncepcje
Jackie

Odpowiedzi:

121

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.

Sjoerd Visscher
źródło
11
Co oznacza termin „skutek”?
missingfaktor
24
@missingfaktor: Oznacza informacje strukturalne Functorczęści, która nie jest parametryczna. Wartość stanu w State, awaria Maybei Either, liczba elementów w []i oczywiście dowolne zewnętrzne skutki uboczne w IO. Nie obchodzi mnie to jako termin ogólny (podobnie jak Monoidfunkcje 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.
CA McCann,
@CA McCann: Rozumiem. Dzięki za odpowiedź!
missingfaktor
1
„Jestem prawie pewien, że nie powinieneś tego robić […]”. Zdecydowanie nie - byłoby to tak nieprzyjemne, jak uzależnienie efektów od appoprzednich wyników. Odpowiednio przeredagowałem tę uwagę.
duplode
2
„Applicative to prawie to samo, co monady, z tym wyjątkiem, że efekty nie mogą zależeć od poprzednich wyników”. ... wiele rzeczy zaskoczyło mnie w tej linii, dzięki!
agam
58

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]]
Landei
źródło
1
Twój wynik końcowy przypomina mi o tym .
hugomg
3
@missingno: Tak, spudłowalifac n = length $ traverse rep [1..n]
Landei
1
Właściwie jest tam pod "List-encoding-programmer" (ale używając list składanych). Ta strona jest obszerna :)
hugomg
1
@missingno: Hm, to nie jest dokładnie to samo ... oba polegają na zachowaniu kartezjańskich produktów z listy, ale witryna używa tylko dwóch naraz, więc bardziej przypomina to robienie liftA2 (,)niż bardziej ogólny formularz traverse.
CA McCann,
42

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.

hammar
źródło
Więc trawers jest po prostu bardziej ogólną formą mapM? W rzeczywistości, sequenceA . fmapponieważ listy jest równoważne, sequence . mapprawda?
Raskell,
Co rozumiesz przez „sekwencjonowanie skutków ubocznych”? Co to jest „efekt uboczny” w Twojej odpowiedzi - pomyślałem, że efekty uboczne są możliwe tylko w monadach. Pozdrowienia.
Marek
1
@Marek "Pomyślałem, że efekty uboczne są możliwe tylko w monadach" - Połączenie jest dużo luźniejsze: (1) IO Typ może być użyty do wyrażenia efektów ubocznych; (2) IOjest 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” .
duplode
(Nawiasem mówiąc, @hammar, pozwoliłem sobie zmienić „efekt uboczny” na „efekt” w tej odpowiedzi z powodów przedstawionych w powyższym komentarzu.)
duplode
17

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.

Kai Sellgren
źródło
7

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.

comonad
źródło