Skip to content

05.md

Latest commit

 

History

History
504 lines (351 loc) · 19.2 KB

05.md

File metadata and controls

504 lines (351 loc) · 19.2 KB

五、局部应用与柯里化

我们在寻求理解函数式编程方面已经走得很远了！我们学习了纯函数和 lambdas，并借助函数组合深入学习了 lambda 演算。我们现在知道如何从其他函数创建函数。

关于 lambda 演算的基础，还有一件事需要学习。除了功能组合，我们还可以通过两种操作从其他功能创建功能——curry 和 partial application。这将完成我们关于功能构建模块的讨论，并允许您继续使用功能进行设计。

本章将涵盖以下主题:

  • 什么是局部应用？
  • 如何在 C++ 中使用分部应用
  • 什么是拍马屁？
  • 如何在 C++ 中咖喱函数
  • 货币与局部应用的关系
  • 如何将讨好与功能组合相结合

技术要求

您将需要一个支持 C++ 17 的编译器。我用的是 GCC 7.3.0。

代码在Chapter05文件夹中的GitHub 上。它包括并使用doctest，这是一个单头开源单元测试库。你可以在它的 GitHub 存储库中找到它:https://github.com/onqtam/doctest。

部分应用和修改

如果您考虑 lambda 以及我们可以对其进行哪些操作来获得其他 lambda，您会想到两件事:

  • 一些关于组合两个 lambdas 的东西，我们在函数组合中看到过
  • 一些关于λ的参数，我们将在接下来访问

我们能用λ的参数做什么？有两件事:

  • 将一个有多个参数的 lambda 分解成多个有一个参数的 lambda，这个操作叫做curry
  • 通过将带有 N 参数的λ的参数绑定到一个值，获得带有 N-1 参数的λ，这种操作称为局部应用

由于即将变得明显的原因，这两个操作是相互关联的，所以我们将一起讨论它们。

部分应用

如果您有一个带有 N 参数的λ，部分应用意味着通过将一个参数绑定到一个值来获得另一个λ，从而获得一个带有 N-1 参数的新λ。例如，我们可以取一个add函数，做一个局部应用，将它的一个参数绑定到值1，得到一个increment函数。在伪 C++ 中，它看起来像这样:

auto add = [](const int first, const int second){return first + second;};
auto increment = partialApplication(add, /*first*/ 1); 
/* equivalent with 
auto increment = [](const int second){return 1 + second;}; 
*/

就这样！部分应用的想法相当简单。让我们看看 C++ 中的语法。

C++ 中的部分应用

部分应用的基本实现可以手动完成。我们可以简单地创建一个名为increment的 lambda，它调用通用的add函数，传递1作为第二个参数:

auto add = [](const int first, const int second) { return first + second; };
TEST_CASE("Increments using manual partial application"){
    auto increment = [](const int value) { return add(value, 1); };

    CHECK_EQ(43, increment(42));
}

这不是我们要找的整洁的操作，但是当你因为某种原因不能使用泛型方法时，它会很有用。

幸运的是，STL 在我们友好的头文件functional—函数bind中提供了一个更好的选择。它将函数、要绑定的值以及仅转发参数的占位符参数作为参数。为了通过调用bind获得increment函数，我们传入通用的addλ；第一个参数的参数值1；以及指定未绑定参数的占位符:

using namespace std::placeholders; // to allow _1, _2 etc.

TEST_CASE("Increments using bind"){
    // bind the value 1 to the first parameter of add 
    // _1 is a placeholder for the first parameter of the increment    
       lambda
    auto increment = bind(add, 1, _1); 

    CHECK_EQ(43, increment(42));
}

虽然方便，但你应该知道bind有很高的编译时开销。当这是一个问题时，您总是可以恢复到前面的选项——直接从另一个手动编写的 lambda 中调用更通用的 lambda。

当然，没有什么能阻止我们绑定这两个参数。由于程序员喜欢数字42，我将把addλ的两个参数都绑定到值1和41，以便获得另一个λ，number42 :

TEST_CASE("Constant using bind"){
   auto number42 = bind(add, 1, 41); 
   CHECK_EQ(42, number42());
}

bind语法有时可能有点棘手，所以让我们更详细地看看它。关键是要理解参数占位符指的是结果λ的参数，而不是初始λ的参数。

为了更清楚地说明这一点，我们来看一个添加了三个参数的 lambda 示例:

auto addThree = [](const int first, const int second, const int third){return first + second + third;};

TEST_CASE("Adds three"){
    CHECK_EQ(42, addThree(10, 20, 12));
}

如果我们想从我们的addThreeλ中获得另一个λ，addTwoNumbersTo10，通过将其第一个参数绑定到值10，那么bind的语法是什么？嗯，我们得到的λ，addTwoNumbersTo10，将接收两个参数。它们的占位符将用_1和_2表示。因此，我们需要告诉 bind，我们的初始λ的第一个参数addThree是10。第二个参数将从addTwoNumbersTo10转发，所以是_1。第三个论点也是从addNumbersTo10的第二个论点转发过来的，所以是_2。我们最终得到了这个代码:

TEST_CASE("Adds two numbers to 10"){
    auto addTwoNumbersTo10 = bind(addThree, 10, _1, _2);

    CHECK_EQ(42, addTwoNumbersTo10(20, 12));
}

让我们继续前进。我们想通过使用部分应用从我们的初始addThreeλ中获得另一个λaddTo10Plus20。得到的函数只有一个参数，_1。其他需要绑定的参数是价值观10和20。我们以下面的代码结束:

TEST_CASE("Adds one number to 10 + 20"){
    auto addTo10Plus20 = bind(addThree, 10, 20, _1);

    CHECK_EQ(42, addTo10Plus20(12));
}

如果我们想绑定第一个和第三个参数呢？现在应该清楚了，参数完全相同，但是它们的顺序在bind调用中发生了变化:

TEST_CASE("Adds 10 to one number, and then to 20"){
    auto addTo10Plus20 = bind(addThree, 10, _1, 20);

    CHECK_EQ(42, addTo10Plus20(12));
}

如果我们想绑定第二个和第三个参数呢？占位符移动了，但它仍然是结果函数的唯一参数，所以_1 :

TEST_CASE("Adds one number to 10, and then to 20"){
    auto addTo10Plus20 = bind(addThree, _1, 10, 20);

    CHECK_EQ(42, addTo10Plus20(12));
}

如果我们想对一个类方法做部分应用呢？

类方法的部分应用

bind函数允许我们对类方法进行部分应用，但是有一个问题——第一个参数必须是类的实例。在这个例子中，我们将使用一个AddOperation类来实现两个数字之间的简单相加:

class AddOperation{
    private:
        int first;
        int second;

    public:
        AddOperation(int first, int second): first(first), 
            second(second){}
        int add(){ return first + second;}
};

我们可以通过将AddOperation类的一个实例绑定到函数来创建一个新函数add:

TEST_CASE("Bind member method"){
    AddOperation operation(41, 1);
    auto add41And1 = bind(&AddOperation::add, operation); 

    CHECK_EQ(42, add41And1());
}

更有趣的是，更接近部分应用的概念，我们可以从调用方转发实例参数:

TEST_CASE("Partial bind member method no arguments"){
    auto add = bind(&AddOperation::add, _1); 
    AddOperation operation(41, 1);
    CHECK_EQ(42, add(operation));
}

如果方法接收参数，绑定也是可能的。例如，假设我们有另一个类实现AddToOperation:

class AddToOperation{
    private:
        int first;

    public:
        AddToOperation(int first): first(first) {}
        int addTo(int second){ return first + second;}
};

我们可以用类的一个实例来部分应用addTo，如下面的代码所示:

TEST_CASE("Partial application member method"){
    AddToOperation operation(41);
    auto addTo41 = bind(&AddToOperation::addTo, operation, _1); 

    CHECK_EQ(42, addTo41(1));
}

类方法的部分应用表明，在功能和面向对象世界之间移动是非常容易的。我们将在接下来的章节中看到如何利用这一点。在此之前，让我们庆幸的是，我们现在知道了什么是部分应用，以及如何在 C++ 中使用它。是时候谈谈它的近亲柯林了。

携带

让我们试着举几个软件开发界的名人，不要搜索互联网。有艾伦·图灵、阿达·洛芙莱斯(她有一个迷人的故事)、格蕾丝·赫柏、唐纳德·克努特、比约恩·斯特罗斯图普、格雷迪·布奇，可能还有许多其他人。他们中有多少人给你在行业中经常听到的不是一个，而是两个东西起了名字？对艾伦·图灵来说是这样，对图灵机和图灵测试来说肯定是这样，但对许多其他人来说就不是这样了。

因此，令人惊讶的是，哈斯克尔编程语言的名称和 currying 操作的名称来自同一个人——哈斯克尔·库里。哈斯克尔·库里是美国数学家和逻辑学家。他研究一种叫做组合逻辑的东西，这是部分函数式编程的基础。

但是什么是讨好呢？它如何连接到部分应用？

什么是拍马屁？

Currying 是将带有 N 个参数的函数分解为带有一个参数的 N 个函数的过程。我们可以通过变量捕获或部分应用来实现这一点。

让我们再来看看我们的addλ:

auto add = [](const int first, const int second) { return first +  
     second; };

TEST_CASE("Adds values"){
    CHECK_EQ(42, add(25, 17));
}

怎么分解？关键是 lambda 只是一个普通的值，这意味着我们可以从函数中返回它。因此，我们可以传入第一个参数，并返回一个 lambda，它捕获第一个参数并同时使用第一个和第二个参数。用代码比用文字更容易理解，所以这里是:

auto curryAdd = [](const int first){ 
    return [first](const int second){
        return first + second;
    };
};

TEST_CASE("Adds values using captured curry"){
    CHECK_EQ(42, curryAdd(25)(17));
}

让我们解开发生了什么:

  • 我们的curryAddλ返回一个λ。
  • 返回的 lambda 捕获第一个参数，接受第二个参数，并返回它们的总和。

这就是为什么，在调用它时，我们需要使用双圆括号。

但这看起来很熟悉，好像和部分应用有关。

柯里化和部分应用

让我们再次看看我们之前是如何进行部分应用的。我们通过部分应用add函数创建了一个increment函数:

TEST_CASE("Increments using bind"){
    auto increment = bind(add, 1, _1); 

    CHECK_EQ(43, increment(42));
}

但是，让我们来讨好我们的add功能:

auto curryAdd = [](const int first){ 
    return [first](const int second){
        return first + second;
    };
};

TEST_CASE("Adds values using captured curry"){
    CHECK_EQ(42, curryAdd(25)(17));
}

那么，increment就很好写了。你能看出是怎么回事吗？

incrementλ正好是curryAdd(1)，如下代码所示:

TEST_CASE("Increments value"){
    auto increment = curryAdd(1);

    CHECK_EQ(43, increment(42));
}

这向我们展示了函数式编程语言常用的一个技巧——默认情况下，函数可以被修改。在这样的语言中，编写以下内容意味着我们首先将add函数应用于first参数，然后将结果函数应用于second参数:

add first second

看起来我们好像在用参数列表调用函数；实际上，这是一个部分应用的课程功能。在这样的语言中，increment函数可以简单地通过编写以下内容从add中导出:

increment = add 1

反之亦然。由于 C++ 默认不做 curry，但是为局部应用提供了一个简单的方法，所以我们可以通过局部应用来实现 curry。不要使用值捕获返回复杂的 lambda，只需绑定到单个值并转发结果函数的单个参数:

auto curryAddPartialApplication = [](const int first){ 
    return bind(add, first, _1);
};

TEST_CASE("Adds values using partial application curry"){
    CHECK_EQ(42, curryAddPartialApplication(25)(17));
}

但是我们能走多远呢？用多个参数来讨好函数容易吗？

具有多个参数的 Currying 函数

在上一节中，我们已经看到了如何用两个参数来处理函数。当我们转到三个参数时，curried 函数也会增长。我们现在需要返回一个 lambda，它返回一个 lambda。同样，代码比任何解释都更容易理解，让我们看看:

auto curriedAddThree = [](const int first){
    return [first](const int second){ 
        return [first, second](const int third){
            return first + second + third;
        };
    };
}; 

TEST_CASE("Add three with curry"){
    CHECK_EQ(42, curriedAddThree(15)(10)(17));
}

那里似乎有一个递归结构。也许通过使用bind我们可以理解它？

原来没那么简单，但是有可能。我想写的是这样的:

bind(bind(bind(addThree, _1),_1), _1)

然而，addThree有三个参数，所以我们需要将它们绑定到某个东西上。下一个bind产生一个带有两个参数的函数，同样，我们需要将它们绑定到某个东西上。所以，它实际上是这样的:

bind(bind(bind(addThree, ?, ?, _1), ?,_1), _1)

问号应该用以前绑定的值替换，但这不适用于我们当前的语法。

但是，有一个解决方法。让我们用 N 参数实现多个在函数上使用bind的simpleCurryN函数，并将其简化为 N-1 。对于有一个参数的函数，结果就是下面的函数:

auto simpleCurry1 = [](auto f){
     return f;
 };

对于两个参数，我们绑定第一个并转发下一个:

auto simpleCurry2 = [](auto f){
    return [f](auto x){ return bind(f, x, _1); };
};

类似的操作适用于三个和四个参数:

auto simpleCurry3 = [](auto f){
     return [f](auto x, auto y){ return bind(f, x, y, _1); };
};
auto simpleCurry4 = [](auto f){
    return [f](auto x, auto y, auto z){ return bind(f, x, y, z, _1);  
};
};

这组simpleCurryN函数允许我们编写我们的curryN函数，这些函数用 N 参数取一个函数，并返回它的 curried 形式:

auto curry2 = [](auto f){
    return simpleCurry2(f);
 };

auto curry3 = [](auto f){
    return curry2(simpleCurry3(f));
 };

auto curry4 = [](auto f){
    return curry3(simpleCurry4(f));
};

让我们用两个、三个和四个参数在add lambdas 上测试它们，如下面的代码所示:

TEST_CASE("Add three with partial application curry"){
    auto add = [](int a, int b) { return a+b; };
    CHECK_EQ(3, curry2(add)(1)(2));

    auto addThreeCurryThree = curry3(addThree);
    CHECK_EQ(6, curry3(addThree)(1)(2)(3));

    auto addFour = [](int a, int b, int c, int d){return a + b + c +  
        d;};
    CHECK_EQ(10, curry4(addFour)(1)(2)(3)(4));
 }

很可能我们可以用一些富有想象力的模板来重写这些函数。我将把这个练习留给读者。

目前，重要的是要看到部分应用如何与货币挂钩。在默认情况下使用 curry 函数的编程语言中，部分应用非常容易——只需用更少的参数调用函数。对于其他编程语言，我们可以通过局部应用来实现 currying。

这些概念非常有趣，但你可能想知道它们在实践中是否有用。让我们看看如何使用这些技术消除重复。

使用部分应用和 currying 删除重复

程序员长期以来一直在寻找解决方案，以编写更少的代码，做更多的事情。函数式编程提出了一种解决方案——通过从其他函数派生来构建函数。

在前面的例子中，我们已经看到了这一点。由于increment是加法的特殊情况，我们可以从加法函数中推导出来:

auto add = [](const auto first, const auto second) { return first + second; };
auto increment = bind(add, _1, 1);

TEST_CASE("Increments"){
    CHECK_EQ(43, increment(42));
}

这对我们有什么帮助？好吧，想象一下，有一天你的客户进来告诉你*我们想使用另一种加法。*想象一下，必须在代码中到处搜索+和++ ，并找出实现新行为的方法。

相反，通过我们的add和increment功能，以及一点模板魔法，这就是我们能做的:

auto add = [](const auto first, const auto second) { return first + 
    second; };

template<typename T, T one>
auto increment = bind(add, _1, one);

TEST_CASE("Increments"){
    CHECK_EQ(43, increment<int, 1>(42));
}

我们的add方法不在乎得到什么类型，只要有一个加号运算符。我们的increment函数并不关心它使用什么类型以及add是如何工作的，只需要你为一个提供一个值。我们已经用三行代码完成了这项工作。我很少这样说代码，但是它不是很美吗？

当然，你可能会说，但是我们的客户并不想改变我们添加东西的方式。你会惊讶于你能用几个简单的操作符做多少事。让我给你举个简单的例子。实现一个游戏，其中一个角色在一条换行线上移动，如下图所示:

这不就是加法的修改版吗？我们来看看:

// Assume wrap at 20 for now
auto addWrapped = [](const auto first, const auto second) { return 
    (first + second)%20; };

TEST_CASE("Adds values"){
    CHECK_EQ(7, addWrapped(10, 17));
}

template<typename T, T one>
auto incrementWrapped = bind<T>(addWrapped, _1, one);

TEST_CASE("Increments"){
    CHECK_EQ(1, incrementWrapped<int, 1>(20));
}

嗯，这个代码看起来和add很像。也许我们可以用局部应用？让我们看看如何:

auto addWrapped = [](const auto first, const auto second, const auto 
    wrapAt) { return (first + second) % wrapAt; };

auto add = bind(addWrapped, _1, _2, 20);

template<typename T, T one>
    auto increment = bind<T>(add, _1, one);

TEST_CASE("Increments"){
    CHECK_EQ(1, increment<int, 1>(20));
}

我们的increment功能和之前完全一样，而我们的add功能已经成为了addWrapped的部分应用。值得注意的是，为了使代码更清晰，我仍然会更改函数名，以使其非常清楚函数在做什么。然而，主要的一点是，部分应用和 curry 帮助我们从代码中删除某些类型的重复，使我们能够将代码打开到我们在设计初始解决方案时不一定知道的实现。虽然我们可以用面向对象程序或模板做到这一点，但功能解决方案通过消除副作用来限制复杂性，并且只需要几行代码。这使得它成为设计程序时的一个有价值的选择。

摘要

看看我们对函数式编程的理解已经走了多远！我们了解了所有的构建模块——纯函数和 lambdas，以及我们可以在它们上面使用的操作——curry、部分应用和函数组合。我们还看到了操作之间是如何相互关联的，以及如何使用 currying 来实现部分应用，反之亦然。我们也看到了用 C++ 实现 currying 的方法。

但我们的探索才刚刚开始。下一站是——开始在更有趣的环境中使用这些结构。是时候解决这个难题了——我们到底该如何设计函数？

问题

  1. 什么是部分函数应用？
  2. 什么是拍马屁？
  3. currying 如何帮助我们实现部分应用？
  4. 如何在 C++ 中实现部分应用？