以递归方式生成类型类约束并在递归函数中使用它们

-- 定义一个类型类 Eq，用于比较两个值是否相等
class Eq a where
    (==) :: a -> a -> Bool

-- 为 Int 类型实现 Eq 类型类
instance Eq Int where
    x == y = x `primIntEq` y

-- 定义一个递归数据类型 Tree
data Tree a = Leaf a | Node (Tree a) (Tree a)

-- 为 Tree 类型实现 Eq 类型类
instance Eq a => Eq (Tree a) where
    Leaf x == Leaf y = x == y
    Node left1 right1 == Node left2 right2 = left1 == left2 && right2 == right2
    _ == _ = False

-- 定义一个递归函数，用于深度优先遍历树并检查所有节点是否相等
dfsEq :: Eq a => Tree a -> Bool
dfsEq (Leaf x) = True
dfsEq (Node left right) = dfsEq left && dfsEq right

-- 示例使用
main :: IO ()
main = do
    let tree1 = Node (Leaf 1) (Node (Leaf 2) (Leaf 3))
    let tree2 = Node (Leaf 1) (Node (Leaf 2) (Leaf 3))
    let tree3 = Node (Leaf 1) (Node (Leaf 2) (Leaf 4))
    print $ dfsEq tree1 == dfsEq tree2  -- 输出 True
    print $ dfsEq tree1 == dfsEq tree3  -- 输出 False

-- 使用尾递归优化的深度优先遍历函数
dfsEqTail :: Eq a => Tree a -> Bool
dfsEqTail tree = go tree True
    where
        go (Leaf _) acc = acc
        go (Node left right) acc = go left (go right acc)