DのY-コンビネータ？

Question

私は、（私はのソートは、スキームにそれを理解する）とD 2.0でそれを実装Yコンビネータよりよく学ぶことをしようとしていると私はかなり惨めに失敗しています：

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の名前を自分に渡す必要があるので、とにかくうまくいかないでしょうか？

しかし、私はどのようにDにY-コンビネータを実装するのですか？

Answer 1

詳細な説明hereを参照してください。

Answer 2

私はDを知りませんが、ほとんどの言語では、非再帰を実装しようとすると関数の型に問題が発生します（まだコードにY-Combinatorはありません）。型を複数の部分に分割し、このようにして型への再帰を取得することで、通常の方法を実現できます。他の言語から

いくつかの例：Cの一

• 通常の関数ポインタを含む構造体を書き込みます。この構造体は、引数として使用できます。

• OCamlでは、関数型をラップするバリアント型を追加します。この場合も、型の分離が可能になり、型の再帰が可能になります。

他の言語の例が必要な場合は、this pageをご覧ください。

Answer 3

型付きの自己参照を扱う関数は宣言することができない（最後に私がチェックした）ことはD（およびC/C++）の既知の制限です。

意味的またはアーキテクチャ的な意味ではなく、構文の制限（関数のプロトタイプの長さは無限）または命名規則（同じ問題ですが名前のマングリング）になります。

Answer 4

Dでの私の一般的なYコンビネータ：

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))); 
} 

私は階乗関数の自明な再帰的定義から始まり、私のコードは次のように見えたまでそれを修正。無限型の問題は型ラッパー（構造体F）で回避されています。