Y-Combinator Exemplo Prático

Question

Estive lendo um pouco ultimamente sobre programação funcional e eu estou tentando Grokar o Y-Combinator. Eu entendo que você pode usar o Y-Combinator para implementar eficazmente a recursividade em uma linguagem que faz recursão não suporte diretamente. No entanto, todas as línguas que eu sou provavelmente já usam suporta recursão, então eu não sei como seria útil para usar o Y-Combinator para isso.

Existe um melhor exemplo prático do uso do Y-Combinator que eu estou perdendo? Tem alguém realmente usou um no código de produção real? Ou está usando o Y-Combinator realmente apenas um exercício acadêmico alucinante (embora um muito se refrescar).

Answer 1

Eu vou discordar de outras respostas: O ponto fixo (Y) combinator faz ter aplicações práticas , mas é preciso uma mente muito imaginativa para encontrá-los . Como Bruce McAdam. Aqui está o resumo de seu papel que cerca de quebra-lo até :

O elemento de combinação Y para calcular pontos fixos pode ser expressa em ML padrão. Ele é frequentemente utilizado como um exemplo do poder de funções de ordem superior, mas não é geralmente considerado como uma construção de programação útil. Aqui, nós olhamos como uma técnica de programação baseada na combinator e invólucros Y pode dar aos programadores um nível de controle sobre o funcionamento interno de funções não seria possível sem reescrever e recompilar o código. Como um experimento, o tipo-inferência algoritmo W é implementado usando esta técnica, de modo que as mensagens de erro são produzidos com um mínimo de interferência para o algoritmo. O código para este exemplo de programa ilustra a utilidade genuína dos conceitos e a facilidade com que eles podem ser aplicados. Um número de outras técnicas de aplicação e as possíveis aplicações são também discutidos, incluindo a utilização de funções de ordem superior para simular a utilização de excepções e continuações.

É um grande papel; Quem estiver interessado em programação funcional provavelmente vai gostar de lê-lo.

Answer 2

Você pode verificar este post bacana na implementação do Y Combinator em C #: recursiva Lambda Expressions , pode ajudar você a entender a ideia melhor.

Você pode querer verificar para fora alguns bons artigos sobre Wikipedia: ponto fixo combinator e < a href = "http://en.wikipedia.org/wiki/Fixed-point_theorem#Fixed_point_theorems_in_discrete_mathematics_and_theoretical_computer_science" rel = "nofollow noreferrer"> ponto fixo teoremas

Como diz Nathan, muitas técnicas funcionais estão relacionados com o Combinator Y e são úteis, por isso mantê-la! Y é realmente útil porque permite que você entenda o seu código melhor, mas eu não acho que é particularmente útil para descrever como isso ajuda.

Answer 3

Você pode pensar no combinator como a máquina virtual que roda a sua função, que você descreve por um (= função de ordem superior) funcional não-recursiva.

Às vezes, seria bom ter esta combinator sob controle do programa, fazer coisas semelhantes como programação orientada a aspectos (memoizing, detecção, ...), mas nenhuma linguagem de programação eu conheço o permite. Provavelmente seria demasiado pesado a maior parte do tempo e / ou muito difícil de aprender.

Answer 4

Outros podem me corrija se eu estiver errado, mas eu tenho certeza que a combinator Y é estritamente acadêmica. Pense nisso: para implementá-lo suas necessidades linguísticas para suportar funções de ordem superior, mas não recursão. Há apenas uma língua que eu sei como essa:. Cálculo lambda

Então, até que nossas máquinas mudar de máquinas de Turing para execução no cálculo lambda, o Combinator Y será estritamente acadêmica.

Nota: outras técnicas funcionais relacionadas com o Combinator Y são útil, então mantê-la. Compreender o Combinator Y vai ajudar você a entender continuações, avaliação preguiçosa, etc.

Answer 5

let sprite = pipe4 sprite_start blanks (manyTill attribute newline) blanks (fun a b c _ -> Sprite(a,c))

let sprites = 
    let rec y f x = f (y f) x // The Y Combinator
    //let rec sprites_up = many1Indents sprite sprites_up |>> (fun x -> SubSprites x) // Does not work.
    let sprites_up = y (fun f -> many1Indents sprite f |>> (fun x -> SubSprites x))
    many1Indents sprite sprites_up

Aqui está um exemplo do compilador para uma biblioteca de jogos pequeno eu estou fazendo no F #. Mais especificamente, no exemplo acima eu preciso ter a sprites_up recursivamente chamar-se de outra forma o analisador recuo não iria funcionar corretamente.

Sem a Y Combinator, eu não poderia ter feito o analisador corretamente e teria tido que recorrer a escrever algo como isto:

let sprites_up4 = many1Indents sprite error |>> (fun x -> SubSprites x) 
let sprites_up3 = many1Indents sprite sprites_up4 |>> (fun x -> SubSprites x) 
let sprites_up2 = many1Indents sprite sprites_up3 |>> (fun x -> SubSprites x) 
let sprites_up1 = many1Indents sprite sprites_up2 |>> (fun x -> SubSprites x) 
let sprites_up = many1Indents sprite sprites_up1 |>> (fun x -> SubSprites x) 

não teria sido uma grande solução, o Y Combinator realmente me salvou lá. Certamente não foi a primeira coisa que me veio à mente embora.