函数式编程E06:输入适配、双向映射与带邻域的计算
已经有一个检查整数是否为正数的 Predicate,现在要检查字符串长度;已经有整数编码器,现在要编码一组字符串拼接后的长度。这两件事都需要在已有消费者之前适配输入。另一个不同问题是对序列每个位置计算邻域之和,它需要保留当前位置之外的上下文。把这些需求分开,Contravariant、Profunctor 与 Comonad 的方向才不会混成名词表。
本篇所有结构都用几十行 Scala 手写,并用定律和一个错误邻域实现作对照。前置类型类背景保留在Scala 的高阶类型与组合定律,完整学习路径见导读与能力自测。
消费者从新的输入到旧的输入
Predicate[A] 持有 A=>Boolean。若已有 Predicate[Int],另有 String=>Int 的长度函数,那么新 Predicate[String] 应先求长度,再交给原检查器。它没有产生一个可以 map 的 A,而是在消费 A。
1 | |
方向从 B=>A 得到 F[A]=>F[B],与常见 Functor 的 A=>B 得到 F[A]=>F[B] 相反。这种相反发生在类型参数的映射方向,不是把实际执行顺序倒过来。运行仍是先拿到 B,再适配成 A,最后调用消费者。
Encoder 的结果固定为 String,它也可以从输入端适配。虽然 Predicate 和 Encoder 最后输出类型不同,两者对输入类型参数的操作规律相同。Cats 的Contravariant 文档以同一操作方向解释消费者适配;本实验不依赖 Cats,只检查最小形状。
身份律要求 p.contramap(identity) 与 p 在所有输入上行为相同。组合律要求连续适配等于一次复合适配:若 f:B=>A、g:C=>B,则 p.contramap(f).contramap(g)=p.contramap(f.compose(g))。注意右侧先执行 g,再执行 f;写成 g.compose(f) 通常类型就对不上。
实验选 f 为字符串长度,g 为字符串列表拼接,在空列表、单元素和多元素上检查两种结构的组合律,又在负二到二之间检查身份律。函数对象不能靠引用相等判断行为相等,因此测试调用 run 后比较结果。这是有限输入的外延近似,不是所有函数的可判定相等算法。
输入与输出都要适配时
若结构是 Pipe[A,B],持有 A=>B,则输入端可以逆向适配,输出端可以正向适配。两个方向合起来就是 dimap:
1 | |
假设原管道给整数加一。before 将字符串取长度,after 将结果乘二,再追加一层输入拼接和输出转字符串。数据路线是列表、字符串、长度、加一、乘二、字符串结果。类型中的两个参数都在变,但输入侧与输出侧不能采用同一个组合次序。
设第一层适配为 before=f、after=h,第二层为 before=g、after=j,组合律就是:
1 | |
左侧输入适配累积为 f∘g,输出适配累积为 j∘h。Cats 2.12.0 的ProfunctorLaws 源码明确列出身份与这种组合方向。本篇的 Pipe 是普通函数的包装,不因此获得解析失败、校验积累或流式背压等额外语义。
Profunctor 也不等于可以双向反解的函数。String=>Int 的长度转换丢失大量信息,dimap 不要求它可逆;输入预处理和输出后处理都只是普通函数。若需求是往返无损,需要额外的数据结构与定律,不能从名字里的“双参数”推导可逆性。
邻域计算为什么需要一个关注位置
对序列 [1,2,4],计算每个位置自己与相邻元素的和,边界只使用存在的元素,结果为 [3,7,6]。普通 map 的回调只收到单个元素,无法知道它位于哪里、左右元素是什么。若通过闭包读取外部数组和索引,语义也能写出,但上下文关系没有体现在参数里。
实验定义 Focus[A] 为非空 Vector 与有效索引:
1 | |
extract 取当前关注点;map 改每个元素但保持关注位置;extend 则把完整上下文依次移动到每个合法位置,运行“看得见邻域”的函数,然后收集结果,同时保留原来的关注索引。输入函数得到的不是一个 A,而是每个位置对应的 Focus[A]。
这正是 Comonad 的一个最小实例。Cats 的Comonad 文档介绍 extract 与 coflatMap;本篇将后者叫 extend。不能把普通可空 List 直接当作这个实例,因为空列表没有可总定义的 extract。实验选择构造时拒绝空 Vector,并同时拒绝越界索引;这是一条运行时不变量,不是 Scala 类型系统已经证明非空。
三条定律逐一对应什么行为
第一条是 w.extend(_.extract)=w。如果在每个位置只取当前元素,结果应重建原数据与原关注点。第二条是 w.extend(f).extract=f(w):先对所有位置计算,再取原关注位置,应该与直接在原上下文计算相同。
第三条是 w.extend(f).extend(g)=w.extend(x=>g(x.extend(f)))。左边先生成全体 f 结果,再让 g 看结果的邻域;右边在每个原位置上下文中完成同样两阶段计算。对 Focus 实现,右侧的 x 保有同一个完整 Vector,只改变索引,因此两侧会把相同的数据与焦点交给每个函数。
实验对三个索引逐一检查这三条,并额外检查 map 身份与组合。函数 f、g 使用邻域求和,结果类型都是 Int,方便实际比较。定律的数学量化范围比测试样本更大,因此文章给出定义展开的理由,测试则负责避免实现时遗漏焦点保留或错误索引。
最容易写错的是把原来的 w 固定下来:遍历三个位置时都计算 sum(w),得到 [7,7,7]。如果只检查中间位置,结果仍为七,错误会漏掉。第一条定律对这种固定焦点实现也会失败,因为它无法重建 [1,2,4]。这说明测试不同焦点并非凑数据,而是在区分实现真正依赖的是当前上下文还是捕获的旧上下文。
局部上下文不等于可变全局状态
extend 中的每一次 f 调用读取同一份不可变 values,并把索引作为值传入。它不是先更新第一个元素,再让第二个元素读取刚更新的结果。若把实现改成原地数组循环,就可能得到顺序相关的平滑结果,与这里的同时基于旧快照计算不同。
例如邻域求和的第一项是三。如果后续位置读取被覆盖的第一项,第二项会从七变成九,第三项还会继续受影响。两种算法都可能有用途,但必须给出不同名称和测试;不能用相同公式把原地迭代包装成同一个 Comonad 实例。
边界策略也是模型的一部分。本实验丢弃越界邻居,所以第一项是 1+2。如果需要环形序列,第一项应包括最后一个四;如果补零,某些运算可能碰巧与截断相同,平均值的分母却会不同。选择边界规则时要测试能区分策略的函数,不能只用一个恰好相等的求和例子。
对长度 n 的序列,extend 会运行 f 共 n 次。若 f 每次只访问固定半径邻域,总体可做到与 n 成正比;若 f 每次扫描全序列,则会出现平方级工作。Comonad 的接口不承诺增量计算或缓存,数据结构与 f 的复杂度仍需单独分析。本实验规模只有三个元素,没有性能结论。
方差标注与映射操作不是同一层
Scala 的 -A 是子类型关系上的声明,contramap 是接收一个普通函数并构造新实例的操作。本篇的 case class 没有声明逆变参数,仍可以定义 contramap。反过来,即使某个接口带有逆变标注,也不能仅靠这个标注推导它已经实现某个库的 Contravariant 类型类及定律。
当 B 是 A 的子类型时,可以把从 B 到 A 的向上转换看作一种特殊适配;contramap 允许的范围更广,例如字符串到长度、订单到总金额,这些通常不是子类型转换。把“输入类型变小”当作全部含义,会无法解释这些实际例子。
消费者的结果也会影响允许的观察。Predicate 只比较 Boolean 时,有些执行差异不可见;如果 Predicate 内部还写日志,连续 contramap 的组合需要保持适配函数与消费者的调用次数和顺序。当前实现每次只调用一次 f 和 run,测试使用纯函数,因此没有声称任何带缓存或重试的消费者也满足同样轨迹。
Focus 的位置是上下文的一部分,而不是数组元素的身份。两个位置恰好都含数字二,仍可能拥有不同邻居。以元素值为键缓存邻域结果会把这些上下文混淆。若需要缓存,至少要考虑整个相关邻域或其稳定版本,而不能只记住 extract 的结果。
多个维度也可以产生不同 Focus 模型。二维网格需要坐标和边界策略,树需要路径与父子关系,图还要决定重复节点和遍历方向。不能只把 Vector 换成任意集合就保留相同 extend 定义;每种上下文都必须解释“移动关注点”意味着什么,并重新检查定律。
最后,Comonad 并不意味着对外部世界拥有一个可读取的全局视图。本例上下文是显式传入的不可变值,且 extract 对每个合法实例都有定义。如果邻域来自远端查询,可能失败、超时或在不同时间返回不同版本,那就增加了效果和一致性问题。应将它们建模在适当边界,不能靠一个 extend 方法名把不稳定读取变成纯上下文计算。
接口选择可以落在一条具体判断上:如果要给已有消费者适配输入,用 contramap;如果一个处理步骤的两端都需要接不同格式,用 dimap;如果每个位置的计算需要读取显式邻域,用 extend。三者不是按复杂程度排序的升级路线,也没有要求一个模块同时引入全部结构。
遇到只需把数字加一的转换,普通函数组合已经足够。只有重复出现的方向与定律确实帮助约束代码时,才值得保留这些包装。教学实验将结构拆小,是为了能直接展开每个定义,而不是建议业务代码照抄一套自制类型类库。
实验里的错误邻域实现单独构造结果,不参与正式 extend 的执行。因此负例失败不会污染正确实例,正反结果可以在同一进程里直接比较;如果复用可变数组,则需要额外防止负例先修改测试输入。
复现与自测
运行 node examples/functional-programming/run.mjs E06,输出包含 neighborhood=3,7,6; fixed-focus-bug=7,7,7; empty=rejected,以及 Predicate/Encoder 的逆变定律、Pipe 的双向定律和三个位置的 Focus 定律检查。完整输入在Main.scala,Scala 3.3.7 的实际记录在result.json。
自测先只看类型:已有 Encoder[Int],要得到 Encoder[Order],缺的是 Order=>Int 还是 Int=>Order?答案是前者,因为新消费者需要把订单转换成旧消费者接受的整数。对 Pipe 则分别写出输入侧与输出侧的缺失函数,避免靠方法名猜方向。
修改题是增加环形邻域,使用 [1,2,4] 时每个位置的三格求和都为七,再用长度五的非对称数据证明实现真的移动了焦点。保留 extract 与 extend 定律检查,增加越界索引拒绝测试。若选择允许空结构,必须解释 extract 的返回类型如何改变,而不是删除 require 后等待数组访问异常。

