• 闭关之 C++ 函数式编程笔记(三):range、 代数数据类型及模式匹配


    第七章 range

    7.1 range 简介

    • 包含两个迭代器
      • 一个指向集合的第一个元素
      • 一个指向集合最后一个元素的后面
    • 同一结构中保存两个迭代器与两个分离的迭代器相比有什么优点
      • 可以返回一个完整的 range 作为函数结果
      • 并把它传递给另一个函数,而无需使用局部变量保存中间结果
    • 示例
      std::vector<std::string> names = transform(
                                          filter(people, is_female),
                                          name
                                      );
      
      • filter 函数将返回一个 range, 包含 people 集合中符合 is_female 谓词元素。
      • transform 函数将接收这个 range, 并从这个过滤好的 range 中返回含姓名的 range
      • 可以有更多的嵌套
    • | 管道操作符
      • 可以把原始集合通过管道操作符和算法连接起来,而不是嵌套的函数谓词
      • 示例
        std::vector names = people | filter(is_female) | transform(name);

    7.2 创建数据的只读试图

    7.2.1 range 的 filter 函数

    • range 是表示集合元素的一种抽象
      • 它需要一个起点,一个终点,并允许获取它的每个元素
    • filter 将返回一个 range 结构
      • 它的起始迭代器是一个智能的迭代器代理,指向源集合中满足指定谓词的第一个元素
      • 结束迭代器是源集合中终止迭代器的代理。
      • 代理迭代器与源集合中的迭代器唯一的不同是,代理迭代器指向符合过滤谓词的元素
    • 每次迭代器代理向后移动时,就需要找到源集合中满足谓词的下一个元素
      • 重载了 ++ 操作符
      • 示例
        auto& operator++() 
        {
            //移动迭代器
            ++m_current_position;
            //从下一个元素开始搜索
            m_current_position = std::find_if(m_current_position, 
                                    m_current_position,
                                    m_end,
                                    m_predicate
                                );
            return *this;
        }
        
      • 通过过滤器的代理迭代器,就无须创建临时集合保存源集合中符合谓词的元素副本
      • 这样做其实创建了源数据的一个新视图 (view)

    7.2.2 range 的 transform 函数

    • 与 filter 类似, transform 函数也不需要返回一个新的集合
    • 与 filter 不同的是,transform 的 ++ 操作符没有重载,而是重载了 * 解引用操作符
    • 示例
      auto operator*()  const
      {  
          //获取源集合中的元素,对他施加转换函数
          //并把它作为代理迭代器指向的返回值
          return m_function( *m_current_position);
      }
      

    7.2.3 range 惰性求值

    • 从上面的解释可以看出,调用 filter 和 transform 都是创建一个视图,没有正真的进行计算。等到调用它们重载的操作符时,才真正的进行计算。这就是上一章惰性求值的方式。

    7.3 修改 range 中的值

    • 虽然转换可以通过视图实现,但有些需要改变源集合中的元素,这种操作称为行为(action)
    • 行为最常见的例子是排序,排序要改变源集合元素位置或创建一个新的集合保存
    • 行为与视图的区别
      • 视图转换对原来的数据创建一个惰性视图
      • 而行为直接处理存在的集合,并立即执行所需操作
    • 示例
      std::vector<std::string>  words = 
                              read_text() | action::sort 
                                          | action:unique;
      
      • 因为向 sort 传递临时文件,因此无需创建副本
    • 行为操作临时数据不是必须的,可以使用 |= 操作符进行左结合运算
      • 示例
        std::vector<std::string>  words = read_text();
        words |= action::sort | action:unique;
        

    7.4 定界 range (delimited range) 和 无限 range

    • 在 range 中,指向末端的迭代器用于指向集合的末尾
      • 但实际上没必要是一个迭代器,可以是任何其东西
        • 只要检测是否能达到集合末尾就可以
      • 这种特殊的值称为哨兵(sentinel)
    • 利用哨兵就可以创建定界 range 和无限 range

    7.4.1 用定界 range 优化用于输入的 range

    • 定界 range 不能实现知晓其大小
      • 但可以通过一个谓词检测是否已经达到末尾
        • 以 null 结尾的字符串是定界 range 的很好的例子
      • 示例
        std::accumulate(
                std::istream_iterator<double>(std::cin),
                std::istream_iterator<double>(),
                0
            );
        
      • 这里算法使用 std::istream_iterator() 检测是否达到集合末尾,类似哨兵的迭代器
      • std::accumulate 将一直读取输入中的值,直到遍历迭代器和末端迭代器相同
      • 下面是类似的哨兵伪代码
        template <typename T>
        bool operator==(const std::istream_iterator<T>& left,
            const std::istream_iterator<T>& right) 
        {
            if (left.is_sentinel() && right.is_sentinel()) 
            {
                return true;
            }
            else if (left.is_sentinel()) 
            {
            ...
            }
            else if (right.is_sentinel()) 
            {
            ...
            } 
            else 
            {
            ...
            }
        }
        
      • 不论左右迭代器是否是哨兵,都应该覆盖所有可能的情况,在算法的每一步都进行这些检查

    7.4.2 用哨兵创建无限 range

    • 无限 range 没有末端。有一个开始,但没有结束
      • 例如:无限整数 range view::ints(1)
    • view::ints(1) 应用示例
      //Range 示例为 std::vector
      template <typename Range>
      void write_top_10(const Range& xs)
      {
          auto items =
              //将电影 range 和从1开始的整数无限 range 压缩在一起
              //得到一个键值对的 range,电影名字和下标
              view::zip(xs, view::ints(1))
                  //取出一个键值对,构造一个包含电影分级和电影名字的字符串
                  | view::transform([] (const auto& pair) {
                          return std::to_string(pair.second) +
                              " " + pair.first;
                  })
                  //只对前10部电影感兴趣
                  | view::take(10);
      
          for (const auto& item: items) {
              std::cout << item << std::endl;
          }
      }
      
    • view::zip 接收两个 range,并对两个元素进行匹配,得到一个元素对
    • 无限 range 的一个优点是可以使代码更通用
      • 算法基于无限 range, 它就可以处理任意大小的 range,包括未知大小的 range

    7.5 用 range 统计词频

    • Code_7_5_1

    第八章 函数式数据结构

    8.1 不可变链表 (Immutable linked lists)

    • 链表对于大多数任务来说效率较低,因为它的定位机制与现代缓存硬件不符

    8.1.1 在表头添加和删除元素

    • 原始链表不可变
      • 在表头添加元素:只需新建一个节点,让新节点的指针指向原始链表表头
      • 在表头删除元素:只需新建一个头指针,指向原始链表中第二个元素

    8.1.2 在链表末尾添加和删除元素

    • 原始链表不可变
      • 在链表末尾添加元素
        • 复制原始链表中的数据,并在复制的链表末尾添加新元素
      • 在链表末尾删除元素
        • 复制原始链表中的数据,并删除复制的链表末尾元素

    8.1.3 在链表中间添加和删除元素

    • 原始链表不可变
      • 在链表中间添加元素
        • 复制位置之前所有元素,插入新元素,并把新元素与原始链表中剩余的元素链接起来
      • 在链表中间删除元素
        • 同理

    8.1.4 内存管理

    • 使用 std::unique_ptr 不理想,使用 std::shared_ptr

    8.2 不可变类向量结构 (略)

    • std::vector 实现不可变结构的问题是
      • 每次需要修改时都要复制所有的元素,创建一个修改后的副本
    • 常用的代替品是位图向量树(bitmapped vector trie, 也称前缀树)
    • Copy-on-write
      • 称为惰性拷贝,是一种优化技术
      • 它把复制延迟到实际修改时进行

    个人理解

    • 这部分更像是一篇论文
    • 个人理解与不可变链表一样,利用原始集合以最小的代价创建新的副本

    第九章 代数数据类型及模式匹配

    9.1 代数数据类型

    • 从已有的类型构造一个新类型有两种主要的操作
      • 和与乘积
    • C++ 创建乘积类型
      • std::pair (对) 和 std::tuple (元组)
      • std::pair 是两种类型的乘积
      • std::tuple可以包含任意多的类型
      • 乘积:笛卡尔积
      • std::tie
        • 创建一个对传递给它的值的引用元组
        • 在创建元组时,并不复制原始数据,原始字符串参与比较
      • std::pairstd::tuple的用途是创建乘积类型,可以自动获取字典比较运算符
      • 示例
        • 包含姓和名的类,需要实现姓和名的小于比较
        bool operator<(const person_t& left, const person_t& right)
        {
            return std::tie(left.m_surname, left.m_name) < 
                std::tie(right.m_surname, right.m_name);
        }
        
        • 创建乘积元组并比较
    • 和类型 (sum type)
    • A 类型和 B 类型的和类型可以包含 A 的实例或 B 的实例,而不能同时包含两个实例
      • 如枚举 (enum)
      • 枚举是一种特殊的和类型
      • 和类型是枚举的泛化类型,在构建和类型时,不是提供单个元素的集合,而是可以使用任意数目元素的集合

    9.1.1 通过继承实现和类型

    • Code_9_1_1
      • dynameic_cast 效率不高
      • 优势
        • 不会有无效状态
        • 没开始统计时,count 不会大于 0
        • count 也不会在统计结束后被意外修改
        • 可以实时掌握程序的状态
      • 个人理解,不适合在主循环中使用,开销有点大,内存碎片怎么办?
    • 继承方式创建和类型有一些缺陷
      • 为了保证开发性,需要使用虚函数和动态指派
      • 为了避免较慢的强制类型转换必须使用类型标志
      • 必须在堆上动态分配状态对象
      • 必须保证 state 指针有效

    9.1.2 通过 union 和 std::variant 实现和类型

    • 可以使用 std::variant 代替继承实现和类型
    • Code_9_1_2
      • std::variant 不是基于动态多态,所以它不会保存指向推中对象的指针
        • 它在自己的内存空间保存对象本身,和 union 一样
        • 不同的是,它可以自动控制保存对象的创建和消耗
        • 并且任意时刻都可以知道所包含对象的类型
        • 可以使用 std::getstd::get_if 访问其中的值
          • 两者都可以通过类型或类型索引访问 variant 中的元素
            • std::get(m_state);
            • std::get_if<1>(&m_state);
          • 不同的是,std::get 要么返回一个值,要么在获取不到时抛出异常
          • std::get_if 返回指向被包含值的指针,或出错时返回null
    • 使用 std::variant 优点
      • 不需要呆板的代码,因为类型标志由 std::variant 掌握
      • 也不需要创建继承关系,还可以对以存在的类型进行聚类
      • 不需要动态内存分配
        • 把存放类型的最大长度作为自己的大小
          • 加上一些额外标记
    • 缺点
      • 扩展比较困难
        • 如果需要向和类型中添加新类型,需要修改 variant 的类型
      • 在需要扩展的少数情况下,必须返回到使用继承实现的和类型
    • 基于继承的开放的和类型的另一种实现是使用 std::any 类,它是任意类型值的安全容器。
      • 虽然有时比较有用,但效率比 std::variant 低,不应该作为 std::variant的简单类型替换

    9.1.3 特定状态的实现

    • std::variant 中的索引成员函数
      • 返回 variant 实例中当前类型的索引
      • m_state.index() == 0
    • 对于使用和类型处理状态的程序设计方法推荐
      • 针对某一状态的处理代码,定义在状态对象中,而处理状态转换的代码定义在主程序中
        • 参考 Code_9_1_2
      • 另一种方法是把所有逻辑都放在状态类中
        • 这种方法可以避免使用 get_if 和索引获取状态,因为状态类的成员函数只用在这一状态时才会被调用
          • 缺陷是状态类型必须负责程序的状态转换,也就是说,状态之间必须互相了解,因此会打破程序的封装性
      • 个人理解
        • 还是使用 Filament 中的 variant 效率较高

    9.1.4 特殊的和类型: Optional

    • 工厂方法使用 std::unique_ptr
    • 返回一个指向已存在对象的指针,但用户不拥有这个对象使用 std::shared_ptr
    • 函数可能执行失败,借用 null 表示函数执行错误使用 std::optional
    • 可以定义一个模板实现自己的 get_if
      template<typename T, typename Variant>
      std::optional<T> get_if(const Variant& variant)
      {
          T* ptr = std::get_if<T>(variant);
          if (ptr)
          {
              return *ptr;
          }
          else
          {
              return std::nullopt;
          }
      
      }
      

    9.1.5 和类型用于错误处理

    • Code_9_1_5
      • Placement new
        • 与通常的 new 不同,new 进行内存分配并初始化
        • 而 placement new 允许使用已分配的内存,并在其中构建对象
        • 只用于实现不需要在运行时分配内存的和类型
      • 把错误嵌入类型中,对异步编程很有用。可以在不同的异步进程之间传递错误

    9.2 使用代数数据类型进行域建模

    • 设计数据类型时的思想
      • 使非法数据无法表示
      • 设计自定义类型或函数时也应该如此
        • 不要考虑需要哪些数据来涵盖程序可以包含的所有可能状态,并将它们放入类中
        • 而应考虑如何定义数据来仅涵盖程序可以包含的状态

    9.2.1 原始方法及其缺点 (设计网球程序)

    • 原始方法
      • 创建两个整型变量记录每个玩家的分数
      • 该方法涵盖了所有可能的状态
      • 问题
        • 会导致对玩家的分数设置成无效的值
        • 通常可以在 setter 进行验证,但不如不验证
          • 如果数据类型本身可以保证代码的正确性
    • 改进方法
      • 使用 enum 枚举代替数值型分数,它只允许分数设置有效的值
      • 这样大幅减少了程序的可能状态
      • 问题
        • 由于两个人可以平分,而且不能表示占先,需要额外添加平局和占先的枚举,从而引入了新的状态
    • 更好的办法是使用自上而下的设计

    9.2.2 更复制的方法:自上而下的设计

    • 将普通得分状态拆分
      class  tennis_t
      {
        enum class points
        {
          love,
          fifteen,
          thirty
        };
        enum class player
        {
          player_1,
          player_2
      
        };
        struct normal_scoring
        {
          points player_1_points;
          points player_2_points;
        };
        struct forty_scoring
        {
          player leading_player;
          points other_player_scores;
      
        };
      
      };
      
    • 平局和占先状态
      class tennis_t
      {
        struct deuce {};
        struct advantage
        {
          player player_with_advantage;
        };
      };
      
    • 定义所有状态的和类型
      class tennis_t
      {
        std::variant<normal_scoring, forty_scoring, deuce, advantage> state_;
      };
      
    • 这个例子主要目的是说明如何设计代数类型以符合业务建模的需要
      • 先把原来的状态分解成几个独立的子状态,再分别描述这些子状态

    9.3 使用模式匹配更好地处理代数数据类型

    • 实现可选值、变体和其他代数数据类型的程序时的主要问题
      • 每当需要一个值,都需要检查它是否存在,并从它的包装类型中提取它
    • 许多函数时编程语言提供了特殊的语法来简化这种操作
      • 语法类似 switch
    • 标准库提供了一个 std::visit 函数
      • 它接收一个 std::variant 实例和一个对 std::variant 中的值操作的函数
      std::vistit([] (const auto& value) {
            std::cout << value << std::endl;
          }, state_);
      
      • 需要对变体 variant 中的值执行不同的代码可以创建一个重载函数对象
        • 对不同类型执行不同的操作
        • 使用了模板参数推断
      template <typename... Fs>
      struct overloaded : Fs... { using Fs::operator()...; };
      
      template <typename... Fs> overloaded(Fs...) -> overloaded<Fs...>;
      
      • 应用
      return std::visit(overloaded {
                  [] (init_t) {
                      return (unsigned)0;
                  },
                  [] (const running_t& state) {
                      return state.count();
                  },
                  [] (const finished_t& state) {
                      return state.count();
                  }
              }, m_state);
      

    9.4 Mach7 的强大匹配功能

    • visitor 模式更高效
    • 缺点:语法比较笨拙
    • 示例
      void point_for(player which_player)
      {
        Match(m_state)
        {
          Case(C<normal_scoring>()) //增加分数或切换状态
          Case(C<forty_scoring>())  //玩家获胜或切换到平局
          Case(C<deuce>())          //却换占先状态
          Case(C<advantage>())      //玩家获胜,或切换回平局状态
        }
        EndMatch
      }
      

    总结

    关键 API

    • std::variant
    • std::get()
    • std::get_if()
    • index()
    • std::any
    • std::optional
    • std::visit()

    思想

    • 和类型用于错误处理 Code_9_1_5
  • 相关阅读:
    leetcode45 跳跃游戏II
    2023CSPS 种树 —— 二分+前缀和
    Python小课之数据类型初识
    react组件多次渲染问题
    【开源项目】libfaketime安装、使用——小白教程
    Android 12 适配攻略
    [linux] 报错信息重定向
    TypeScript基础语法
    Oracle11gr2 + plsql 配置
    竣达技术 | 适用于”日月元”品牌UPS微信云监控卡
  • 原文地址:https://blog.csdn.net/jiamada/article/details/127069661