Alguém pode explicar a função transversal em Haskell?

99

Estou tentando e falhando em grocar a traversefunção de Data.Traversable. Não consigo ver seu ponto. Visto que venho de um background imperativo, alguém pode me explicar em termos de um loop imperativo? O pseudo-código seria muito apreciado. Obrigado.

Konan
fonte
1
O artigo A essência do padrão do iterador pode ser útil, pois constrói a noção de transversal passo a passo. Alguns conceitos avançados estão presentes
Jackie

Respostas:

121

traverseé o mesmo que fmap, exceto que também permite que você execute efeitos enquanto reconstrói a estrutura de dados.

Dê uma olhada no exemplo da Data.Traversabledocumentação.

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

A Functorinstância de Treeseria:

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)

Ele reconstrói a árvore inteira, aplicando-se fa todos os valores.

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

A Traversableinstância é quase a mesma, exceto que os construtores são chamados no estilo aplicativo. Isso significa que podemos ter efeitos (colaterais) enquanto reconstruímos a árvore. O Applicative é quase o mesmo que as mônadas, exceto que os efeitos não podem depender dos resultados anteriores. Neste exemplo, isso significa que você não pode fazer algo diferente para o ramo direito de um nó, dependendo dos resultados da reconstrução do ramo esquerdo, por exemplo.

Por razões históricas, a Traversableclasse também contém uma versão monádica de traversechamado mapM. Para todos os efeitos e propósitos mapMé o mesmo que traverse- existe como um método separado porque Applicativesó mais tarde se tornou uma superclasse de Monad.

Se você implementasse isso em uma linguagem impura, fmapseria o mesmo que traverse, já que não há como evitar efeitos colaterais. Você não pode implementá-lo como um loop, pois tem que percorrer sua estrutura de dados recursivamente. Aqui está um pequeno exemplo de como eu faria isso em Javascript:

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

Implementá-lo assim limita você aos efeitos que a linguagem permite. Se você quer o não determinismo (que é a instância da lista de modelos Aplicativos) e sua linguagem não o tem embutido, você está sem sorte.

Sjoerd Visscher
fonte
11
O que significa o termo 'efeito'?
missingfaktor,
24
@missingfaktor: Significa a informação estrutural de a Functor, a parte que não é paramétrica. O valor do estado em State, falha em Maybee Either, o número de elementos em []e, claro, efeitos colaterais externos arbitrários em IO. Eu não ligo para ele como um termo genérico (como as Monoidfunções usando "vazio" e "anexar", o conceito é mais genérico do que o termo sugere no início), mas é bastante comum e serve ao propósito muito bem.
CA McCann de
@CA McCann: Entendi. Obrigado por responder!
missingfaktor,
1
"Tenho quase certeza de que você não deveria fazer isso [...]." Definitivamente não - seria tão desagradável quanto fazer os efeitos de apdepender dos resultados anteriores. Eu reformulei essa observação em conformidade.
duplode
2
"Aplicative é quase o mesmo que mônadas, exceto que os efeitos não podem depender de resultados anteriores." ... muitas coisas se encaixaram para mim com esta linha, obrigado!
agam
58

traversetransforma as coisas dentro de uma Traversableem uma Traversabledas coisas "dentro" de uma Applicative, dada uma função que faz Applicatives das coisas.

Vamos usar Maybecomo Applicativee listar como Traversable. Primeiro, precisamos da função de transformação:

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

Portanto, se um número for par, obtemos metade dele (dentro de a Just), caso contrário, obtemos Nothing. Se tudo correr "bem", será assim:

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

Mas...

traverse half [1..10]
-- Nothing

O motivo é que a <*>função é usada para construir o resultado, e quando um dos argumentos é Nothing, nós o obtemos Nothing.

Outro exemplo:

rep x = replicate x x

Esta função gera uma lista de comprimento xcom o conteúdo x, por exemplo rep 3= [3,3,3]. Qual é o resultado de traverse rep [1..3]?

Nós obter os resultados parciais de [1], [2,2]e [3,3,3]usando rep. Agora a semântica de listas como Applicativesé "tomar todas as combinações", por exemplo, (+) <$> [10,20] <*> [3,4]é [13,14,23,24].

"Todas as combinações" de [1]e [2,2]são duas vezes [1,2]. Todas as combinações de duas vezes [1,2]e [3,3,3]são seis vezes [1,2,3]. Então nós temos:

traverse rep [1..3]
--[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]
Landei
fonte
1
Seu resultado final me lembra disso .
hugomg
3
@missingno: Sim, eles perderamfac n = length $ traverse rep [1..n]
Landei
1
Na verdade, está lá em "List-encoding-programmer" (mas usando listas de compreensão). Esse site é abrangente :)
hugomg
1
@missingno: Hm, não é exatamente o mesmo ... ambos estão contando com o comportamento do produto cartesiano da mônada da lista, mas o site só usa dois de cada vez, então é mais como fazer do liftA2 (,)que usar a forma mais genérica traverse.
CA McCann de
41

Acho que é mais fácil de entender em termos de sequenceA, como traversepode ser definido a seguir.

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

sequenceA sequencia os elementos de uma estrutura da esquerda para a direita, retornando uma estrutura com a mesma forma contendo os resultados.

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

Você também pode pensar sequenceAem inverter a ordem de dois functores, por exemplo, ir de uma lista de ações para uma ação que retorna uma lista de resultados.

Então traversepega alguma estrutura e se aplica fpara transformar cada elemento da estrutura em algum aplicativo, então sequencia os efeitos desses aplicativos da esquerda para a direita, retornando uma estrutura com o mesmo formato contendo os resultados.

Você também pode compará-lo com Foldable, que define a função relacionada traverse_.

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

Portanto, você pode ver que a principal diferença entre Foldablee Traversableé que o último permite que você preserve a forma da estrutura, enquanto o primeiro exige que você dobre o resultado em algum outro valor.


Um exemplo simples de seu uso é o uso de uma lista como estrutura percorrível e IOcomo aplicativo:

λ> 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"]

Embora este exemplo seja bastante monótono, as coisas ficam mais interessantes quando traverseé usado em outros tipos de contêineres ou usando outros aplicativos.

Hammar
fonte
Portanto, travessia é simplesmente uma forma mais geral de mapM? Na verdade, sequenceA . fmappara listas é equivalente a sequence . mapnão é?
Raskell
O que você quer dizer com 'sequenciamento de efeitos colaterais'? Qual é o 'efeito colateral' em sua resposta - eu apenas pensei que os efeitos colaterais são possíveis apenas em mônadas. Saudações.
Marek
1
@Marek "Eu apenas pensei que os efeitos colaterais só são possíveis em mônadas" - A conexão é muito mais frouxa do que isso: (1) O IO tipo pode ser usado para expressar efeitos colaterais; (2) IOpassa a ser uma mônada, o que acaba sendo muito conveniente. Mônadas não estão essencialmente ligadas a efeitos colaterais. Também deve ser notado que há um significado de “efeito” que é mais amplo do que “efeito colateral” em seu sentido usual - um que inclui cálculos puros. Sobre este último ponto, veja também o que significa exatamente “eficaz” .
duplode
(A propósito, @hammar, tomei a liberdade de alterar "efeito colateral" para "efeito" nesta resposta devido às razões descritas no comentário acima.)
duplode
17

É mais fmapou menos parecido , exceto que você pode executar efeitos dentro da função do mapeador, que também altera o tipo de resultado.

Imagine uma lista de inteiros que representam IDs de usuário em um banco de dados: [1, 2, 3]. Se você quiser fmapesses IDs de usuário para nomes de usuário, não pode usar um tradicional fmap, porque dentro da função você precisa acessar o banco de dados para ler os nomes de usuário (o que requer um efeito - neste caso, usando a IOmônada).

A assinatura de traverseé:

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

Com o traverse, você pode fazer efeitos, portanto, seu código para mapear IDs de usuário para nomes de usuário se parece com:

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

Também existe uma função chamada mapM:

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

Qualquer uso de mapMpode ser substituído por traverse, mas não o contrário. mapMsó funciona para mônadas, embora traverseseja mais genérico.

Se você quiser apenas para conseguir um efeito e não devolver qualquer valor útil, existem traverse_e mapM_versões destas funções, sendo que ambos ignorar o valor de retorno da função e são ligeiramente mais rápido.

Kai Sellgren
fonte
7

traverse é o loop. Sua implementação depende da estrutura de dados a ser percorrida. Isso pode ser uma lista, árvore, Maybe, Seq(influência), ou qualquer coisa que tenha uma forma genérica de ser percorrido através de algo como um para-loop ou função recursiva. Um array teria um loop for, uma lista um loop while, uma árvore ou algo recursivo ou a combinação de uma pilha com um loop while; mas em linguagens funcionais você não precisa desses comandos de loop incômodos: você combina a parte interna do loop (na forma de uma função) com a estrutura de dados de uma maneira mais direta e menos detalhada.

Com a Traversabletypeclass, você provavelmente poderia escrever seus algoritmos mais independentes e versáteis. Mas minha experiência diz que isso Traversablegeralmente é usado apenas para colar algoritmos em estruturas de dados existentes. É muito bom não precisar escrever funções semelhantes para diferentes tipos de dados qualificados também.

comonad
fonte