então eu ouço muitas vezes as palavras “catamorfismo”e” esquemas de recursão”. O que se passa?
Catamorfismos (ou cata) são generalizações do conceito de um fold na programação funcional. Dada uma álgebra F e uma estrutura recursiva de dados, um catamorfismo produzirá um valor ao avaliar recursivamente a sua estrutura de dados.
o que é uma álgebra F? Talvez possa mostrar alguns exemplos de código primeiro?
a configuração não é tão simples assim vamos começar simples. Digamos que você tenha a seguinte estrutura de dados para representar uma expressão:
HaskellScala
E uma expressão simples pode ficar assim:
Tendo apenas uma expressão estrutura de dados é inútil, é claro que você vai precisar de uma função de avaliar e obter o resultado:
Este é o lugar onde catamorphism generalização vem em:
🤨, mas qual é o ponto? Estás a aplicar uma discussão a uma função?
isso é porque é notReallyCata. A função real cata é genérica e não depende de qualquer estrutura de dados particular ou função de Avaliador. Veja, a criação de uma estrutura de dados recursiva e então dobrando sobre ela é um padrão comum que cata tenta generalizar.Ok, então como é o verdadeiro cata?
🤯
por isso começamos com notReallyCata. Vamos quebrar a implementação mais tarde até que ela clica. Mas agora vamos continuar com o nosso exemplo Expression. Primeiro, precisamos nos livrar da recursão introduzindo um parâmetro de tipo:
todas as referências a Expression são substituídas por a parâmetro do tipo de modo que a estrutura de dados não é mais recursiva.
por que existe um F no final dos construtores de tipo?Ainda bem que perguntou.Functor:
nada de Especial, apenas a aplicar alguma função ao valor embrulhado preservando a stucture.
Não sei por que temos que 🤔
não faz sentido agora, mas ele vai um pouco mais tarde. Agora, a forma como criamos a nossa expressão não se alterou (exceto para nomes construtor):
Mas o tipo resultante é diferente:
expr cai tudo em um único Expression enquanto exprF codifica as informações sobre o nível de aninhamento de nossa árvore de expressão. Por falar em avaliação, é assim que podemos implementar eval for ExpressionF:
a principal diferença com evalExpr original é que não temos chamada recursiva para evalExprF (ExpressionF não é recursiva, lembra-se?). Isso também significa que a nossa avaliador pode trabalhar apenas com um único nível de expressão:
E não vai compilar neste:
Simplesmente porque exprF expepects ExpressionF Int e estamos empurrando ExpressionF (ExpressionF Int).Para o fazer funcionar, poderíamos definir outro avaliador.:
parece um pouco ad hoc, e se tiver expressões profundamente aninhadas?
Sim, para arbitrário aninhadas expressão esta abordagem não é escalável — cada nível de aninhamento requer que você escreva função especializada.
há uma maneira de generalizar este nidificação com um novo tipo:
arranjar? Parece uma estrutura de dados recursiva que não faz muito. Como é útil?
vamos primeiro olhar para a expressão antes do sinal de igual: na verdade Fix é uma estrutura de dados recursiva que tem um parâmetro de tipo f. Este parâmetro tem tipo * -> * e.g. ele também tem um parâmetro tipo. Por exemplo, você não pode construir Fix fornecendo Int ou Bool, tem que ser algo como Maybe, List ou… ExpressionF. É por isso que introduzimos o parâmetro tipo para ExpressionF. Em seguida, após o sinal de igual, temos um único construtor de tipo Fx tomando um único argumento de tipo f (Fix f) que é basicamente uma expressão que constrói o valor de f. No caso de Maybe seria Maybe (Fix Maybe) e então a coisa toda é embrulhada com Fx em Tipo Fix Maybe.
a assinatura do tipo é confusa para se ler no início porque o construtor do tipo pode ter o mesmo nome que o próprio tipo mais auto-referenciação. Mas não há muito mais para ele do que apenas empacotar um tipo de ordem superior em uma estrutura de dados. Btw, unfix é um oposto a Fx e tudo o que faz é corresponder padrão em Fx e retorna o valor embrulhado, nada de especial.
agora, vamos substituir cada ExpressionF da nossa árvore de expressão por Fix ExpressionF. Observe a diferença na construção de expressões com e sem Fx — eles são basicamente o mesmo, exceto que precisa preceder Fx $:
O tipo resultante de um “fixo”, versão Fix ExpressionF então estamos de volta a uma representação recursiva, mas agora nós temos que usar unfix função para obter os nossos não recursiva estrutura de dados de volta.
quais são os benefícios de ter Fix? Parece que é a mesma abordagem do tipo original Expression mas agora temos este absurdo estranho Fix e unfix?
Sim, mas estamos tentando generalizar o processo de dobramento, que requer a introdução de abstrações adicionais, como Fix e Algebra que discutiremos mais tarde. Sê paciente comigo, vai fazer mais sentido mais tarde.Então temos a nossa estrutura de dados “fixa”, como seria a função de avaliação?
Dado um Fix ExpressionF a única coisa que podemos fazer com ele é chamada de unfix que produz ExpressionF (Fix ExpressionF):
A devolvidos ExpressionF pode ser um dos nossos ValueF, AddF ou MultF tendo um Fix ExpressionF o tipo de parâmetro. Faz sentido para fazer a correspondência de padrão e decidir o que fazer a seguir:
Sim, parece o mesmo que o nosso primeiro recursiva avaliador Expression com adição de ter para desembrulhar a expressão unfix. Então, porquê preocupar-se com Fix?Aqui está a chave.: vamos reutilizar o nosso avaliador “fix-less” original para ExpressionF e, de alguma forma, distribuí-lo pela stucture Fix ExpressionF. Portanto, isso deve ser uma função que toma dois argumentos — o avaliador e a estrutura para avaliar:
Vamos tentar descobrir a implementação — a primeira coisa lógica a fazer é usar unfix para obter ExpressionF e, em seguida, talvez passar para evaluator:
Obviamente, isso não funciona, evaluator espera ExpressionF Int e não ExpressionF (Fix ExpressionF). A propósito, lembra-te que ExpressionF é um Functor? Este é o local onde fica a calhar podemos usar fmap para aplicar o mesmo processo para o nível interno de nossa árvore de expressão:
Tome um momento e pense sobre o que acontece: estamos passando uma função recursiva em fmap. Se a expressão atual for AddF ou MultF então esta função será passada um nível mais profundo e fmap será chamada novamente. Isto irá acontecer até chegarmos a ValueF, o fmapping sobre ValueF devolve o valor do tipo ExpressionF Int e é exactamente isso que a nossa função evaluator aceita.
observando almostCata podemos ver que ele realmente não tem nada específico para ExpressionF ou Int tipo e, teoricamente, pode ser generalizado, com algum tipo de parâmetro f. A única restrição deve ser ter uma instância Functor para f, porque estamos usando fmap:
e esta é a versão final de cata. Aqui está a implementação completa com alguns exemplos de uso:
acho que isso é fixe. Mas porquê?
muitos conceitos na teoria das categorias e na programação funcional são bastante abstractos e, por vezes, é difícil encontrar aplicação prática imediata para uma determinada ideia. Mas procurar abstrações e generalizações é útil para encontrar padrões e soluções elegantes para problemas que de outra forma requerem implementação ad-hoc.A propósito, ao generalizar a nossa função ExpressionF -> Int a Functor f => (f a -> a) descobrimos outro conceito importante chamado F-Álgebra. Basicamente F-álgebra é um triplo de functor f, algum tipo a e função Avaliadora f a -> a. Note que a aqui não polimórfico — tem que ser um tipo concreto, como Int ou Bool e é chamado de tipo portador. Para qualquer endo-functor f você pode criar vários F-Álgebra baseados nele. Tomemos como exemplo as nossas expressões — endo-functor f é ExpressionF, a é Int e o avaliador é evalExprF. Mas podemos mudar o transportador tipo e produzir mais álgebras:
isso é apenas diferentes avaliadores que podem ser passados para cata, certo?
Sim, estamos escolhendo diferentes tipos de portadoras e escolhendo a nossa implementação. Mas aí está o truque-há uma mãe de todos os avaliadores que podemos criar escolhendo o nosso tipo de porta-aviões para ser … Fix ExprF.
avaliar a Int ou Bool faz todo o sentido, mas o que é que este initialAlgebra avaliaria? Quando preciso de ter Fix de algo como resultado do meu avaliador?
é claro que você não vai escrever algo assim você mesmo, só quer mostrar-lhe o significado mais profundo por trás das álgebras f e cata. Na verdade, já temos uma implementação para esse avaliador e isso é exatamente Fx construtor:
espera, o Fx é um avaliador? Isso é uma loucura.
Yes and it does the most simple thing you can do-save the expession into a data structure. Enquanto todos os outros avaliadores (algebra0, algebra1) produziu alguns de valor, reduzindo a expressão (como fazer soma ou concatenação) Fx apenas envolve a expressão, sem perder quaisquer dados.
é por Isso que introduzimos Fix em primeiro lugar — você o primeiro a avaliar sua estrutura de dados original com Fx na inicial álgebra Fix f e, em seguida, usando cata o ‘real’ avaliação acontece por fmaping seu concreto avaliador sobre o primeiro álgebra.
do ponto de vista da teoria das categorias, Todas as álgebras baseadas no mesmo functor de endo formam uma categoria. Esta categoria tem um objeto inicial que é a nossa álgebra inicial criada escolhendo o tipo portador como Fix f. Há alguns posts grandes blog por Bartosz Milewski que eu recomendo verificar para fora se você quiser obter compreensão categórica profunda.
ainda É muito difícil de compreender, eu não acho que eu entender completamente o conceito
É sempre melhor fazer as mãos sobre: tente re-implementação Fix e cata em seu próprio país, pensar sobre possíveis estruturas de dados e álgebra. Por exemplo, um String pode ser representado recursivamente (como um Char cabeça e cauda de String), o length de uma cadeia pode ser calculado com cata. Aqui estão alguns grandes recursos para mais leitura:
Entendimento F-Álgebras e ligeiramente diferente do F-Álgebras por Bartosz Milewski
Catamorphisms em 15 minutos por Chris Jones
Puro, Funcional de Programação de Banco de dados com ponto fixo Tipos de Rob Norris
