fp-ts Traversable 模块全解析：traverse / sequence 的 Applicative 遍历与组合实战

fp-ts Traversable 模块全解析traverse / sequence 的 Applicative 遍历与组合实战【免费下载链接】fp-tsFunctional programming in TypeScript项目地址: https://gitcode.com/gh_mirrors/fp/fp-ts导读Traversable是 fp-ts 中描述可遍历数据结构的核心类型类它让开发者可以在一个数据结构如ReadonlyArray、Option上执行带效果effect的遍历并在某个Applicativefunctor 中累积结果。本文以 docs/modules/Traversable.ts.md 为骨架结合 src/Traversable.ts 源码与 test/Traversable.ts 测试系统讲解traverse与sequence的语义、兼容律、全部接口签名含 HKT 高 Kind 类型、可管道化接口以及 v2.10.0 引入的traverse/sequence组合函数读完你将能在自己的数据结构上实现并通过律测试验证Traversable实例。1. Traversable 是什么在 Applicative 中积累结果与效果的遍历根据 src/Traversable.ts 的模块文档Traversable表示可以在某个Applicativefunctor 中遍历、并积累结果与效果的数据结构。它定义了两个核心操作traverse对数据结构中的每个元素运行一个动作action并累积结果。sequence运行数据结构中已包含的动作并累积结果。二者的关系可以这样理解traverse是对每个元素施加函数再收集映射 效果累积sequence是元素本身就是效果直接收集等价于traverse(xs, identity)。在实际项目中traverse最常见的应用场景是把一个ReadonlyArrayA中每个元素经过一个返回TaskE, B/IOB/OptionB的异步或可能失败的函数处理最终得到TaskE, ReadonlyArrayB/OptionReadonlyArrayB——即批量处理并整体聚合结果中途某个元素失败则整体失败对Option/Either而言。2. traverse 与 sequence 的兼容律law原文档明确指出traverse和sequence应当在如下意义上兼容traverse(A)(xs, f) - sequence(A)(A.map(xs, f)) sequence(A)(xs) - traverse(A)(xs, identity)其中A是一个Applicative实例。第一条律说明先map再sequence等价于直接traverse第二条律说明sequence就是traverse以恒等函数为动作的特例。Traversable实例还必须与对应的Foldable实例兼容原文给出的约束是import { getApplicative, make } from fp-ts/Const const A getApplicative(M) foldMap(M)(xs, f) traverse(A)(xs, (a) make(f(a)))其中M是一个Monoid实例。这一律保证当效果容器退化为Const即只累积、不产生其他效果时traverse的行为必须与Foldable的foldMap完全一致。换句话说Traversable是Functor与Foldable的结构化叠加——在源码 src/Traversable.ts 中所有Traversable接口都同时extends FunctorT与FoldableT。3. model五个核心接口签名原文档model一节给出了 5 个接口它们依据类型构造子的元数arity分层是 fp-ts HKTHigher Kinded Types编码的体现。全部接口自 v2.0.0 起可用见 src/Traversable.ts3.1 Traversable非 HKT 版本export interface TraversableT extends FunctorT, FoldableT { /** * Runs an action for every element in a data structure and accumulates the results */ readonly traverse: TraverseT readonly sequence: SequenceT }3.2 一元类型构造子Traversable1T extends URIS例如ReadonlyArray、Option都属于这类export interface Traversable1T extends URIS extends Functor1T, Foldable1T { readonly traverse: Traverse1T readonly sequence: Sequence1T }3.3 二元类型构造子Traversable2 与 Traversable2CT extends URIS2例如EitherE, AE固定为错误类型、Reader、State等export interface Traversable2T extends URIS2 extends Functor2T, Foldable2T { readonly traverse: Traverse2T readonly sequence: Sequence2T } // 2C 版本第一个类型参数被固定fixed为 TL如 EitherL, A 已确定错误类型 export interface Traversable2CT extends URIS2, TL extends Functor2CT, TL, Foldable2CT, TL { readonly traverse: Traverse2CT, TL readonly sequence: Sequence2CT, TL }2C后缀表示constrained约束/固定适用于类型构造子的首参数在实例化时已被固定的场景。3.4 三元类型构造子Traversable3T extends URIS3例如ReaderTaskEitherR, E, A、StateReaderTaskEitherS, R, E, A这类携带三个类型参数的数据结构export interface Traversable3T extends URIS3 extends Functor3T, Foldable3T { readonly traverse: Traverse3T readonly sequence: Sequence3T }实战选型建议写实例时按你目标数据结构的元数选择对应接口写泛型约束时优先使用更精确的Traversable1/2/3以获得更好的类型推断仅在确需最宽泛约束时才退回到非 HKT 的TraversableT。4. Traverse 与 Sequence 方法签名详解TraverseT与SequenceT是两个带重载的方法签名接口见 src/Traversable.ts 与 src/Traversable.ts它们针对目标Applicative的不同元数4/3/2/1/非 HKT逐一重载。以TraverseT为例Sequence结构相同只是入参已包含效果export interface TraverseT { F extends URIS4(F: Applicative4F): A, S, R, E, B( ta: HKTT, A, f: (a: A) Kind4F, S, R, E, B ) Kind4F, S, R, E, HKTT, B F extends URIS3(F: Applicative3F): A, R, E, B( ta: HKTT, A, f: (a: A) Kind3F, R, E, B ) Kind3F, R, E, HKTT, B F extends URIS2(F: Applicative2F): A, E, B( ta: HKTT, A, f: (a: A) Kind2F, E, B ) Kind2F, E, HKTT, B F extends URIS(F: Applicative1F): A, B( ta: HKTT, A, f: (a: A) KindF, B ) KindF, HKTT, B F(F: ApplicativeF): A, B(ta: HKTT, A, f: (a: A) HKTF, B) HKTF, HKTT, B }要点解读调用形态是两段式柯里化先传Applicative实例F得到动作函数f→ 数据结构ta→ 结果的转换器。最终结果把容器反转HKTT, A变为HKTF, HKTT, B即内层容器T被翻到效果F的内部。重载覆盖URIS4如StateReaderTaskEither的四参数效果、URIS3、URIS2、URIS以及无 URI 的HKT兜底重载保证任意元数的Applicative都能被传入。同理Traverse1/2/2C/3只是把HKTT, ...替换为对应元数的KindT, .../Kind2T, TE, .../Kind3T, TR, TE, ...具体签名逐一列于原文档 Traverse1、Traverse2、Traverse2C、Traverse3 与Sequence1/2/2C/3实现均位于 src/Traversable.ts。Sequence系列与Traverse系列的区别在于sequence的入参是HKTT, KindF, A元素本身就是效果不需要f直接把这些效果翻出来。5. 组合子traverse 与 sequence 的组合v2.10.0原文档utils一节的traverse与sequence是组合子combinator用于把两个Traversable组合成一个嵌套遍历。两者均在 v2.10.0 引入见 src/Traversable.ts取代了旧的getTraversableComposition。5.1 traverse 组合子export declare function traverseT extends URIS, G extends URIS2( T: Traversable1T, G: Traversable2G ): { F extends URIS4(F: Applicative4F): A, S, R, FE, B( f: (a: A) Kind4F, S, R, FE, B ) GE(tga: KindT, Kind2G, GE, A) Kind4F, S, R, FE, KindT, Kind2G, GE, B // ... 其余重载 }它接受两个Traversable实例支持Traversable1T Traversable2G、Traversable1T Traversable1G、以及非 HKT 的TraversableT TraversableG三种重载返回一个接受Applicative→ 接受动作函数 → 接受嵌套结构的转换器。核心实现src/Traversable.ts非常简洁export function traverseT, G(T: TraversableT, G: TraversableG) { return (F) { const traverseT T.traverse(F) const traverseG G.traverse(F) return (f) (fga) traverseT(fga, (ga) traverseG(ga, f)) } }逻辑是对嵌套结构TGA先用G.traverse(F)把内层G翻到F里再用T.traverse(F)把外层T翻到F里最终得到FTGB。5.2 sequence 组合子sequence组合子的输入是tgfa: TGFA即效果F在最内层组合后把F翻到最外层得到FTGA。核心实现src/Traversable.tsexport function sequenceT, G(T: TraversableT, G: TraversableG) { return (F) { const sequenceT T.sequence(F) const sequenceG G.sequence(F) return (fgha) sequenceT(T.map(fgha, sequenceG)) } }实现先用T.map对内层的每个GFA执行sequenceG得到G包裹的FA变成FGA再用sequenceT把外层T翻出来。5.3 测试用例验证test/Traversable.ts 给出了两个组合子的直接验证it(traverse, () { const traverse _.traverse(RA.Traversable, RA.Traversable)(E.Applicative) U.deepStrictEqual(pipe([[E.right(1)]], traverse(identity)), E.right([[1]])) }) it(sequence, () { const sequence _.sequence(RA.Traversable, RA.Traversable)(E.Applicative) U.deepStrictEqual(pipe([[E.right(1)]], sequence), E.right([[1]])) })注意RA.Traversable在 src/ReadonlyArray.ts 导出RA.traverse在 src/ReadonlyArray.ts 实现——数组实例的traverse正是通过pipe(ta, traverseF(f))委托给内部traverse组合子完成的印证了模块间的一致设计。6. 可管道化接口PipeableTraverse1 / PipeableTraverse2v2.6.3原文档utils一节还包含两个**可管道化pipeable**接口v2.6.3 引入。它们的目的是把traverse变成适合pipe链式调用的形态柯里化顺序被调整为先 Applicative、再函数、最后数据结构从而可以写作pipe( ta, // TA F.traverse(f) // 得到 FTB )PipeableTraverse1Tsrc/Traversable.ts签名要点export interface PipeableTraverse1T extends URIS { F extends URIS3(F: Applicative3F): A, FR, FE, B( f: (a: A) Kind3F, FR, FE, B ) (ta: KindT, A) Kind3F, FR, FE, KindT, B F extends URIS2(F: Applicative2F): A, FE, B( f: (a: A) Kind2F, FE, B ) (ta: KindT, A) Kind2F, FE, KindT, B F extends URIS(F: Applicative1F): A, B( f: (a: A) KindF, B ) (ta: KindT, A) KindF, KindT, B F(F: ApplicativeF): A, B(f: (a: A) HKTF, B) (ta: KindT, A) HKTF, KindT, B }与TraverseT相比PipeableTraverse把数据结构ta放到了最后一个参数柯里化返回的函数接收它这正是 pipeable 风格的定义特征。PipeableTraverse2T extends URIS2则是面向二元构造子如Either的版本其中TE是数据结构自身的类型参数。典型用法示例结合 src/ReadonlyArray.ts 的实例实现思路import * as RA from fp-ts/ReadonlyArray import * as O from fp-ts/Option import { pipe } from fp-ts/function // 对数组每个元素做可能失败的处理任一失败则整体失败 const result pipe( [1, 2, 3], RA.traverse(O.Applicative)((n) (n 0 ? O.some(n * 2) : O.none)) ) // O.some([2, 4, 6])7. zone of death已废弃的组合 APIgetTraversableComposition原文档末尾的 zone of death废弃区列出了 v2.0.0 引入、现已标记deprecated的旧接口与函数src/Traversable.tsTraversableCompositionF, GFoldableCompositionF, G与FunctorCompositionF, G的组合含traverse/sequence成员TraversableComposition11F, G针对一元构造子的版本TraverseComposition11F, G与SequenceComposition11F, G组合遍历与组合序列的方法签名getTraversableComposition(F, G)工厂函数返回上述组合对象。test/Traversable.ts 仍保留了getTraversableComposition的回归测试覆盖map、traverse成功与失败分支与sequence含O.none传播const T _.getTraversableComposition(RA.Traversable, O.Traversable) // T.map / T.traverse(O.Applicative) / T.sequence(O.Applicative) // 例如 traverse 中任一元素返回 O.none 时整体结果为 O.none迁移建议文档与源码均明确指出请改用 v2.10.0 的traverse与sequence组合子替代getTraversableComposition——新 API 更简洁、类型更精确且无需构造中间对象。8. 从源码看实例实现模式以 ReadonlyArray 为例要为自己的数据结构实现Traversable可参考 fp-ts 内置实例的写法。src/ReadonlyArray.ts 中实例方法先通过ApplicativeHKTF泛化任意效果再委托给模块内的traverse(F)组合子const _traverse: Traversable1URI[traverse] F( F: ApplicativeHKTF ): (A, B(ta: ReadonlyArrayA, f: (a: A) HKTF, B) HKTF, ReadonlyArrayB) { const traverseF traverse(F) return (ta, f) pipe(ta, traverseF(f)) }最终在 src/ReadonlyArray.ts 组装成公开实例export const Traversable: Traversable1URI { map: _map, reduce: _reduce, foldMap: _foldMap, reduceRight: _reduceRight, traverse: _traverse, sequence: _sequence // ... }这给出了通用实现套路内部使用可复用的traverse/sequence组合子外部暴露满足对应TraversableN接口签名的实例并确保第 2 节的律与Applicative的兼容律、与Foldable的一致性通过测试。9. 总结与速查表概念说明版本TraversableT及Traversable1/2/2C/3可遍历数据结构类型类继承Functor与Foldablev2.0.0TraverseT/SequenceT含 1/2/2C/3实例方法签名按目标Applicative元数重载v2.0.0PipeableTraverse1/2可管道化的traverse数据结构参数置于末尾v2.6.3traverse(T, G)/sequence(T, G)两个Traversable的组合子替代旧工厂v2.10.0getTraversableComposition及配套接口已废弃的组合 APIzone of deathv2.0.0已弃用核心结论Traversable Functor Foldable 可翻转移位traverse/sequence的本质是把容器与效果互换位置TFA↔FTA因此实现时必须依赖Applicative。必须满足兼容律traverse(A)(xs, f) - sequence(A)(A.map(xs, f))且与Foldable.foldMap通过Const建立一致性。新代码一律使用 v2.10.0 的traverse/sequence组合子做嵌套遍历不要使用已废弃的getTraversableComposition。想深入学习实例实现可继续阅读 src/ReadonlyArray.ts数组、src/Option.tsOption与 src/Either.tsEither中的Traversable导出以及 test/Traversable.ts 中完整的组合验证用例。【免费下载链接】fp-tsFunctional programming in TypeScript项目地址: https://gitcode.com/gh_mirrors/fp/fp-ts创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考