如何用标准函数式模式带累加器遍历转换RoseTree？

我定义了一种近似RoseTree的数据类型：

type RoseTree<'T> =
    {
        Root: 'T
        Children: LazyList<RoseTree<'T>>
    }

我希望将该树的实例转换为新树，其中节点的计算依赖其他节点的值（例如按遍历顺序为节点编号）。我尝试了map、Haskell的foldTree、unfold等标准函数，但均不满足需求：

• map仅处理孤立节点，无法共享状态；
• foldTree没有共享累加器，没法在遍历过程中传递状态；
• unfold生成的子树相互独立，无法利用父节点或之前节点的状态。

我不想手写递归函数或使用Zippers，想了解是否存在合适的标准函数式模式/类型类来实现这种带累加器的遍历处理？

你要找的是带共享状态的递归转换模式——核心是用状态封装遍历过程中需要传递的累加值，结合树的遍历抽象来完成转换，完全不用手写递归或Zippers。

1. 用State Monad封装状态传递 #

在函数式编程里，State monad是处理这类带状态遍历的标准工具，它能把状态传递的逻辑从业务逻辑中剥离，不用手动管理状态流转。以F#为例，先定义一个轻量的State计算表达式：

type State<'S, 'T> = State of ('S -> 'T * 'S)

module State =
    let run (State f) s = f s
    let return' x = State (fun s -> (x, s))
    let bind f (State x) = State (fun s ->
        let (x', s') = x s
        run (f x') s')

    let get = State (fun s -> (s, s))
    let put s = State (fun _ -> ((), s))

    type StateBuilder() =
        member _.Return(x) = return' x
        member _.Bind(x, f) = bind f x

    let state = StateBuilder()

2. 结合Traverse实现带状态的树转换 #

针对你的RoseTree，实现一个带状态的traverse函数，它会遍历每个节点并共享状态，生成新树。比如按前序遍历给节点编号的逻辑：

open LazyList

let traverseRoseTree (f: 'T -> State<'S, 'U>) (tree: RoseTree<'T>) : State<'S, RoseTree<'U>> =
    State.state {
        // 处理根节点，同步更新状态
        let! newRoot = f tree.Root
        // 递归处理所有子节点，复用同一个状态
        let! newChildren = tree.Children |> mapM (traverseRoseTree f)
        return { Root = newRoot; Children = newChildren }
    }

// 示例：前序编号，初始状态从1开始
let numberNode (value: 'T) = State.state {
    let! current = State.get
    do! State.put (current + 1)
    return (value, current)
}

// 使用示例
let originalTree = { Root = "A"; Children = cons { Root = "B"; Children = nil } (cons { Root = "C"; Children = nil } nil) }
let (numberedTree, _) = traverseRoseTree numberNode originalTree |> State.run 1
// 结果树结构：
// { Root = ("A", 1); Children = cons { Root = ("B", 2); Children = nil } (cons { Root = ("C", 3); Children = nil } nil) }

3. Haskell场景的类型类方案 #

如果用Haskell，这种模式对应Traversable类型类结合State monad。给RoseTree实现Traversable实例后，直接用标准traverse函数即可：

import Control.Monad.State
import Data.List (mapM)

data RoseTree a = RoseTree { root :: a, children :: [RoseTree a] } deriving (Show)

instance Traversable RoseTree where
    traverse f (RoseTree r cs) = RoseTree <$> f r <*> traverse (traverse f) cs

-- 前序编号逻辑
numberNode :: a -> State Int (a, Int)
numberNode x = do
    n <- get
    put (n + 1)
    return (x, n)

numberTree :: RoseTree a -> RoseTree (a, Int)
numberTree t = evalState (traverse numberNode t) 1

优势 #

• 状态逻辑被封装，业务代码更简洁，不用重复写递归；
• 复用通用的traverse抽象，符合函数式编程的模块化原则；
• 状态传递的细节被隐藏，避免手动递归容易出现的错误。

内容的提问来源于stack exchange，提问作者MrD at KookerellaLtd