Y-combinator in D?

Question

Я пытаюсь выучить Y-комбинатор лучше (я рода понимаю на схеме) и реализовать его в D 2.0, и я неудачу довольно плачевно:

auto fact = delegate(uint delegate(uint) recurse) 
{ 
    return delegate(uint n) 
    { 
     return n > 1 ? n * recurse(n - 1) : 1; 
    }; 
}; 

fact(fact)(5); 

Это не работа, по той очевидной причине, что я не могу пройти fact до fact (каков был бы его тип?). И кроме того, мне все еще нужно имя fact, чтобы передать ему, так что это не сработает, правда?

Но ... как я могу реализовать Y-комбинатор в D?

Answer 1

См. Подробное объяснение here.

Answer 2

Я не знаю D, но с большинством языков у вас появятся проблемы с типом функции при попытке реализовать нерекурсию (в коде еще нет Y-Combinator). Обычный способ может быть достигнут путем разделения типов на несколько частей и таким образом получения рекурсии в тип.

Некоторые примеры из других языков:

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

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

Если вы хотите, чтобы какой-либо пример с других языков, посмотрите на this page.

Answer 3

Это ограниченное знание D (и C/C++), что функции, которые обрабатывают типизированные ссылки на себя, невозможны (последний раз, когда я проверил), чтобы объявить.

Я нахожу это ироничным, потому что это означает ограничение синтаксиса (длина прототипа функции бесконечна) или соглашение об именовании (та же проблема, но с изменением имени), а не что-либо семантическое или архитектурное.

Answer 4

Моего общий Y комбинатор в D:

import std.stdio, std.algorithm, std.range; 
auto Y(R,T...)(R delegate(T) delegate (R delegate(T)) f){ 
    struct F{R delegate(F,T) f;}; 
    return (R delegate(T)delegate(F) a){return a(F((F b,T i){return f(a(b))(i);})); 
    }((F b){return (T n){return b.f(b,n);};}); 
} 
void main(){ 
    auto factorial=Y((long delegate(long) self){return (long i){return i?self(i-1)*i:1;};}); 
    auto fibonacci=Y((int delegate(int) self){return (int i){return i<2?i:self(i-1)+self(i-2);};}); 
    auto ackermann=Y((long delegate(long,long) self){return (long n,long m){return n?m?self(n-1,self(n,m-1)):self(n-1,1):m+1;};}); 
    writeln(map!factorial(iota(0,20))); 
    writeln(map!fibonacci(iota(0,20))); 
    writeln(map!((a){return ackermann(a%4,a/4);})(iota(0,20))); 
} 

Я начал с тривиальным рекурсивным определением функции факториала и модифицировал его, пока мой код не выглядел так. Бесконечная проблема типа обрабатывается с помощью обертки типа (struct F).