Haskell类型匹配错误排查：二叉树叶到根路径生成代码报错

核心错误原因 #

你的代码出现类型不匹配，主要是两个关键问题：

1. 列表合并方式错误 #

go l和go r的返回类型是[[Int]]（每个都是叶到根的路径列表），但你用了(:)来合并它们。(:)的作用是将单个元素添加到列表头部，所以go l : go r会试图把一个[[Int]]作为元素放到[[Int]]类型的列表前，最终得到[[[Int]]]，但insev的第一个参数需要的是[[Int]]，直接导致类型不匹配。

正确的合并方式应该用++，它负责拼接两个同类型的列表，go l ++ go r得到的仍然是[[Int]]，完全符合insev的参数要求。

2. 模式匹配逻辑错误 #

你写的insev [[]] x = []是匹配「包含空列表的单元素列表」，但实际场景中，当子树有路径时输入的是正常路径列表，即使子树无路径（你的Tree定义不存在空树，但代码需要鲁棒性），输入也会是空列表[]，所以这个模式完全没用，应该改成insev [] _ = []来处理空输入。

修正后的代码 #

data Tree = Leaf Int | Node Tree Int Tree

-- 显式添加类型签名，提前发现类型问题
go :: Tree -> [[Int]]
go (Leaf a) = [[a]]  -- 等价于原代码的 (a : []) : []，更简洁
go (Node l n r) = insev (go l ++ go r) n

insev :: [[a]] -> a -> [[a]]
insev [] _ = []  -- 处理空列表输入
insev (h:t) x = (insb h x) : insev t x

insb :: [a] -> a -> [a]
insb [] num = [num]  -- 等价于原代码的 num : []，更简洁
insb (h:t) num = h : insb t num

测试示例 #

构造测试树：

testTree = Node (Leaf 1) 2 (Node (Leaf 3) 4 (Leaf 5))

调用go testTree会得到：

[[1,2], [3,4,2], [5,4,2]]

这正是从叶节点到根节点的所有路径。

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