Haskell递归模式实践：递归类型与参数化类型该选用哪种？

这问题真的特别接地气——我当初刚接触递归方案（recursion schemes）的时候，也对着这俩结构纠结了好久，总觉得“理论上只用TreeF就行，但写代码的时候咋这么麻烦？”，现在给你掰扯清楚实际开发里的选择逻辑：

先搞懂两种结构的核心定位 #

首先得明确，这俩结构不是“替代关系”，而是“分工不同”：

• Tree a：直接递归的具象结构
  这就是你平时写Haskell最顺手的递归数据类型，优点拉满：

  • 直观易懂，写构造树的代码不用额外套In/out，比如Node 1 (Leaf 2) (Leaf 3)直接就能写
  • Haskell能自动推导Show、Eq、Ord这些基础类型类，调试的时候打印树、比较树都不用自己写代码
  • 适合快速原型、小工具，或者不需要复杂递归逻辑的场景

• TreeF a r + Fix f：抽象的递归骨架
  把递归部分抽成参数r，再用Fix把它“打造成”递归结构，核心目的是复用通用的递归模式：
  比如你要写树的遍历、折叠、展开逻辑，不用给Tree单独写递归函数，而是用cata（折叠）、ana（展开）这类通用函数，只要TreeF是Functor，就能套用所有递归方案的工具。这在处理多个递归数据类型（比如表达式树、JSON树、AST）的时候，能省超多重复代码。

要不要同时用？看场景！ #

不是必须同时用，但混合使用往往是最高效的方案：

推荐的做法：外部用具象结构，内部用抽象骨架 #

• 对外暴露的API用Tree a：不管是给别人用还是自己后续维护，都不用记In/out的包裹逻辑，自动推导的类型类也能直接用，调试起来特别省心。
• 内部处理复杂递归逻辑的时候，把Tree a转换成Fix (TreeF a)：比如你要写一个通用的树结构转换函数，或者用cata实现树的求值/统计，就转成抽象结构处理，用完再转回去。

举个表达式树的例子（就是你提到的场景）：

-- 对外的具象表达式树
data Expr = Lit Int | Add Expr Expr | Mul Expr Expr deriving (Show, Eq)

-- 内部的递归骨架
data ExprF r = LitF Int | AddF r r | MulF r r deriving (Functor, Show, Eq)

-- 转换函数：具象 ↔ 抽象
toFixExpr :: Expr -> Fix ExprF
toFixExpr (Lit n) = In (LitF n)
toFixExpr (Add a b) = In (AddF (toFixExpr a) (toFixExpr b))
toFixExpr (Mul a b) = In (MulF (toFixExpr a) (toFixExpr b))

fromFixExpr :: Fix ExprF -> Expr
fromFixExpr (In (LitF n)) = Lit n
fromFixExpr (In (AddF a b)) = Add (fromFixExpr a) (fromFixExpr b)
fromFixExpr (In (MulF a b)) = Mul (fromFixExpr a) (fromFixExpr b)

-- 用递归方案实现求值（通用逻辑，换个递归结构也能复用思路）
evalFix :: Fix ExprF -> Int
evalFix = cata $ \case
  LitF n -> n
  AddF x y -> x + y
  MulF x y -> x * y

-- 对外的API，隐藏内部的抽象结构
evalExpr :: Expr -> Int
evalExpr = evalFix . toFixExpr

这样用户用的时候，只需要和Expr打交道，而你内部可以复用递归方案的强大能力，两全其美。

解决你提到的痛点：Fix (TreeF a)无法自动推导类型类 #

这个确实是个小麻烦，但有两个靠谱的解决办法：

1. 手动写实例：其实没你想的那么复杂，利用TreeF的实例递归处理就行，比如给Fix (TreeF a)写Show：

   instance (Show a) => Show (Fix (TreeF a)) where
     show (In (LeafF x)) = "Leaf " ++ show x
     show (In (NodeF x l r)) = "Node " ++ show x ++ " (" ++ show l ++ ") (" ++ show r ++ ")"
   

2. 用第三方库简化：比如recursion-schemes这个常用库，它的Fix类型已经通过Generic帮你处理了很多实例，而且提供了很多辅助工具来转换具象和抽象结构，能省不少代码。

最后总结选择逻辑 #

• 如果你的场景不需要通用递归逻辑（比如只是简单构造、遍历树）：直接用Tree a就行，省心省力，代码可读性拉满。
• 如果需要处理复杂递归逻辑，或者有多个递归数据类型要复用逻辑：引入TreeF + Fix，但记得用具象结构做外部接口，兼顾易用性和复用性。

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