Haskell:从 P 树中导出列表 [英] Haskell: Deriving a list from a P-Tree

问题描述

我来自命令式语言的背景，所以 Haskell 和函数式编程对我来说是一个非常新的概念.

I am coming from a background of Imperative languages, so Haskell and functional programming are a pretty new concept to me.

我有一个构建 P 树的数据类型，一棵有 p 个孩子的树.它类似于二叉树，只是叶子有值而内部节点没有.

I have a data type that builds P-trees, a tree with p children. It's similar to a binary tree except for the fact that the leaves have values but the internal nodes do not.

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

This is the data type I came up with (Kindly correct me If I am wrong).

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

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

I want to write a function that takes in a PTree and returns a list of the elements in the tree. This is what I have come up with so far

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

我没有得到预期的结果.例如，如果我尝试在 ghci 中运行以下代码，

I'm not getting my intended results. For instance, if I try to run the following code in ghci,

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

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

I am hoping to get a list of [5,6,7,8]. Could someone please give me a clue on figuring this out and guide me onto the correct path.

推荐答案

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

这里的 PTree 是一棵树，其中每个内部节点都有两个子节点(参见一"和二")，并且内部节点不携带 a 类型的值.PTree 没有 P 个孩子——每个节点有两个.类型没有指定总共有多少叶子.

Here PTree is a tree where each internal node has two children (see 'One' and 'Two) and internal nodes do not carry values of type a. A PTree does not have P children - each node has two. How many leafs total is not specified by the type.

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

关闭！试试 pList (PLeaf a) = [a].您的方式使 PLeaf 和 a 分开参数，而不是对单个参数进行模式匹配.

Close! try pList (PLeaf a) = [a]. Your way makes PLeaf and a separate arguments instead of pattern matching on a single argument.

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

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

Mmmm.... less close. Above you already showed PNode takes two PTrees and not a list. Consider instead:

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

这篇关于Haskell:从 P 树中导出列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！