26

C++ で無名階乗関数を作成し、コードを g++4.9.2 でコンパイルしました。それはうまくいきます。ただし、関数の型がわかりません。

#include<iostream>
#include<functional>
using std::function;
int main()
{
    //tested at g++ 4.9.2
    //g++ -std=c++1y -o anony anony.cpp
    auto fac = [](auto self,auto n)->auto{
        if(n < 1)
            return 1;
        else 
            return n * self(self,n-1);
    };
    std::cout<<fac(fac,3)<<std::endl;//6
    return 0;
}

それで、私は疑問に思います: と の型は何facですかself? C++ コードを Haskell に変換しただけでは、無限の型が含まれているためコンパイルできません。

fac2 self 0 = 1
fac2 self n = n * (self self $ n-1)

そして、それを回避する再帰型の作業を定義する必要があります。

data Y a = Y ((Y a)->a->a)
fac2 self 0 = 1
fac2 self n = n * ((applY self self) (n-1))
    where applY (Y f1) f2 = f1 f2
fact2 = fac2 $ Y fac2

では、なぜ g++ は正確に正しい型のfac関数を取得できるのでしょうか? また、g++ はその関数をどのような型だと考えているのfacでしょうか?

4

3 に答える 3

27

C++facは実際には関数ではなく、メンバー関数を持つ構造体です。

struct aaaa // Not its real name.
{
    template<typename a, typename b>
    auto operator()(a self, b n) const
    { 
    }
};

オーバーロードされた呼び出し演算子は、「ラムダ関数」を実装するために C++ が実行するトリックの一部を隠します。

「呼び出す」facと、何が起こるか

fac.operator() (fac, 3);

したがって、関数への引数は関数自体ではなく、それをメンバーとして持つオブジェクトです。
この影響の 1 つは、関数の型 (つまり、 の型) が関数自体operator()の型に含まれないことです。 ( の型は、関数を定義する構造体です。)operator()
self

これが機能するためにテンプレート部分は必要ありません。facこれは「関数」の非汎用バージョンです。

struct F
{
    int operator()(const F& self, int n) const
    { 
        // ...
    }
};

F fac;
fac(fac, 3);

テンプレートを保持し、名前を に変更するoperator()とapplY:

// The Y type
template<typename a>
struct Y
{
    // The wrapped function has type (Y<a>, a) -> a
    a applY(const Y<a>& self, a n) const
    { 
        if(n < 1)
            return 1;
        else 
            return n * self.applY(self, n-1);
    }
};

template<typename a>
a fac(a n)
{
    Y<a> y;
    return y.applY(y, n);
}

作業中の Haskell プログラムと C++ プログラムは非常に似ていることがわかります。相違点は主に句読点です。

対照的に、Haskell では

fac2 self 0 = 1
fac2 self n = n * (self self $ n-1)

self は関数であり、fac2の型は

X -> Int -> Int

いくつかのためにX。は関数であり、Int であるため、
の型もです。selfself self $ n-1selfX -> Int -> Int

しかし、何ができXますか？それ自体
の型と同じでなければなりません。 しかし、それは の型が ( の代わりに) であることを意味します:selfX -> Int -> Int
selfX

(X -> Int -> Int) -> Int -> Int

そのため、タイプXも

(X -> Int -> Int) -> Int -> Int

soselfの型は

((X -> Int -> Int) -> Int -> Int) -> Int -> Int

など、無限に。
つまり、Haskell では型は無限になります。

Haskell のソリューションでは、基本的に、C++ がメンバー関数を使用してその構造を介して生成する必要なインダイレクションを明示的に導入しています。

于 2015-01-07T09:00:19.320 に答える
15

他の人が指摘したように、ラムダはテンプレートを含む構造として機能します。問題は、なぜ Haskell は自己適用を型付けできないのに、C++ は型付けできるのでしょうか?

その答えは、C++ テンプレートと Haskell ポリモーフィック関数の違いにあります。これらを比較してください：

-- valid Haskell
foo :: forall a b. a -> b -> a
foo x y = x

// valid C++
template <typename a, typename b>
a foo(a x, b y) { return x; }

それらはほぼ同等に見えるかもしれませんが、実際にはそうではありません。

Haskell の型が上記の宣言をチェックするとき、定義がどの型に対しても型安全であることをチェックしますa,b。つまり、a,b任意の 2 つの型で置換する場合、関数は明確に定義されている必要があります。

C++ は別のアプローチに従います。テンプレートの定義では、 の置換a,bが正しいかどうかはチェックされません。このチェックは、テンプレートの使用時点、つまりインスタンス化の時点まで延期されます。+1ポイントを強調するために、コードに a を追加しましょう。

-- INVALID Haskell
foo :: forall a b. a -> b -> a
foo x y = x+1

// valid C++
template <typename a, typename b>
a foo(a x, b y) { return x+1; }

Haskell 定義は型チェックを行いません: が任意の型であるx+1場合に実行できる保証はありません。x代わりに、C++ コードは問題ありません。のいくつかの置換がa間違ったコードにつながるという事実は、現在は関係ありません。

このチェックを延期すると、「無限に型指定された値」が大まかに許可されます。PythonやSchemeなどの動的言語は、これらの型エラーを実行時までさらに延期し、もちろん自己適用を問題なく処理します。

于 2015-01-07T10:40:07.067 に答える
6

次の式auto fac =はラムダ式であり、コンパイラはそこからクロージャ オブジェクトを自動的に生成します。そのオブジェクトの型は一意であり、コンパイラだけが知っています。

N4296 から、§5.1.2/3 [expr.prim.lambda]

ラムダ式の型(クロージャ オブジェクトの型でもあります) は、名前のない一意の非共用体クラス型 —クロージャ型と呼ばれます — のプロパティについては、以下で説明します。このクラス型は、集約 (8.5.1) でもリテラル型 (3.9) でもありません。クロージャー型は、対応するlambda-expressionを含む最小のブロック スコープ、クラス スコープ、または名前空間スコープで宣言されます。

このため、2 つの同一のラムダ式でも異なる型を持つことに注意してください。例えば、

auto l1 = []{};
auto l2 = []{}; // l1 and l2 are of different types

ラムダ式は C++14 の汎用ラムダであり、コンパイラによって次のようなクラスに変換されます。

struct __unique_name
{
    template<typename Arg1, typename Arg2>
    auto operator()(Arg1 self, Arg2 n) const
    { 
        // body of your lambda
    }
};

Haskell の部分についてコメントすることはできませんが、再帰式が C++ で機能する理由はfac、各呼び出しで単にクロージャ オブジェクト インスタンス ( ) のコピーを渡しているからです。テンプレートであることは、他のoperator()方法で名前を付けることができない場合でも、ラムダのタイプを推測できます。

于 2015-01-07T08:00:27.107 に答える