Y-комбинатор в D? - PullRequest
Новая
       78

Y-комбинатор в D?

8 голосов
/ 04 августа 2011

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

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

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

Ответы [ 4 ]

7 голосов
/ 04 августа 2011

Смотрите подробное объяснение здесь .

4 голосов
/ 04 августа 2011

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

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

3 голосов
/ 04 августа 2011

Мой общий 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).

3 голосов
/ 04 августа 2011

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

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

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

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

Если вам нужен пример с других языков, посмотрите эту страницу .

...