Combinator titik tetap golf

9

Tulis kombinator titik tetap dalam karakter sesedikit mungkin, dalam bahasa pilihan Anda.

  • bentuk bebas ( mis. , apa pun yang terpendek): seluruh program, fungsi aktual, cuplikan kode
  • Anda tidak boleh menggunakan perpustakaan standar Anda jika ada
  • Namun Anda dapat mengekstraknya dari fungsi tingkat tinggi lainnya, Anda lebih suka melakukannya daripada membangunnya dari basis

Harap sertakan faktorial rekursif atau Fibonacci yang menggunakannya sebagai demo.

Dalam pertanyaan ini, referensi-diri dapat diterima, tujuannya hanya untuk menghapusnya dari fungsi rekursif yang akan diterapkan.

JB
sumber
Apakah implementasi bahasa malas oke? (Maukah Anda menerima (define Y(lambda(f)(f(Y f))))?)
Eelvex
Setiap implementasi yang dapat Anda peragakan dengan salah satu contoh yang diminta tidak masalah.
JB
1
Jika saya tidak salah, secara tegas, istilah "Y combinator" merujuk secara khusus pada combinator fixpoint tunggal yang ditemukan oleh Haskell Curry, λ (λx.f (xx)) (λx.f (xx)).
Joey Adams
@Eelvex: Jelas kedua jawaban sejauh ini (termasuk jawaban OP sendiri) menggunakan cara curang, jadi, saya kira itu membuatnya baik-baik saja. :-P Secara pribadi, saya lebih suka menggunakan pendekatan @ Joey dan mengatakan bahwa hanya kombinator Y (non-referensial) nyata yang akan melakukannya. ;-)
Chris Jester-Young
@ Chris: Ya ampun. Itulah yang ada dalam pikiran saya pada awalnya, dan kemudian saya ... lupa di sepanjang jalan. Agak terlambat untuk berubah sekarang, kita harus membuka pertanyaan lain.
JB

Jawaban:

13

Haskell: 10 karakter

y f=f$y f

Contoh penggunaan untuk membuat definisi rekursif dari faktorial atau n-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]

Meskipun demikian, cara yang lebih umum untuk digunakan yadalah dengan menghasilkan urutan ini secara langsung, daripada sebagai fungsi:

> 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]

Tentu saja, dengan Haskell, ini seperti menembak ikan dalam tong! The Data.Functionperpustakaan memiliki fungsi ini, disebut fix, meskipun dilaksanakan agak lebih rinci.

MtnViewMark
sumber
4

Perl, 37

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

Demonstrasi faktorial:

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

Peragaan 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
sumber
3

GNU C - 89 karakter

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

Contoh:

#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
sumber
1

k2, 12 char

Implementasi self-referensial yang jelas adalah yang terpendek. Ini adalah tanda desain bahasa yang baik. Sayangnya, K tidak malas, jadi kami hanya bisa mengatur nilai berdasarkan panggilan.

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

Definisi ini juga harus bekerja di k4 dan q tanpa masalah, meskipun saya menganggap k2 untuk contoh di bawah ini.

  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

18 karakter yang lebih sederhana memungkinkan kita secara tepat menuliskan (λx. x x) (λxyz. y (x x y) z)dalam K.

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

Mungkin suatu hari nanti (k7?), Ini bisa terlihat seperti Y:{x Y x}.

algoritme hiu
sumber
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]))

Kredit: https://gist.github.com/WoLpH/17552c9508753044e44f

Labo
sumber
Python 3 memiliki filter. Maaf, saya lupa menandai komentar itu sebagai lelucon
Cyoce
Filter Python 3 mengembalikan objek filter dan bukan daftar. Akan kurang mudah dibaca atau pythonic untuk menggunakan filter.
Labo
itu akan kurang Pythonic, tetapi lebih sejalan adalah pemrograman fungsional , yang merupakan poin saya
Cyoce