O que constitui uma dobra para tipos diferentes de lista?

Considere uma lista de link único. Parece algo como

data List x = Node x (List x) | End 

É natural definir uma function de dobragem como

 reduce :: (x -> y -> y) -> y -> List x -> y 

De certo modo, reduce f x0 substitui todos os Node por f e cada End com x0 . Isto é o que o Prelúdio se refere como uma dobra .

Agora considere uma tree binária simples:

 data Tree x = Leaf x | Branch (Tree x) (Tree x) 

É igualmente natural definir uma function como

 reduce :: (y -> y -> y) -> (x -> y) -> Tree x -> y 

Observe que essa redução tem um caráter bem diferente; Considerando que o baseado em lista é inerentemente sequencial, este novo baseado em tree tem mais de uma sensação de dividir-e-conquistar para ele. Você poderia até imaginar jogando alguns combinadores de par lá dentro. (Onde você colocaria essa coisa na versão da lista?)

Minha pergunta: essa function ainda é classificada como “dobra” ou é outra coisa? (E se sim, o que é isso?)

Basicamente, sempre que alguém fala sobre dobrar, eles sempre falam sobre listas dobráveis, que são inerentemente sequenciais. Eu estou querendo saber se “seqüencial” é parte da definição do que é uma dobra, ou se esta é apenas uma propriedade coincidente do exemplo mais comumente usado de dobrar.

Tikhon tem o material técnico para baixo. Acho que vou tentar simplificar o que ele disse.

O termo “dobrar”, infelizmente, tornou-se ambíguo ao longo dos anos para significar uma das duas coisas:

  1. Reduzindo uma coleção sequencialmente em alguma ordem. Em Haskell, isso é o que significa “dobrar” na class Foldable , que o larsmans traz.
  2. A noção que você pediu: “destruindo” (oposto de construir ), “observando” ou “eliminando” um tipo de dado algébrico de acordo com sua estrutura. Também chamado de catamorfismo .

É possível definir essas duas noções genericamente, de modo que uma function parametrizada seja capaz de fazer isso para uma variedade de tipos. Tikhon mostra como fazer no segundo caso.

Mas na maioria das vezes vai todo o caminho com Fix e as álgebras e tal é um exagero. Vamos elaborar uma maneira mais simples de escrever a dobra para qualquer tipo de dado algébrico. Usaremos Maybe , pares, listas e trees como nossos exemplos:

 data Maybe a = Nothing | Just a data Pair ab = Pair ab data List a = Nil | Cons a (List a) data Tree x = Leaf x | Branch (Tree x) (Tree x) data BTree a = Empty | Node a (BTree a) (BTree a) 

Note que Pair não é recursivo; o procedimento que vou mostrar não assume que o tipo “fold” seja recursivo. As pessoas geralmente não chamam esse caso de “fold”, mas é realmente o caso não-recursivo do mesmo conceito.

Primeiro passo: a dobra para um determinado tipo consumirá o tipo dobrado e produzirá algum tipo de parâmetro como resultado. Eu gosto de chamar o último r (para “resultado”). Assim:

 foldMaybe :: ... -> Maybe a -> r foldPair :: ... -> Pair ab -> r foldList :: ... -> List a -> r foldTree :: ... -> Tree a -> r foldBTree :: ... -> BTree a -> r 

Segunda etapa: além do último argumento (o da estrutura), a dobra recebe tantos argumentos quanto o tipo tem construtores. Pair tem um construtor e nossos outros exemplos têm dois, então:

 foldMaybe :: nothing -> just -> Maybe a -> r foldPair :: pair -> Pair ab -> r foldList :: nil -> cons -> List a -> r foldTree :: leaf -> branch -> Tree a -> r foldBTree :: empty -> node -> BTree a -> r 

Terceiro passo: cada um desses argumentos tem a mesma aridade que o construtor ao qual corresponde. Vamos tratar os construtores como funções e escrever seus tipos (certificando-se de que as variables ​​de tipo combinem com aquelas nas assinaturas que estamos escrevendo):

 Nothing :: Maybe a Just :: a -> Maybe a Pair :: a -> b -> Pair ab Nil :: List a Cons :: a -> List a -> List a Leaf :: a -> Tree a Branch :: Tree a -> Tree a -> Tree a Empty :: BTree a Node :: a -> BTree a -> BTree a -> BTree a 

Etapa 4: na assinatura de cada construtor, replaceemos todas as ocorrências do tipo de dados que ele constrói com nossa variável de tipo r (que estamos usando em nossas assinaturas de dobra):

 nothing := r just := a -> r pair := a -> b -> r nil := r cons := a -> r -> r leaf := a -> r branch := r -> r -> r empty := r node := a -> r -> r -> r 

Como você pode ver, eu “atribuí” as assinaturas resultantes às minhas variables ​​do tipo dummy da segunda etapa. Agora, Etapa 5: preencha os dados nas assinaturas de dobra de esboço anteriores:

 foldMaybe :: r -> (a -> r) -> Maybe a -> r foldPair :: (a -> b -> r) -> Pair ab -> r foldList :: r -> (a -> r -> r) -> List a -> r foldTree :: (a -> r) -> (r -> r -> r) -> Tree a -> r foldBTree :: r -> (a -> r -> r -> r) -> BTree a -> r 

Agora, estas são assinaturas para as dobras desses tipos. Eles têm uma ordem de argumento engraçada, porque eu fiz isso mecanicamente lendo o tipo de dobra das declarações de data e tipos de construtor, mas por algum motivo na functional programming é convencional colocar casos base primeiro em definições de data mas manipuladores de caso recursivos primeiro em definições de fold . Sem problemas! Vamos reorganizá-los para torná-los mais convencionais:

 foldMaybe :: (a -> r) -> r -> Maybe a -> r foldPair :: (a -> b -> r) -> Pair ab -> r foldList :: (a -> r -> r) -> r -> List a -> r foldTree :: (r -> r -> r) -> (a -> r) -> Tree a -> r foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r 

As definições também podem ser preenchidas mecanicamente. Vamos escolher o foldBTree e implementá-lo passo a passo. A dobra para um determinado tipo é a única function do tipo que descobrimos que atende a essa condição: dobrar com os construtores do tipo é uma function de identidade sobre esse tipo (você obtém o mesmo resultado que o valor com o qual começou).

Vamos começar assim:

 foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r foldBTree = ??? 

Sabemos que são necessários três argumentos, para que possamos adicionar variables ​​para refleti-los. Vou usar nomes descritivos longos:

 foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r foldBTree branch empty tree = ??? 

Olhando para a declaração de data , sabemos que o BTree tem dois possíveis construtores. Podemos dividir a definição em um caso para cada e preencher variables ​​para seus elementos:

 foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r foldBTree branch empty Empty = ??? foldBTree branch empty (Branch alr) = ??? -- Let's use comments to keep track of the types: -- a :: a -- l, r :: BTree a 

Agora, aquém de algo como undefined , a única maneira de preencher a primeira equação é com empty :

 foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r foldBTree branch empty Empty = empty foldBTree branch empty (Branch alr) = ??? -- a :: a -- l, r :: BTree a 

Como preenchemos a segunda equação? Mais uma vez, curto de undefined , temos isso:

 branch :: a -> r -> r -> r a :: a l, r :: BTree a 

Se tivéssemos subfold :: BTree a -> r , poderíamos fazer branch a (subfold l) (subfold r) :: r . Mas é claro, podemos escrever “subfold” facilmente:

 foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r foldBTree branch empty Empty = empty foldBTree branch empty (Branch alr) = branch a (subfold l) (subfold r) where subfold = foldBTree branch empty 

Esta é a dobra para BTree , porque foldBTree Branch Empty anyTree == anyTree . Note que foldBTree não é a única function deste tipo; também tem isso:

 mangleBTree :: (a -> r -> r -> r) -> r -> BTree a -> r mangleBTree branch empty Empty = empty mangleBTree branch empty (Branch alr) = branch a (submangle r) (submangle l) where submangle = mangleBTree branch empty 

Mas, em geral, o mangleBTree não possui a propriedade requerida; por exemplo, se tivermos foo = Branch 1 (Branch 2 Empty Empty) Empty , segue-se que mangleBTree Branch Empty foo /= foo . Então mangleBTree , embora tenha o tipo correto, não é a dobra.


Agora, vamos dar um passo para trás a partir dos detalhes e nos concentrar no último ponto com o exemplo do mangleTree . Uma dobra (no sentido estrutural, # 2 no topo da minha resposta) é nada mais e nada mais do que a function mais simples, não-trivial para um tipo algébrico de tal forma que, quando você dá passagem nos construtores do tipo como seus argumentos, torna-se a function de identidade para esse tipo. (Por não trivial, quero dizer que coisas como foo fz xs = xs não são permitidas.)

Isso é muito significativo. Duas maneiras que eu gosto de pensar sobre isso são as seguintes:

  1. A dobra para um determinado tipo pode “ver” todas as informações contidas por qualquer valor desse tipo. (É por isso que é capaz de “reconstruir” perfeitamente qualquer valor desse tipo a partir do zero usando os construtores do tipo.)
  2. A dobra é a function de “consumidor” mais geral para esse tipo. Qualquer function que consome um valor do tipo em questão pode ser escrita de modo que as únicas operações que ele usa desse tipo sejam a dobra e os construtores. (Embora as versões somente de dobrar de algumas funções sejam difíceis de escrever e executar mal, tente escrever tail :: [a] -> [a] com foldr , (:) e [] como um exercício doloroso.)

E o segundo ponto vai ainda mais longe, pois você nem precisa dos construtores. Você pode implementar qualquer tipo algébrico sem usar declarações de data ou construtores, usando nada além de dobras:

 {-# LANGUAGE RankNTypes #-} -- | A Church-encoded list is a function that takes the two 'foldr' arguments -- and produces a result from them. newtype ChurchList a = ChurchList { runList :: forall r. (a -> r -> r) -- ^ first arg of 'foldr' -> r -- ^ second arg of 'foldr' -> r -- ^ 'foldr' result } -- | Convenience function: make a ChurchList out of a regular list toChurchList :: [a] -> ChurchList a toChurchList xs = ChurchList (\kons knil -> foldr kons knil xs) -- | 'toChurchList' isn't actually needed, however, we can make do without '[]' -- completely. cons :: a -> ChurchList a -> ChurchList a cons x xs = ChurchList (\fz -> fx (runlist xs fz)) nil :: ChurchList a nil = ChurchList (\fz -> z) foldr' :: (a -> r -> r) -> r -> ChurchList a -> r foldr' fz xs = runList xs fz head :: ChurchList a -> Maybe a head = foldr' ((Just .) . const) Nothing append :: ChurchList a -> ChurchList a -> ChurchList a append xs ys = foldr' cons ys xs -- | Convert a 'ChurchList' to a regular list. fromChurchList :: ChurchList a -> [a] fromChurchList xs = runList xs (:) [] 

Como um exercício, você pode tentar escrever outros tipos dessa maneira (que usa a extensão RankNTypes leia isto para uma cartilha ). Essa técnica é chamada de codificação Church e às vezes é útil na programação real – por exemplo, o GHC usa algo chamado foldr / build fusion para otimizar o código de lista para remover listas intermediárias; veja esta página Wiki do Haskell e observe o tipo de build :

 build :: (forall b. (a -> b -> b) -> b -> b) -> [a] build g = g (:) [] 

Exceto pelo newtype , isso é o mesmo que o meu fromChurchList acima. Basicamente, uma das regras que o GHC usa para otimizar o código de processamento de lista é:

 -- Don't materialize the list if all we're going to do with it is -- fold it right away: foldr kons knil (fromChurchList xs) ==> runChurchList xs kons knil 

Ao implementar as funções básicas da lista para usar internamente as codificações da Igreja, inserindo suas definições agressivamente e aplicando essa regra ao código embutido, os usos nesteds de funções como map podem ser fundidos em um loop fechado.

Uma dobra para cada ocasião

Na verdade, podemos chegar a uma noção genérica de dobramento que pode ser aplicada a um monte de tipos diferentes. Ou seja, podemos definir sistematicamente uma function de fold para listas, trees e muito mais.

Essa noção genérica de fold corresponde aos catamorfismos @pelotom mencionados em seu comentário.

Tipos Recursivos

O principal insight é que essas funções de fold são definidas sobre tipos recursivos . Em particular:

 data List a = Cons a (List a) | Nil data Tree a = Branch (Tree a) (Tree a) | Leaf a 

Ambos os tipos são claramente recursivos – List no caso Cons e Tree no caso Branch .

Pontos Fixos

Assim como as funções, podemos rewrite esses tipos usando pontos fixos. Lembre-se da definição de fix :

 fix f = f (fix f) 

Na verdade, podemos escrever algo muito semelhante para tipos, exceto que ele precisa ter um wrapper de construtor extra:

 newtype Fix f = Roll (f (Fix f)) 

Assim como a fix define o ponto fixo de uma function , isso define o ponto fixo de um functor . Podemos expressar todos os nossos tipos recursivos usando esse novo tipo de Fix .

Isso nos permite rewrite os tipos de List seguinte maneira:

 data ListContainer a rest = Cons a rest | Nil type List a = Fix (ListContainer a) 

Essencialmente, o Fix nos permite aninhar ListContainer s em profundidades arbitrárias. Então poderíamos ter:

 Roll Nil Roll (Cons 1 (Roll Nil)) Roll (Cons 1 (Roll (Cons 2 (Roll Nil)))) 

que correspondem a [] , [1] e [1,2] respectivamente.

Vendo que ListContainer é um Functor é fácil:

 instance Functor (ListContainer a) where fmap f (Cons a rest) = Cons a (f rest) fmap f Nil = Nil 

Eu acho que o mapeamento de ListContainer para List é bastante natural: em vez de recursing explicitamente, fazemos da parte recursiva uma variável. Então, apenas usamos Fix para preencher essa variável conforme apropriado.

Podemos escrever um tipo análogo para Tree também.

“Desempacotando” Pontos Fixos

Então, por que nos importamos? Podemos definir fold para tipos arbitrários escritos usando Fix . Em particular:

 fold :: Functor f => (fa -> a) -> (Fix f -> a) fold h = h . fmap (fold h) . unRoll where unRoll (Roll a) = a 

Essencialmente, tudo que uma dobra faz é desembrulhar o tipo “rolado” uma camada de cada vez, aplicando uma function ao resultado a cada vez. Esse “desenrolamento” nos permite definir uma dobra para qualquer tipo recursivo e generalizar o conceito de maneira clara e natural.

Para o exemplo da lista, funciona assim:

  1. A cada passo, nós desembrulhamos o Roll para obter um Cons ou um Nil
  2. Recapitalizamos o restante da lista usando o fmap .
    1. No caso Nil , fmap (fold h) Nil = Nil , então apenas retornamos Nil .
    2. No caso Cons , o fmap continua a dobra sobre o resto da lista.
  3. No final, recebemos um monte de chamadas aninhadas para fold terminando em um Nil assim como o foldr padrão.

Comparando Tipos

Agora vamos ver os tipos das duas funções de dobra. Primeiro, foldr :

 foldr :: (a -> b -> b) -> b -> [a] -> b 

Agora, fold especializada para ListContainer :

 fold :: (ListContainer ab -> b) -> (Fix (ListContainer a) -> b) 

No início, estes parecem completamente diferentes. No entanto, com um pouco de massagem, podemos mostrar que são iguais. Os dois primeiros argumentos para foldr são a -> b -> b e b . Nós temos uma function e uma constante. Podemos pensar em b como () -> b . Agora temos duas funções _ -> b onde _ é () e a -> b . Para tornar a vida mais simples, vamos colocar a segunda function nos dando (a, b) -> b . Agora podemos escrevê-los como uma única function usando o Either :

 Either (a, b) () -> b 

Isso é verdade porque, dado f :: a -> c e g :: b -> c , sempre podemos escrever o seguinte:

 h :: Either ab -> c h (Left a) = fa h (Right b) = gb 

Então agora podemos ver o foldr como:

 foldr :: (Either (a, b) () -> b) -> ([a] -> b) 

(Estamos sempre livres para adicionar parênteses ao redor -> assim, desde que sejam de associação à direita).

Agora vamos ver o ListContainer . Esse tipo tem dois casos: Nil , que não contém informações e Cons , que tem um a e um b . Em outras Nil , Nil é como () e Cons é como (a, b) , então podemos escrever:

 type ListContainer a rest = Either (a, rest) () 

Claramente isto é o mesmo que eu usei em foldr acima. Então agora nós temos:

 foldr :: (Either (a, b) () -> b) -> ([a] -> b) fold :: (Either (a, b) () -> b) -> (List a -> b) 

Então, na verdade, os tipos são isomórficos – apenas maneiras diferentes de escrever a mesma coisa! Eu acho isso muito legal.

(Como uma nota lateral, se você quiser saber mais sobre esse tipo de raciocínio com tipos, confira a álgebra de tipos de dados algébricos , uma boa série de posts sobre apenas isso.)

De volta às trees

Então, vimos como podemos definir uma fold genérica para tipos escritos como pontos fixos. Também vimos como isso corresponde diretamente a foldr para listas. Agora vamos ver seu segundo exemplo, a tree binária. Nós temos o tipo:

 data Tree a = Branch a (Tree a) (Tree a) | Leaf a 

podemos rewrite isso usando Fix seguindo as regras que fiz acima: substituímos a parte recursiva por uma variável de tipo:

 data TreeContainer a rest = Branch rest rest | Leaf a type Tree a = Fix (TreeContainer a) 

Agora nós temos uma fold tree:

 fold :: (TreeContainer ab -> b) -> (Tree a -> b) 

Seu foldTree original é assim:

 foldTree :: (b -> b -> b) -> (a -> b) -> Tree a -> b 

foldTree aceita duas funções; vamos combinar o primeiro currying e depois usar o Either :

 foldTree :: (Either (b, b) a -> b) -> (Tree a -> b) 

Nós também podemos ver como Either (b, b) a é isomorfo a TreeContainer ab . O contêiner de tree tem dois casos: Branch , contendo dois b e Leaf , contendo um a .

Portanto, esses tipos de dobras são isomórficos da mesma maneira que o exemplo de lista.

Generalizando

Existe um padrão claro emergindo. Dado um tipo de dado recursivo normal, podemos sistematicamente criar uma versão não recursiva do tipo, que nos permite expressar o tipo como um ponto fixo de um functor. Isso significa que podemos criar mecanicamente funções de fold para todos esses tipos diferentes – na verdade, provavelmente poderíamos automatizar todo o processo usando o GHC Generics ou algo assim.

De certa forma, isso significa que não temos realmente diferentes funções de fold para diferentes tipos. Em vez disso, temos uma única function de fold que é muito polimórfica.

Mais

Eu compreendi pela primeira vez essas idéias a partir de uma palestra dada por Conal Elliott. Isso entra em mais detalhes e também fala sobre o unfold , que é o dual a ser fold .

Se você quiser aprofundar-se nesse tipo de coisa, leia o fantástico artigo “Programação funcional com bananas, lentes, envelopes e arame farpado” . Entre outras coisas, isto introduz as noções de “catamorfismos” e “anamorfismos” que correspondem a dobras e desdobramentos.

Álgebras (e Coalgebras)

Além disso, não posso resistir a adicionar um plug para mim: p. Você pode ver algumas semelhanças interessantes entre o modo como usamos aqui e o modo como usei quando falamos de álgebras em outra resposta SO.

Há, de fato, uma conexão profunda entre o fold e as álgebras; além disso, unfold – o já mencionado dual of fold – está ligado a coalgebras, que são o dual de álgebras. A idéia importante é que os tipos de dados algébricos correspondem a “álgebras iniciais”, que também definem dobras, conforme descrito no restante da minha resposta.

Você pode ver esta conexão no tipo geral de fold :

 fold :: Functor f => (fa -> a) -> (Fix f -> a) 

O fa -> a termo parece muito familiar! Lembre-se que uma f-álgebra foi definida como algo como:

 class Functor f => Algebra fa where op :: fa -> a 

Então, podemos pensar em fold como apenas:

 fold :: Algebra fa => Fix f -> a 

Essencialmente, o fold nos permite “resumir” as estruturas definidas usando a álgebra.

Uma dobra substitui todos os construtores por uma function.

Por exemplo, foldr cons nil substitui every (:) por cons e [] por nil :

 foldr cons nil ((:) 1 ((:) 2 [])) = cons 1 (cons 2 nil) 

Para uma tree, a foldTree branch leaf substitui cada Branch com a branch e cada Leaf com a leaf :

 foldTree branch leaf (Branch (Branch (Leaf 1) (leaf 2)) (Leaf 3)) = branch (branch (leaf 1) (leaf 2)) (leaf 2) 

É por isso que cada dobra aceita argumentos que têm exatamente o mesmo tipo que os construtores:

 foldr :: (a -> list -> list) -> list -> [a] -> list foldTree :: (tree -> tree -> tree) -> (a -> tree) -> Tree a -> tree 

Eu chamaria isso de fold e declararia Tree a Foldable . Veja o exemplo Foldable nos documentos do GHC .

    Intereting Posts