我最近在 Haskell 中查找了一些关于递归方案的指南，但是大多数文章并没有超出实现这些概念所需的基本基础结构。
给定递归数据类型，如二叉树
data Tree a =
Leaf a
| Node a (Tree a) (Tree a)
我们还将实现一个类似的结构，用类型参数替换定义的递归部分，以便能够使用诸如等的通用cata折叠ana
data TreeF a r =
LeafF a
| NodeF a r r
连同一个固定点组合器
newtype Fix f = In { out :: f (Fix f) }
这允许我们用我们的新表示来表达任意嵌套的树。
所以我的问题很直截了当（也许很愚蠢）：我们在程序的其余部分中实际使用了哪种数据结构表示？我们两者都需要吗？理论上我们只能使用TreeF，但是根据我在玩弄以这种方式实现的表达式语法树时发现的情况，这往往有点问题，主要是因为您现在必须将树的每个级别包装在新的数据构造函数中据我所知，您不能再从基本类型类（如Showor ）自动派生Eq。