如何用FP-TS/Ramda实现嵌套惰性列表的遍历匹配与扁平化？

需求背景 #

我刚学习了lift和applicative相关知识，想通过实战场景加深对这些结构的理解，当前场景如下：
现有一个惰性列表，只有加载完成后才能获取到元素数量和子节点信息，节点的获取、加载以及嵌套子节点的加载都是异步操作，节点结构示例如下：

[{title:"test1",children:[]},{title:"test2",children:[{title:"test2_1",children:[]}]}]

每个子节点是否存在下级节点，只有加载该节点后查看子节点数量才能确认。
需要通过函数式编程实现任意嵌套层级的全列表检查，满足以下两种需求之一即可：

• 逐次加载检查每个节点，找到匹配项或者遍历完所有节点后停止；
• 先加载所有节点，嵌套存入Right()/Left()后扁平化到单列表，再通过foldMap根据标题谓词匹配目标项，参考非嵌套数组的实现逻辑如下：

[{title:"test1"},{title:"test2"},{title:"test3"}] // 待加载的结构

const find= (l,f)=>l.foldMap(x=>First(f(x)?Right(x):Left()),First.empty())

const nodes = await getNodes() // 仅示例节点获取加载是异步操作，不额外定义类型
const list = List(await load(nodes)) // 仅示例节点获取加载是异步操作，不额外定义类型

console.log(find(list,x=>x.title==='test3').fold(x=>x).fold(console.error,x=>x)) 

现有命令式实现（Sharepoint导航节点获取逻辑） #

GetNavigationNodeChildren = node => node.get_children();
GetNavigationNodeRoot = spCtx => spCtx.get_web()
  .get_navigation().get_topNavigationBar();
ExecQuery = spCtx => resource => {
  return new Promise((res, rej) => spCtx.executeQueryAsync(
    () => res(resource),
    (s, a) => rej({ s, a }),
  ));
};
LoadResource = spCtx => resource => (spCtx.load(resource) ? resource : resource);
LoadAndExec = spCtx => async resource => {
    LoadResource(spCtx)(resource )
    await ExecQuery(spCtx)(resource )
    return resource
}
getAll = spCtx=> async resource=> {
    return {node:await LoadAndExec(spCtx)(resource),children:await hasChildren(c)(resource.get_children())}
}
hasChildren = spCtx => async resource => {
    LoadResource(spCtx)(resource )
    await ExecQuery(spCtx)(resource )
    return Promise.all(resource.get_count()>0?resource.get_objectData().$1G_0.map(await getAll(spCtx)):[])
}

c=new SP.ClientContext()
root=GetNavigationNodeRoot(c)
await LoadAndExec(c)(root)
all=await hasChildren(c)(root)

FP改造实现（优先使用Applicative） #

我们基于fp-ts的常用类型实现，核心用到Applicative组合异步操作、lift提升普通函数到异步错误上下文、Traversable处理嵌套异步结构、foldMap完成结果收集。

第一步：导入依赖类型 #

import * as TE from 'fp-ts/TaskEither'
import * as A from 'fp-ts/Array'
import * as L from 'fp-ts/List'
import { First } from 'fp-ts/First'
import { Either, right, left } from 'fp-ts/Either'
import { flow, pipe } from 'fp-ts/function'
import { lift } from 'fp-ts/TaskEither'

第二步：改造基础工具函数为纯函数 #

把原有副作用操作封装为返回TaskEither的纯函数，统一处理异步错误：

// 取根节点 纯函数
const GetNavigationNodeRoot = (spCtx: SP.ClientContext) => 
  spCtx.get_web().get_navigation().get_topNavigationBar()

// 取子节点 纯函数
const GetNavigationNodeChildren = (node: SP.NavigationNode) => 
  node.get_children()

// 执行查询 封装为TaskEither<Error, T>，统一处理异步错误
const ExecQuery = <T>(spCtx: SP.ClientContext) => (resource: T) => 
  TE.tryCatch(
    () => new Promise<T>((res, rej) => spCtx.executeQueryAsync(
      () => res(resource),
      (_, a) => rej(new Error(a.get_message()))
    )),
    (e) => e as Error
  )

// 加载资源 纯函数
const LoadResource = <T>(spCtx: SP.ClientContext) => (resource: T) => {
  spCtx.load(resource)
  return resource
}

// 加载并执行查询 组合两个操作，返回TaskEither
const LoadAndExec = <T>(spCtx: SP.ClientContext) => flow(
  LoadResource(spCtx),
  ExecQuery(spCtx)
)

第三步：实现递归加载所有节点的函数 #

这里用到Applicative的traverse能力，把Array<TaskEither<Error, NavigationNodeTree>>转成TaskEither<Error, Array<NavigationNodeTree>>，无需手动处理Promise.all和错误捕获：

// 定义节点树结构
type NavigationNodeTree = {
  node: SP.NavigationNode,
  children: Array<NavigationNodeTree>
}

// 递归加载节点及所有子节点
const loadNodeTree = (spCtx: SP.ClientContext): (node: SP.NavigationNode) => TE.TaskEither<Error, NavigationNodeTree> => 
  flow(
    // 先加载当前节点
    LoadAndExec(spCtx),
    // 用chain处理后续异步操作
    TE.chain(node => pipe(
      // 取当前节点的子节点集合
      GetNavigationNodeChildren(node),
      // 加载子节点集合
      LoadAndExec(spCtx),
      // 处理子节点加载结果
      TE.chain(childrenCollection => {
        // 子节点为空直接返回
        if (childrenCollection.get_count() === 0) {
          return TE.right({ node, children: [] })
        }
        // 拿到子节点原始数组
        const childrenNodes = childrenCollection.get_objectData().$1G_0 as SP.NavigationNode[]
        // 这里用A.traverse(TE.ApplicativePar)，本质是用Array和TaskEither的Applicative实例组合
        // 并行加载所有子节点的树结构，无需手动写Promise.all和错误处理
        return pipe(
          childrenNodes,
          A.traverse(TE.ApplicativePar)(loadNodeTree(spCtx)),
          TE.map(children => ({ node, children }))
        )
      })
    ))
  )

第四步：实现查询函数 #

用foldMap配合First完成匹配项查找，同时用lift把普通谓词函数提升到TaskEither上下文：

// 把节点树扁平化为单列表的纯函数
const flattenTree = (tree: NavigationNodeTree): L.List<SP.NavigationNode> => 
  L.cons(tree.node, pipe(tree.children, L.fromArray, L.chain(flattenTree)))

// 定义查找函数，lift把普通的谓词函数(node) => boolean 提升到TaskEither上下文
const findNodeByTitle = (title: string) => (list: L.List<SP.NavigationNode>) => 
  list.foldMap(First.getMonoid<Either<Error, SP.NavigationNode>>())(
    node => First(
      lift((n: SP.NavigationNode) => n.get_title() === title)(TE.right(node))()
        .then(match => match ? right(node) : left(new Error('不匹配')))
    )
  )

第五步：使用示例 #

const main = async () => {
  const spCtx = new SP.ClientContext()
  const rootNode = GetNavigationNodeRoot(spCtx)

  // 加载全量节点树
  const treeEither = await loadNodeTree(spCtx)(rootNode)()

  pipe(
    treeEither,
    // 加载成功则处理
    Either.match(
      err => console.error('加载失败', err),
      tree => pipe(
        tree,
        flattenTree,
        findNodeByTitle('test2_1'),
        first => first.value,
        Either.match(
          err => console.log('未找到匹配节点', err),
          node => console.log('找到匹配节点', node)
        )
      )
    )
  )
}

main()

核心FP概念说明 #

1. Applicative应用：A.traverse(TE.ApplicativePar)用到了Applicative的能力，把多个独立的异步加载操作组合成一个批量异步操作，自动处理所有子任务的错误传递，不需要手动嵌套await和捕获错误。
2. lift应用：把普通的标题匹配谓词函数提升到TaskEither的异步错误上下文，不需要手动拆包处理Either的错误分支，函数逻辑复用性更强。
3. foldMap应用：遍历扁平化后的节点列表，用First幺半群的特性，只会保留第一个匹配的Right节点，符合查找需求。

内容的提问来源于stack exchange，提问作者Ricardo Silva