Haskell二进制树路径功能

Question

我正在尝试定义一个函数，该函数将返回所有列表穿过给定的二进制树的路径。我已经定义了以下功能：

data BTree a = Leaf a | Node a (BTree a) (BTree a)
     deriving (Show,Eq)
paths :: BTree a -> [[a]] 
paths (Leaf a) = [[]]
paths (Node x left right) = map (x:) (paths left ++ paths right)

使用此功能，我有以下结果：例如： [[5,4],[5,4],[5,3],[5,3]]。但是我本来应该有输出[[5,4,1],[5,4,2],[5,3,3],[5,3,4]]。有人知道为什么我没有获得第三值吗？谢谢

Answer 1

您的BTree类型是：

data BTree a = Leaf a | Node a (BTree a) (BTree a)

请注意，与列表不同，它永远不会空：叶子和节点都包含类型a的值。就是这样，如果您在paths中有案例总是会产生空列表，例如...

paths (Leaf a) = [[]]

...您一定要扔掉价值。您想要的是：

paths :: BTree a -> [[a]] 
paths (Leaf a) = [[a]]
paths (Node x left right) = map (x:) (paths left ++ paths right)