Explicação dos combinadores para o trabalhador

93

O que é um combinador ??

É "uma função ou definição sem variáveis ​​livres" (conforme definido no SO)?

Ou que tal isto: de acordo com John Hughes em seu conhecido artigo sobre Arrows, "um combinador é uma função que constrói fragmentos de programa a partir de fragmentos de programa" , o que é vantajoso porque "... o programador usando combinadores constrói muito do desejado programa automaticamente, em vez de escrever todos os detalhes à mão ". Ele prossegue dizendo isso mape filtersão dois exemplos comuns de tais combinadores.

Alguns combinadores que correspondem à primeira definição:

Alguns combinadores que correspondem à segunda definição:

  • mapa
  • filtro
  • dobrar / reduzir (presumivelmente)
  • qualquer um de >> =, compose, fmap ?????

Não estou interessado na primeira definição - isso não me ajudaria a escrever um programa real (+1 se você me convencer que estou errado). Por favor me ajude a entender a segunda definição . Acho que mapear, filtrar e reduzir são úteis: eles me permitem programar em um nível mais alto - menos erros, código mais curto e mais claro. Aqui estão algumas das minhas perguntas específicas sobre combinadores:

  1. Quais são mais exemplos de combinadores, como mapa, filtro?
  2. Quais combinadores as linguagens de programação costumam implementar?
  3. Como os combinadores podem me ajudar a projetar uma API melhor?
  4. Como faço para projetar combinadores eficazes?
  5. O que são combinadores semelhantes em uma linguagem não funcional (digamos, Java), ou o que essas linguagens usam no lugar dos combinadores?

Atualizar

Graças a @CA McCann, agora tenho um entendimento um pouco melhor sobre combinadores. Mas uma questão ainda é um obstáculo para mim:

Qual é a diferença entre um programa funcional escrito com, e outro escrito sem o uso pesado de combinadores?

Suspeito que a resposta seja que a versão com combinador pesado é mais curta, mais clara, mais geral, mas gostaria de uma discussão mais aprofundada, se possível.

Também estou procurando mais exemplos e explicações de combinadores complexos (ou seja, mais complexos do que fold) em linguagens de programação comuns.

Matt Fenwick
fonte
4
Eu considero map / filter / fold Funções de ordem superior e eu as uso o tempo todo. Ainda não tenho ideia do que é um combinador.
1
@pst - Eu teria concordado 5 dias atrás, mas agora não posso discutir com John Hughes
Matt Fenwick

Respostas:

93

Não estou interessado na primeira definição - isso não me ajudaria a escrever um programa real (+1 se você me convencer que estou errado). Por favor me ajude a entender a segunda definição. Acho que mapear, filtrar e reduzir são úteis: eles me permitem programar em um nível mais alto - menos erros, código mais curto e mais claro.

As duas definições são basicamente a mesma coisa. O primeiro é baseado na definição formal e os exemplos que você dá são combinadores primitivos - os menores blocos de construção possíveis. Eles podem ajudá-lo a escrever um programa real na medida em que, com eles, você pode construir combinadores mais sofisticados. Pense em combinadores como S e K como a linguagem de máquina de um hipotético "computador combinatório". Os computadores reais não funcionam dessa forma, é claro, então na prática você geralmente terá operações de nível superior implementadas nos bastidores de outras maneiras, mas a base conceitual ainda é uma ferramenta útil para entender o significado daquelas de nível superior operações.

A segunda definição que você dá é mais informal e sobre o uso de combinadores mais sofisticados, na forma de funções de ordem superior que combinam outras funções de várias maneiras. Observe que, se os blocos de construção básicos são os combinadores primitivos acima, tudo o que é construído a partir deles é uma função de ordem superior e também um combinador. Em uma linguagem onde existem outros primitivos, no entanto, você tem uma distinção entre coisas que são ou não funções, caso em que um combinador é normalmente definido como uma função que manipula outras funções de uma maneira geral, ao invés de operar em qualquer funcionar as coisas diretamente.

Quais são mais exemplos de combinadores, como mapa, filtro?

Muitos para listar! Ambos transformam uma função que descreve o comportamento de um único valor em uma função que descreve o comportamento de uma coleção inteira. Você também pode ter funções que transformam apenas outras funções, como compô-las de ponta a ponta ou dividir e recombinar argumentos. Você pode ter combinadores que transformam operações de etapa única em operações recursivas que produzem ou consomem coleções. Ou todos os tipos de outras coisas, na verdade.

Quais combinadores as linguagens de programação costumam implementar?

Isso vai variar um pouco. Existem relativamente poucos combinadores completamente genéricos - principalmente os primitivos mencionados acima - então, na maioria dos casos, os combinadores terão alguma consciência de quaisquer estruturas de dados sendo usadas (mesmo se essas estruturas de dados forem construídas a partir de outros combinadores de qualquer maneira), nos quais Nesse caso, normalmente há um punhado de combinadores "totalmente genéricos" e, em seguida, quaisquer várias formas especializadas que alguém decidiu fornecer. Há um número ridículo de casos em que (versões generalizadas de) mapear, dobrar e desdobrar são suficientes para fazer quase tudo o que você deseja.

Como os combinadores podem me ajudar a projetar uma API melhor?

Exatamente como você disse, pensando em termos de operações de alto nível e a maneira como elas interagem, em vez de detalhes de baixo nível.

Pense na popularidade dos loops no estilo "para cada" sobre as coleções, o que permite abstrair os detalhes da enumeração de uma coleção. Na maioria dos casos, são apenas operações de mapeamento / dobra e, ao torná-lo um combinador (em vez de sintaxe embutida), você pode fazer coisas como pegar dois loops existentes e combiná-los diretamente de várias maneiras - aninhar um dentro do outro, faça um após o outro e assim por diante - apenas aplicando um combinador, em vez de manipular um monte de código.

Como faço para projetar combinadores eficazes?

Primeiro, pense em quais operações fazem sentido em quaisquer dados que seu programa usa. Em seguida, pense em como essas operações podem ser combinadas de forma significativa de maneiras genéricas, bem como em como as operações podem ser divididas em partes menores que são conectadas novamente. O principal é trabalhar com transformações e operações , não com ações diretas . Quando você tem uma função que apenas executa algumas funções complicadas de uma forma opaca e apenas produz algum tipo de resultado pré-digerido, não há muito o que fazer com isso. Deixe os resultados finais para o código que usa os combinadores - você quer coisas que o levem do ponto A ao ponto B, não coisas que esperam ser o início ou o fim de um processo.

O que são combinadores semelhantes em uma linguagem não funcional (digamos, Java), ou o que essas linguagens usam no lugar dos combinadores?

Ahahahaha. Engraçado você perguntar, porque os objetos são coisas de ordem superior em primeiro lugar - eles têm alguns dados, mas também carregam um monte de operações, e muito do que constitui um bom design OOP se resume a "objetos deveriam geralmente agem como combinadores, não como estruturas de dados ".

Portanto, provavelmente a melhor resposta aqui é que, em vez de coisas do tipo combinador, eles usam classes com muitos métodos getter e setter ou campos públicos, e lógica que consiste principalmente em fazer alguma ação predefinida opaca.

CA McCann
fonte
Ótima resposta! Vamos ver se entendi - os combinadores não são especiais, mas sim uma parte integrante da construção de um sistema de software sustentável? Ainda estou tentando digerir a declaração de "fragmentos de programa" de Hughes, no contexto de sua postagem.
Matt Fenwick
@Matt Fenwick: Tenho certeza de que ele está apenas usando "fragmentos de programa" para significar o tipo de transformações / operações de que estou falando, principalmente se for sobre "Setas", que enfatizam essa abordagem ainda mais fortemente. Além disso, eu não diria que é exatamente sobre construir sistemas sustentáveis - mais sobre construir sistemas que são altamente modulares e desacoplados de uma maneira particular , com os benefícios que isso acarreta.
CA McCann
Você conhece algum bom recurso para ler sobre o uso prático de combinadores? Muitíssimo obrigado!
Matt Fenwick,
@Matt Fenwick: Nada específico disso logo de cara, desculpe. No entanto, tende a ser uma abordagem natural para programas escritos em um estilo muito funcional, então apenas passar algum tempo com linguagens que encorajam fortemente isso (por exemplo, Haskell ou Clojure), e ver como o código limpo e idiomático é escrito nessa linguagem , é uma boa maneira de sentir o estilo.
CA McCann,