行者无畏
20220925 函数式编程
明昧 Lv7
  2022-09-25 19:35:45   2024-06-19 19:59:53    

20220925 函数式编程

第一次了解

一、函数式编程

与 OOP 不同，函数式编程首先将程序分成输入、中间函数以及输出三个模块。

其中，

输入模块负责将各种输入设备中的数据转化成方便处理的数据结构。

中间函数处理输入数据，输出处理后的数据或状态。

输出模块再将处理后的内存数据交给各种输出设备。

其中，中间函数要求是纯函数，即没有副作用（不会改变函数帧以外的内存数据）且对相同输入参数永远给出相同返回值的函数。一个复杂的纯函数可以通过更简单的纯函数组合而成。纯函数的特点允许程序员自由调用它们而不必担心环境的变化。

除了函数组合意外，函数式编程还支持对纯函数的 partial application 和 currying，这很好的避免了代码的重复。

1.1 创建纯函数

类成员函数

由于纯函数不会改变类成员变量，所以要么直接声明成 static 要么用 const 修饰函数。

1
2
3
4
5
6
7
8
9
10
11
12
//  传值
static int increment(const int value);
int increment(const int value) const;
// 传引用
static int increment(const int& value);
int increment(const int& value) const;
// 传指针，形参不必是指针常量
static const int* increment(const int* value);
const int* increment(const int* value) const;
// 传指针的引用
static const int* increment(const int* const& value);
const int* increment(const int* const & value) const;

独立函数

对于独立的非成员函数，static 和修饰函数的 const 关键字就可以去掉了。

Lambda 表达式

Lambda 表达式本质上编译器在编译期间创建的一个类。它将捕获到的变量作为成员变量并重载了"()" 算符实现Lambda函数体。

1
2
3
4
5
6
7
8
// 捕获值，改变捕获的变量会报错
int var = 1;
auto increment = [var](const int p){return var+p;}; // 捕获指定变量
auto increment = [=](const int p){return var+p;}; // 捕获所有变量
// 尽量避免捕获引用
int var = 1;
auto increment = [&var](const int p){return var + p;};
auto increment = [&](const int p){return var+p;};

1.2 Partial Application 与 Currying

Partial Application

就是通过固定部分函数参数的值来实现新的函数的意思，

在 C++ 中主要靠 functional 库中的 bind() 函数来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <functional>
using namespace std;
using namespace std::placeholders;

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

auto addTwoNumbersTo10 = bind(addThree,10,_1,_2);
auto addTo10Plus20 = bind(addThree,10,20,_1);
#include "doctest.h"
TEST_CASE("Partial Application"){
    CHECK_EQ(60,addTwoNumbersTo10(20,30));
    CHECK_EQ(60,addTo10Plus20(30));
}

Currying

就是将 f(auto first, auto second,auto third …)

写成 f(auto first)(auto second)(auto third)… 的意思。

主要通过在 Lambda表达式中返回 Lambda 表达式来实现。

与 Partial Application 相比，Currying 虽然缺少了指定参数顺序的灵活性，但是语法上更简单。在定义纯函数时，应该尽可能将其 Currying 化。

1
2
3
4
5
6
7
8
9
10
11
12
auto curriedAddThree = [](const int first){
    return [first](const int second){
        return [first,second](const int third){
            return first + second + third;
        };
    };
};
auto addTo10Plus20 = curriedAddThree(10)(20);
TEST_CASE("Add three with curry"){
    CHECK_EQ(42,curriedAddThree(15)(10)(17));
    CHECK_EQ(60,addTo10Plus20(30));
}

好怪，不知道在干什么

二、 < functional >

function< T >

该数据类型可以用于各种函数，如 lambda 表达式，独立函数以及成员函数等。

1
2
3
4
5
6
7
8
9
10
function<const int(const int)> identity = [](const int value){ return value;};

const int f(){return 2;};
function<const int()> fun = f;

class c{
    public:
    const int cf() const {return 2;};
}
function<const int(const c&)> func = &c::cf();

三、 < algorithms>

all_of、any_of、none_of

1
2
3
4
5
std::vector<int> v = {1,2,3};
auto isEven = [](int i)->bool {return !(i%2);};
CHECK(std::all_of(v.begin(),v.end(),isEven)==FALSE);
CHECK(std::any_of(v.begin(),v.end(),isEven)==TRUE);
CHECK(std::none_of(v.begin(),v.end(),isEven)==FALSE);

find 系列

1
2
3
4
5
6
7
std::vector<int> v = {1,2,4,5,2,4,11,8,3,2};
auto isDividedByThree = [](int i)->bool{return (i%3==0);};
// 查找等于给定值的第一个位置，若没有找到则返回last;
auto it = std::find(auto first = v.begin(),auto last = v.end(),4);
// 查找满足/不满足条件的元素的第一个位置
auto it2 = std::find_if(v.begin(),v.end(),isDividedByThree);
auto it3 = std::find_if_not(v.begin(),v.end(),isDividedByThree);

count 系列

1
2
3
4
std::vector<int> v = {1,2,4,5,2,4,11,8,3,2};
auto isDividedByThree = [](int i)->bool{return (i%3==0);};
std::count(v.begin(),v.end(),4);
std::count_if(v.begin(),v.end(),isDividedByThree);

copy 系列

1
2
3
4
std::vector<int> v = {1,2,4,5,2,4,11,8,3,2};
std::vector<int> v1;
std::copy(v.begin(),v.end(),v1.begin());
std::copy_if(v.begin(),v.end(),v1.begin(),isEven);

transform

1
2
std::string s("hello");
std::transform(s.begin(),s.end(),s.begin(),[](unsigned char c){return std::toupper(c)

四、< numeric>

accumulate

1
2
3
4
// 对 v 求和，初始值为0
std::accumulate(v.begin(),v.end(),0);
// 对 v 求连乘，初始值为1
std::accumulate(v.begin(),v.end(),1,std::multiply<int>());

五、 < ranges>

algorithms

ranges 重载了 中的算法，可以用容器 v 本身代替 v.begin() 和 v.end()。

views

views 支持管道算法和惰性求值（Lazy Evaluation），避免了过多的拷贝过程，从而提高了程序运行效率。

views 不会改变源容器，最后会将满足条件的元素拷贝到一个新的容器中。

1
2
3
4
5
6
7
8
9
10
11
// filter and transform
    std::vector<int> const vi{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    using namespace ranges;


    auto rng = vi | views::filter([](int i) { return i % 2 == 0; }) |
               views::transform([](int i) { return std::to_string(i); });

// generate and accumulate
    int sum = accumulate(views::ints(1, unreachable) | views::transform([](int i) {
                             return i * i;}) | views::take(10), 0);

除了知道vi在哪里，真不理解这个调用过程又会是怎样完成的

rng到底再求什么东西啊？？？又按位运算

第二次了解

核心思想

函数式编程是一种声明式的编程风格。它的唯一重点是“解决什么”，而命令式风格则主要关注“如何解决”。它使用表达式而不是语句。

函数式编程关键概念

  • 作为第一类对象的函数
  • 纯函数

函数式编程规则

  • 不可变变量：在函数式编程中，变量初始化后不能修改。你就是不能。您可以创建新变量，但不能修改现有变量。
  • 无副作用：副作用是当前正在执行的函数之外的状态变化。修改函数外部定义的变量、打印到控制台、引发异常以及从文件中读取数据都是副作用的示例。
  • *无状态：*函数内部可能有包含临时状态的局部变量，但该函数不能引用该函数所属的类或对象的任何成员变量。状态鼓励导致副作用的可变性。函数式编程不希望你这样做。

这些是FP的几个关键概念，规则。即使您没有一直遵循所有这些规则，您仍然可以从应用程序中的 FP 思想中受益。无论如何，C++ 从来都不是一种严格或纯粹的函数式编程语言。老实说，函数式编程并不是解决所有问题的正确工具（是的！这是我的观点。将来可能会改变。观点会随着经验而改变！）。现在，让我们了解一下 FP 擅长解决哪些问题。

作为第一类对象的函数

在函数式编程世界中，函数是一流的对象。函数被视为任何其他变量。例如，一个函数可以作为参数传递给其他函数，也可以作为值分配给变量。

在 C++ 中，函数不是第一类对象。我们得到的最接近的是 lambda 表达式。

1
auto printText = [](std::string text) { std::cout << text << std::endl; };

上面的代码正在创建一个 lambda printText，它接受一个参数text ，打印它并且什么都不返回。[]括号用于指定函数的闭包。更多关于 lambdas 的信息可以在这里找到。

让我们看看我们如何在 C++ vector或任何集合上应用不同的组合器，如过滤器、映射、减少，来看看我们如何做 FP。让我们采用以下vector：

1
std::vector<std::string> messages = { "Hello Pal", "How are you?", "I'm still coding in C++" };

for_each

1
2
std::for_each(messages.begin(), messages.end(), printText);

前两个参数是集合的开始和结束。然后我们传递的第三个参数是一个对每个元素进行操作的一元 lambda。

Let’s create a vector of custom student objects and apply the combinators on it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Student
{
public:
    string _name;
    int _score;
    Student(string name, int score)
    {
        _name = name;
        _score = score;
    }
    void incrementScore() {
        _score += 1;
    }
    string name()
    {
        return _name;
    }
    int score()
    {
        return _score;
    }
};
std::vector<Student> students = {Student("Alice", 85), Student("Bob", 62), Student("Charlie", 81), Student("Jack", 90), Student("Jimmy", 40), Student("Sherlock", 67),};

Assume, you’re the teacher and want to print their details. Then, you can use for_each to print their details.

1
2
auto printStudentDetails = [](Student student) { std::cout << student.name() << " " << student.score() << std::endl; };
std::for_each(students.begin(), students.end(), printStudentDetails);

In the above code, we have used a printing lambda to print each student’s detail.

map

In C++, the equivalent for the functional map is transform. Assume,

You gave a one mark question with insufficient/invalid data

and want to add one mark to every student.

Then you can use transform to update every student’s score.

1
2
auto addOne = [](Student student) { student.incrementScore(); return student; };
 std::transform(students.begin(), students.end(), students.begin(), addOne);

您必须提供输入集合的开始、结束指针、输出集合的开始指针和操作。您甚至可以transform一次在两个集合上执行。您可以查看它，它超出了本博客的范围。

筛选

在 C++ 中，函数filter有许多基于用例的等价物。如果您只想获取具有特定属性的元素的副本，您可以使用copy_if. 无论如何，还有其他功能，例如remove_if,find_if等。并且每个这样的功能都有一个“ not”替代品以及copy_if_not，find_if_not等。

1
2
3
4
5
6
auto aboveEighty = [](Student student) { return student.score() > 80; }; 

vector<student
> topStudents = {}; 
auto it = std::copy_if(students.begin(),students.end(), back_inserter(topStudents), aboveEighty); 
std::for_each(topStudents.begin(), topStudents.end(), printStudentDetails);

的语法copy_if是：copy_if(Iterator inputBegin, Iterator inputEnd, Iterator outputBegin, predicate). 您必须提供输入集合的开始、结束指针、输出集合的开始指针和操作。我使用了back_inserter_iterator而不是 outputBegin，这使我能够将元素推送到 topStudents 向量中，而无需初始化向量。

Reduce or Fold

The functional reduce equivalent in C++ is accumulate. Assume you’ve a vector with numbers and you want to sum them all.

1
2
3
vector<int> numbers{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 std::cout << std::accumulate(numbers.begin(), numbers.end(), 0,
        [](int first, int second) { return  first + second; });

You’ll have to provide the begin, end pointers of the input collection, the initial value of the accumulator and a binary lambda. Accumulator can also be applied to our custom students vector. Below code calculates the average score of the classroom.

1
2
auto binaryOp = [](int score, Student student) { return score + student.score(); };
std::cout << std::accumulate(students.begin(), students.end(), 0, binaryOp)/students.size();

纯函数

A function is a pure function if:

  • The execution of the function has no side effects.
  • The return value of the function depends only on the input parameters passed to the function.
1
2
3
int sum(int a, int b){
   return a+b;
}

Above created function is a pure function. Many in-built C++ functions are pure like min, max, strlen, etc. You can write functions which accept all const parameters and don’t change the instance variables. In GCC, you can even mark functions as pure using the “pure” attribute which enables better optimization. If a function is known as pure to the compiler then Loop optimization and subexpression elimination can be applied to it. But C++ allows side-effects, mutability as well by default.

1
2
3
4
5
6
7
8
9
10
11
public class NonPureFunctionAndMutatingParametersExample{
    private int total= 0;

    public int add(int nextValue) {
        this.total+= nextValue;
        return this.total;
    }
    public void incrementScore(Student &student){
         student.score += 1;
    }
}

In the above code:

  • add method is changing the state
  • incrementScore method is changing the function parameters

We should avoid doing the above things unless necessary. Yes, there are cases where side effects, mutability would benefit.

The rule Immutable variables is a good practice to follow. Once you create a variable and set its value, you can have full confidence knowing that the value of that variable will never change but sometimes it is not suitable. If you’re building an application which has to run in the end-users low configuration machines, then you’ll have limited memory, time. In such cases, it’s suggested to accept the references/pointers of the parameters, mutate them to save memory and copying time.

The rule No side effects is very helpful. It gives confidence that this function won’t affect the outside world and it’s safe to call it anywhere. But it makes it hard in some scenarios e.g. writing to a database (that is a side effect).

There are some other concepts, rules like Higher order functions, recursion over loop, etc which can be applied whenever needed.

总结

1.第一次看通篇看下来蛮奇怪的，一点都感受不到什么函数式编程，只看见一堆lambda狂用

2.函数式编程感觉就是仿函数和lambda们的使用，能够通过这种方式来使得函数能够作为对象进行传参来被其他可能有改变的（？？？）算法或者行为进行调用

第三次了解

https://www.bilibili.com/read/cv25550735/

感觉这个讲解的很清楚了

甚至其他编程范式的区别也很明显的表示出来了

  • 函数作为对象

  • 以函数式作为编程思想的出发点

  • 不可变性和无副作用我不太理解

  • 介绍了基于函数式编程的几种代码形式

    函数组合

    Pipeline （链式调用函数对象）

    PointFree （看不懂）

    懒惰求值（这个是在编译器层面做的工作吗？）

    尾递归（看不懂）

    MapReduce （好家伙这么来的是吧）

  • 4.1.1 优点

    简洁性：函数式编程通常比命令式编程更简洁，因为它们不需要维护状态或副作用。这使得代码更容易理解和维护。

    可读性：函数式编程通常更容易阅读，因为它们的代码更加模块化和组合化。这使得代码更容易理解和修改。

    可扩展性：函数式编程通常更容易扩展，因为它们的代码更加模块化和组合化。这使得代码更容易重用和修改。

    可靠性：函数式编程通常更可靠，因为它们不依赖于共享状态或副作用。这使得代码更容易测试和调试。

    并行性：函数式编程通常更容易并行化，因为它们的代码不依赖于共享状态或副作用。这使得代码更容易利用多核处理器和分布式系统。

    4.1.2 缺点

    性能：函数式编程通常比命令式编程更慢，因为它们需要更多的内存和计算资源来处理数据。这使得函数式编程不适合处理大规模数据或高性能应用程序。

    学习曲线：函数式编程通常比命令式编程更难学习，因为它们需要更多的数学和抽象思维。这使得函数式编程不适合初学者或非技术人员。

    可读性：函数式编程通常比命令式编程更难阅读，因为它们的代码更加抽象和符号化。这使得函数式编程不适合所有人，特别是那些不熟悉函数式编程的人。

    可维护性：函数式编程通常比命令式编程更难维护，因为它们的代码更加抽象和符号化。这使得函数式编程不适合所有人，特别是那些不熟悉函数式编程的人。

    工具支持：函数式编程通常比命令式编程缺乏工具支持，因为它们需要更多的数学和抽象思维。这使得函数式编程不适合所有人，特别是那些需要使用工具来提高生产力的人。

 Comments
Comment plugin failed to load
Loading comment plugin
  1. 1. 20220925 函数式编程
  2. 2. 第一次了解
    1. 2.1. 一、函数式编程
      1. 2.1.1. 1.1 创建纯函数
    2. 2.2. 1.2 Partial Application 与 Currying
    3. 2.3. 二、 < functional >
    4. 2.4. 三、 < algorithms>
    5. 2.5. 四、< numeric>
    6. 2.6. 五、 < ranges>
  3. 3. 第二次了解
    1. 3.1. 核心思想
    2. 3.2. 函数式编程关键概念
    3. 3.3. 函数式编程规则
    4. 3.4. 作为第一类对象的函数
    5. 3.5. for_each
    6. 3.6. map
    7. 3.7. 筛选
    8. 3.8. Reduce or Fold
    9. 3.9. 纯函数
  4. 4. 总结
  5. 5. 第三次了解
© 2020 - 2025    明昧
Powered by Hexo & Theme Keep
Unique Visitor Page View
  1. 1. 20220925 函数式编程
  2. 2. 第一次了解
    1. 2.1. 一、函数式编程
      1. 2.1.1. 1.1 创建纯函数
    2. 2.2. 1.2 Partial Application 与 Currying
    3. 2.3. 二、 < functional >
    4. 2.4. 三、 < algorithms>
    5. 2.5. 四、< numeric>
    6. 2.6. 五、 < ranges>
  3. 3. 第二次了解
    1. 3.1. 核心思想
    2. 3.2. 函数式编程关键概念
    3. 3.3. 函数式编程规则
    4. 3.4. 作为第一类对象的函数
    5. 3.5. for_each
    6. 3.6. map
    7. 3.7. 筛选
    8. 3.8. Reduce or Fold
    9. 3.9. 纯函数
  4. 4. 总结
  5. 5. 第三次了解