我怎样才能在哈斯克尔找到分支的深度

Question

我想实现一个函数，它为我提供树中每个分支的深度，并将深度的整数打包在一个列表中。我知道我如何找到最大值和最小值，但我不知道如何找到其他的。

我的代码与示例树：

初始化我的树：

data NBaum a = NBlatt a | NKnoten a [NBaum a]
  deriving(Eq,Show)

示例树：

NKnoten "Sonne"[NKnoten "Jupiter" [NBlatt "Io", NBlatt "Europa", NBlatt "Ganymed", NBlatt "Kallisto"],NKnoten "Mars" [NBlatt "Phobos", NBlatt "Deimos"],NBlatt "Merkur", NBlatt "Venus", NKnoten "Erde" [NBlatt "Mond"]]

最大深度：

tdepth (NBlatt a) = 1
tdepth (NKnoten _ b) = 1 + maximum [tdepth branch | branch <- b]

最小深度：

tdepth (NBlatt a) = 1
tdepth (NKnoten _ b) = 1 + minimum [tdepth branch | branch <- b]

示例树的解决方案，我将拥有：[2,2,3,3,3,3,3,3,3] .列表的元素可以有其他顺序。

Answer 1

我未实现递归调用 也许这个 shell 可能会有所帮助：

depths :: (Num b) => NBaum a -> [b]
depths = go 1
  where
    go n (NBlatt _) = [n]
    go n (NKnoten _ xs) = error "depths.go: not implemented"

Answer 2

听起来好像

你想自己找出解决方案，但这里有一个提示：你是否编写了有序或深度优先的遍历函数？

您可以为遍历函数提供另一个记住深度的参数。 每个递归调用都会递增它。 不要将节点的内容添加到列表中，而是添加深度。

如果您还没有做到这一点，编写该函数的一个好方法是添加一个构造列表的累积参数。 从根目录开始，有一个空列表和深度 1，每次点击叶节点时，都会将当前深度追加到列表的末尾。 在父节点上，将当前深度与从子节点上调用函数时返回的列表连接起来。

Answer 3

请检查一下。这个想法是将相同的函数应用于NKnoten中的每个子树，并且使用concat将结果连接到单个列表中。

depths :: (Num b) => NBaum a -> [b]
depths = go 1
  where
    go n (NBlatt _) = [n]
    go n (NKnoten _ xs) = concat (map (go (n+1)) xs)