Гольф-комбинатор с фиксированной точкой

9

Напишите комбинатор с фиксированной точкой, используя как можно меньше символов на выбранном вами языке.

  • произвольная форма ( т. е. самое короткое): вся программа, реальная функция, фрагмент кода
  • вы не можете использовать вашу стандартную библиотеку, если она есть
  • однако вы можете извлечь его из других высокоуровневых функций, если захотите, а не создавать его из баз

Пожалуйста, включите рекурсивный факториал или Фибоначчи, который использует его в качестве демонстрации.

В этом вопросе допустима ссылка на себя, цель - исключить ее из рекурсивной функции, к которой она будет применяться.

JB
источник
Реализация с ленивым языком в порядке? (Вы согласны (define Y(lambda(f)(f(Y f))))?)
Eelvex
Любая реализация, которую вы можете продемонстрировать на одном из запрошенных примеров, в порядке.
JB
1
Если я не ошибаюсь, строго говоря, термин «Y комбинатор» относится конкретно к одному комбинатору с фиксированной точкой, обнаруженному Хаскеллом Карри, λf. (Λx.f (xx)) (λx.f (xx)).
Джои Адамс
@Eelvex: Очевидно, что оба ответа (включая собственный ответ ОП) используют мошеннический способ, так что, я думаю, с этим все в порядке. :-P Лично я предпочел бы пойти с подходом @ Джоуи и сказать, что подойдет только реальный (не само-ссылочный) Y-комбинатор. ;-)
Крис Шестер-Янг
@ Крис: О боже. Это то, что я имел в виду, а потом я ... забыл по пути. Сейчас уже слишком поздно что-либо менять, нам придется открыть еще один вопрос.
JB

Ответы:

13

Хаскель: 10 персонажей

y f=f$y f

Пример использования для создания рекурсивных определений факториала или n-го Фибоначчи:

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

Тем не менее, более распространенным способом использования yбудет генерирование этих последовательностей напрямую, а не в виде функций:

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

Конечно, с Haskell это немного похоже на отстрел рыбы в бочке! Эта Data.Functionфункция называется в библиотеке fix, хотя и реализована более многословно.

MtnViewMark
источник
4

Perl, 37

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

Факториальная демонстрация:

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

Демонстрация Фибоначчи:

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
источник
3

GNU C - 89 символов

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

Пример:

#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;
}
Джои Адамс
источник
1

к2, 12 символов

Очевидная самоссылочная реализация является самой короткой. Это признак хорошего языкового дизайна. К сожалению, K не ленив, поэтому мы можем управлять только по стоимости.

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

Это определение также должно работать в k4 и q без проблем, хотя я предполагаю k2 для примеров ниже.

  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 символов позволяют нам точно транскрибировать (λx. x x) (λxyz. y (x x y) z)в К.

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

Может быть, когда-нибудь (k7?) Это может выглядеть так Y:{x Y x}.

algorithmshark
источник
0

Python 3, 30 байт

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

Демо:

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

Кредиты: https://gist.github.com/WoLpH/17552c9508753044e44f

Labo
источник
Python 3 имеет фильтр. Кроме того, мне жаль, что я пренебрег этим комментарием как шуткой
Cyoce
Фильтр Python 3 возвращает объект фильтра, а не список. Было бы менее читабельным или питонным использовать фильтр.
Labo
это было бы менее Pythonic, но больше было функциональное программирование , что было моей точкой зрения
Cyoce