Haskell:从 P 树派生列表

Question

我有命令式语言背景，因此 Haskell 和函数式编程对我来说是一个相当新的概念。

我有一种构建 P 树的数据类型，即具有 p 个子节点的树。它类似于二叉树，只不过叶子有值但内部节点没有。

这是我想出的数据类型(如果我错了，请纠正我)。

data PTree a = PNode (PTree a) (PTree a) | PLeaf a
   deriving Show

我想编写一个函数，它接受 PTree 并返回树中元素的列表。这是我到目前为止想到的

pList :: (Ord a) => PTree a -> [a]
pList PLeaf a = [a]
pList (PNode left right)  = pList left ++ pList right

我没有得到我想要的结果。例如，如果我尝试在 ghci 中运行以下代码，

pList (PNode [PLeaf 5, PLeaf 6, PLeaf 7, PLeaf 8])

我希望得到 [5,6,7,8] 的列表。有人可以给我一个解决这个问题的线索并引导我走上正确的道路吗？

Answer 1

data PTree a = PNode (PTree a) (PTree a) | PLeaf a
                   --   ^ One    ^ Two
   deriving Show

这里 PTree 是一棵树，其中每个内部节点都有两个子节点(请参阅“One”和“Two”)，并且内部节点不携带 a 类型的值。 PTree 没有 P 个子节点 - 每个节点有两个。类型未指定总共有多少片叶子。

pList :: (Ord a) => PTree a -> [a]
pList PLeaf a = [a]
pList (PNode left right)  = pList left ++ pList right

关闭!尝试pList (PLeaf a) = [a]。您的方式使 PLeaf 和 a 成为单独的参数，而不是对单个参数进行模式匹配。

pList (PNode [PLeaf 5, PLeaf 6, PLeaf 7, PLeaf 8])

嗯...不太接近。上面你已经展示了 PNode 需要两个 PTree 而不是一个列表。考虑一下:

PNode (PNode (PLeaf 5) (PLeaf 6)) (PNode (PLeaf 7) (PLeaf 8))