如何以函数式编程方式划分集合为子组？含GOP分组示例

用Python的reduce实现核心逻辑 #

这类依赖上下文的分组操作，核心是状态累积，而reduce（左折叠）是函数式编程中处理此类场景的标准工具——它能维护一个累积状态，遍历集合时逐步更新状态。

下面是用纯函数式风格（仅用reduce、lambda等）实现的GOP分组代码：

from functools import reduce

def group_gops(frames):
    # 累积状态为二元组：(当前正在构建的GOP, 已完成的GOP列表)
    current_gop, completed_gops = reduce(
        lambda state, frame:
            # 遇到I帧时：若当前已有未完成的GOP，先存入已完成列表，再新建以I帧开头的新GOP
            ([frame], completed_gops + [current_gop]) if frame == 'I' and current_gop else
            # 若是第一个I帧（当前GOP为空），直接新建GOP；非I帧则追加到当前GOP
            (current_gop + [frame], completed_gops),
        frames,
        ([], [])  # 初始状态：空的当前GOP + 空的已完成列表
    )
    # 最后把剩余的未完成GOP加入结果
    return completed_gops + ([current_gop] if current_gop else [])

# 测试示例
frames = list("IPBBBPBBBIPBIPBPBP")
print(group_gops(frames))
# 输出：[['I', 'P', 'B', 'B', 'B', 'P', 'B', 'B', 'B'], ['I', 'P', 'B'], ['I', 'P', 'B', 'P', 'B', 'P']]

Lambda演算的表达思路 #

Lambda演算中没有原生的列表、状态等概念，需要用Church编码来模拟这些结构，核心依然是用折叠（fold，对应Python的reduce）来维护状态：

1. 先定义基础结构的Church编码：

   • 空列表：Empty = λf.λx.x
   • 列表构造（cons）：Cons = λa.λl.λf.λx.f a (l f x)
   • 左折叠（foldl，对应reduce）：Foldl = λf.λacc.λlist.list f acc
   • 状态二元组：Pair = λa.λb.λf.f a b；取第一个元素Fst = λp.p λa.λb.a；取第二个元素Snd = λp.p λa.λb.b

2. 定义处理单帧的逻辑函数：

   Process = λstate.λframe.λisI.
     isI frame 
     (
       (Fst state ≠ Empty)
       (Pair (Cons frame Empty) (Cons (Fst state) (Snd state)))
       (Pair (Cons frame Empty) (Snd state))
     )
     (Pair (Cons frame (Fst state)) (Snd state))
   

   逻辑和Python版一致：遇到I帧时根据当前状态决定是否归档旧GOP，非I帧则追加到当前GOP。

3. 最终分组函数：

   GroupGOPs = λframes.
     let initial = Pair Empty Empty in
     let finalState = Foldl Process initial frames in
     Reverse (Cons (Reverse (Fst finalState)) (Reverse (Snd finalState)))
   

   这里的Reverse是用foldl实现的列表反转（因为Church编码的cons是前置元素，需要反转才能得到正确顺序的GOP）。

补充说明 #

• 为什么不用map/filter？因为这两个操作都是无状态的：map是一对一转换，filter是元素筛选，都无法维护“当前正在构建的GOP”这个上下文状态，因此必须依赖reduce（折叠）来完成这类带状态的分组。
• Python完全支持这种函数式实现，上面的代码就是纯Python的函数式风格实现，没有任何命令式的循环或赋值。

内容的提问来源于stack exchange，提问作者John Ke