Todo o código pode ser representado como uma série de operações de Mapa / Filtro / Redução?

16

Recentemente, refatorei grandes pedaços de código e os substituímos por consultas Linq.

Removendo o viés de idioma - Linq é essencialmente um conjunto de operações de Mapa / Filtro e Redução que operam em uma sequência de dados.

Isso me fez pensar em quão longe eu teoricamente seria capaz de levar isso. Eu seria capaz de reescrever toda a base de código em uma série (ou até uma única) de operações Map / Filter e Reduce.

Infelizmente, sou pago para fazer coisas úteis, portanto não pude experimentar muito mais, mas não consigo pensar em nenhuma estrutura de código que não pudesse ser reestruturada como tal. O código lateral afetado pode ser tratado por mônadas. Até a saída está essencialmente mapeando endereços de memória para endereços de tela.

Existe algo que não possa ser (teoricamente) reescrito como uma consulta Linq?

computer-science Mongus Pong
fonte
Para árvores, veja aqui: stackoverflow.com/questions/250377/…
blueberryfields
Eu sempre pensei que "reduzir" é suficiente para garantir a conclusão de Turing (o mapa e o filtro podem ser implementados como operações de redução, não?) - pelo menos, a linguagem funcional equivalente a reduzir. Não sei o suficiente sobre o Linq para ter certeza de quão próxima a implementação segue a funcional.
blueberryfields
1
Não sei, mas uma regra geral é que qualquer coisa que alguém considere escrever todo o código será Turing completo. Mas o corolário disso é que ser Turing completo não é muito emocionante.
Psr
1
Eu concordo com o psr; Eu acho que uma resposta válida para essa pergunta precisa abordar a integridade de Turing. Uma prova pode tentar implementar uma máquina de Turing usando apenas essas operações.
Rob
Idle pensamento: Mesmo se permitirmos coisas sem sentido my_list.map(_ignored => a copy of my_list), parece que o uso do espaço de um programa desse tipo é limitado por algum polinômio (dependendo da duração do programa). Então, esse idioma certamente não poderia computar problemas que não estão no PSPACE. No entanto, como muitos problemas no PSPACE são considerados intratáveis, para não falar de classes maiores, isso pode não ser uma restrição muito séria.

Respostas:

1

É chamado de programação funcional e é considerado por muitos como um conceito fundamental. Aqui está uma boa introdução sobre o Joel On Software . A resposta mais técnica é não, atualmente não existe uma maneira conhecida de fazer perguntas ao seu computador (de uma maneira bem definida) que não possam ser respondidas através do cálculo do SKI.

JP Mcgrady
fonte
1
Há muito mais na programação funcional do que as funções map, filtere reduce(isso triplicará se ignorarmos a integridade e usarmos linguagens FP práticas). De fato, eles são bastante gerais e, portanto, geralmente úteis, mas na verdade são aplicações muito simples de programação funcional. O cálculo lambda mínimo desencapado pode definir essas funções entre muitas outras, e não o contrário.
"aqui está uma boa introdução ao Joel On Software" - que consegue confundir o Fortran com o Basic, para que eu não confie muito em outros fatos.
quant_dev