Combinador de pontos fixos para golfe

9

Escreva um combinador de pontos fixos no menor número de caracteres possível, no idioma de sua escolha.

  • forma livre ( ou seja , o que for mais curto): programa inteiro, função real, trecho de código
  • você não pode usar a biblioteca padrão, se houver uma
  • no entanto, você pode extraí-lo de outras funções de alto nível que preferiria fazer do que construí-lo a partir das bases

Inclua um fatorial recursivo ou Fibonacci que o utilize como demonstração.

Nesta questão, a auto-referência é aceitável, o objetivo é apenas removê-lo da função recursiva à qual ele se aplicará.

JB
fonte
Uma implementação de linguagem lenta é aceitável? (Você aceitaria (define Y(lambda(f)(f(Y f))))?)
Eelvex
Qualquer implementação que você possa demonstrar com um dos exemplos solicitados está ok.
JB
11
Se não me engano, estritamente falando, o termo "combinador Y" refere-se especificamente a um único combinador de fixpoint descoberto por Haskell Curry, λf. (Λx.f (xx)) (λx.f (xx)).
Joey Adams
@Eelvex: Obviamente, ambas as respostas até agora (incluindo a resposta do próprio OP) usam a maneira de trapacear, então, acho que isso faz tudo bem. :-P Pessoalmente, prefiro seguir a abordagem de @ Joey e dizer que somente o combinador Y real (não-auto-referencial) servirá. ;-)
Chris Jester-Young
@ Chris: Oh meu. Era isso que eu tinha em mente inicialmente, e então eu ... esqueci ao longo do caminho. É meio tarde demais para mudar agora, teremos que abrir outra pergunta.
JB

Respostas:

13

Haskell: 10 caracteres

y f=f$y f

Exemplo de uso para criar definições recursivas de fatorial ou enésimo-Fibonacci:

> map ( y(\f n->if n <= 1 then 1 else n*f(n-1)) ) [1..10]
[1,2,6,24,120,720,5040,40320,362880,3628800]

> map ( y(\f n->if n <= 1 then 1 else f(n-1)+f(n-2)) ) [0..10]
[1,1,2,3,5,8,13,21,34,55,89]

Porém, uma maneira mais comum de usar yseria gerar essas seqüências diretamente, e não como funções:

> take 10 $ y(\p->1:zipWith (*) [2..] p)
[1,2,6,24,120,720,5040,40320,362880,3628800]

> take 11 $ y(\f->1:1:zipWith (+) f (tail f))
[1,1,2,3,5,8,13,21,34,55,89]

Claro, com Haskell, isso é um pouco como pescar em um barril! A Data.Functionbiblioteca possui essa função, chamada fix, embora implementada de maneira um pouco mais detalhada.

MtnViewMark
fonte
4

Perl, 37

sub f{my$s=$_[0];sub{$s->(f($s),@_)}}

Demonstração fatorial:

sub fact {
  my ($r, $n) = @_;
  return 1 if $n < 2;
  return $n * $r->($n-1);
}
print "Factorial $_ is ", f(\&fact)->($_), "\n" for 0..10;

Demonstração de Fibonacci:

sub fib {
  my ($r, $n) = @_;
  return 1 if $n < 2;
  return $r->($n-1) + $r->($n-2);
}
print "Fibonacci number $_ is ", f(\&fib)->($_), "\n" for 0..10;
JB
fonte
3

GNU C - 89 caracteres

#define fix(f,z)({typeof(f)__f=(f);typeof(__f(0,z))x(typeof(z)n){return __f(x,n);}x(z);})

Exemplo:

#define lambda2(arg1, arg2, expr) ({arg1;arg2;typeof(expr)__f(arg1,arg2){return(expr);};__f;})

int main(void)
{
    /* 3628800 */
    printf("%ld\n", fix(lambda2(
        long factorial(int n), int n, 
            n < 2 ? 1 : n * factorial(n-1)
        ), 10));

    /* 89 */
    printf("%ld\n", fix(lambda2(
        long fibonacci(int n), int n, 
            n < 2 ? 1 : fibonacci(n-1) + fibonacci(n-2)
        ), 10));

    return 0;
}
Joey Adams
fonte
1

k2, 12 caracteres

A implementação auto-referencial óbvia é a mais curta. Este é um sinal de bom design de linguagem. Infelizmente, K não é preguiçoso; portanto, podemos gerenciar apenas a chamada por valor.

Y:{x[Y[x]]y}

Essa definição também deve funcionar em k4 e q sem problemas, embora eu assuma k2 nos exemplos abaixo.

  Y:{x[Y[x]]y}
  fac: {[f;arg] :[arg>0; arg*f[arg-1]; 1]}
  Y[fac] 5
120
  fib: {[f;arg] :[arg>1; f[arg-1] + f[arg-2]; arg]}
  Y[fib]' !10
0 1 1 2 3 5 8 13 21 34

Uns 18 caracteres mais modestos nos permitem transcrever exatamente (λx. x x) (λxyz. y (x x y) z)para K.

{x[x]}{y[x[x;y]]z}

Talvez um dia (k7?), Isso possa parecer Y:{x Y x}.

algoritmshark
fonte
0

Python 3, 30 bytes

Y=lambda f:lambda a:f(Y(f))(a)

Demo:

Y=lambda f:lambda a:f(Y(f))(a)
quicksort = Y(
lambda f:
    lambda x: (
        f([item for item in x if item < x[0]])
        + [y for y in x if x[0] == y]
        + f([item for item in x if item > x[0]])
    ) if x
    else []
)
print(quicksort([1, 3, 5, 4, 1, 3, 2]))

Créditos: https://gist.github.com/WoLpH/17552c9508753044e44f

Labo
fonte
Python 3 tem filtro. Também Me desculpe, eu negligenciado para marcar esse comentário como uma piada
Cyoce
O filtro do Python 3 retorna um objeto de filtro e não uma lista. Seria menos legível ou pitônico usar filtro.
Labo 06/06
seria menos Pythonic, mas mais em linha era funcional de programação , que era o meu ponto
Cyoce