一棵树的深度(哈斯克尔)

Question

我试图弄清楚如何计算哈斯克尔中一般树的深度。我可以找出简单二叉树的解决方案，但不能找出具有任意数量叶子的一般树的解决方案。

这是我为二叉树准备的代码。

--depth of a binary tree.
depth :: Tree a -> Int
depth Nil            = 0
depth (Node n x1 x2) = 1 + max (depth x1) (depth x2)

如何修改常规树的此设置？一般树包含树列表，这就是我遇到困难的地方。

其次，我想将树变成一个列表(这样我就可以做一些操作，比如计算总和等)

同样，我可以为二叉树弄清楚，但不能为一般树弄清楚。

--tree into a list.
treeToList:: Tree a -> [a]
treeToList Nil = []
treeToList (Node n x1 x2)
= collapse x1 ++ [n] ++ collapse x2

Answer 1

使用

Foldable获取单个值，使用Functor映射函数

user2407038 的好答案向您展示了如何手动编写Foldable实例，这是非常好的建议，您可以使用foldMap不仅可以制作treeToList，还可以方便地制作其他函数。

GHC 允许您自动派生这些实例：

{-# LANGUAGE DeriveFunctor, DeriveFoldable #-}
import Data.Monoid
import Data.Foldable
data Tree a = Node a [Tree a] 
deriving (Show,Functor,Foldable)

让我们用一个例子来测试一下：

example :: Tree Int
example = Node 3 [Node 2 [], Node 5 [Node 2 [],Node 1 []],Node 10 []]
--   3
--   |
--   +--+-----+
--   2  5     10
--      |
--      +--+
--      2  1

让我们用fmap将所有东西乘以 10：

> example
Node  3 [Node  2 [], Node 5 [Node  2 [], Node 1 []], Node 10 []]
> fmap (*10) example
Node 30 [Node 20 [],Node 50 [Node 60 [],Node 10 []],Node 100 []]

使用Monoid组合值

Monoid 允许您组合 (mappend) 值，并且具有称为mempty的无所事事/标识值。 列表是单体，具有mempty = []和mappend = (++)，数字以多种方式是单体，例如，使用(+)(Sum幺半群)，使用(*)(Product幺半群)，使用最大值(我必须手写Max幺半群)。

我们将使用foldMap来标记 Ints 和我们要使用的幺半群：

> foldMap Sum example
Sum {getSum = 23}
> foldMap Product example
Product {getProduct = 600}
> foldMap Max example
Max {unMax = 10}

您可以随心所欲地定义自己的幺半群 - 以下是制作 Max 幺半群的方法：

instance (Ord a,Bounded a) => Monoid (Max a) where
mempty = Max minBound
mappend (Max a) (Max b) = Max $ if a >= b then a else b

您可以进行的最一般的折叠

在这个有很好答案的好问题中，Haskell 的头号提问者 MathematicalOrchid 询问如何将折叠推广到其他数据类型。这个问题的答案很棒，值得一读。

广义折叠只是用函数替换数据类型的每个构造函数，并计算以获取值。

手动滚动的方式是查看每个构造函数的类型，并创建一个函数，该函数接受一个函数参数来匹配每个构造函数和一个参数来匹配对象本身，并返回一个值。

例子：

[]有两个构造函数，(:) :: a -> [a] -> [a]和[] :: [a]所以

foldList :: (a -> l -> l) ->    l      -> [a] -> l
foldList    useCons         useEmpty      = f where 
f (a:as) = useCons a (f as)
f [] = useEmpty

Either a b有两个构造函数，Left :: a -> Either a和Right :: a -> Either所以

foldEither :: (a -> e) -> (b -> e) -> Either a b -> e
foldEither    useLeft      useRight    = f where 
f (Left a) = useLeft a
f (Right b) = useRight b  

树的广义褶皱

generalFold :: (a -> [t] -> t) -> Tree a -> t
generalFold useNode = f where
f (Node a ts) = useNode a (map f ts)

我们可以用它来对树做任何我们想做的事情：

-- maximum of a list, or zero for an empty list:
maxOr0 [] = 0
maxOr0 xs = maximum xs
height :: Tree a -> Int
height = generalFold maxPlus1 where
maxPlus1 a as = 1 + maxOr0 as
sumTree = generalFold sumNode where
sumNode a as = a + sum as
productTree = generalFold productNode where
productNode a as = a * product as
longestPath = generalFold longest where
longest a as = a + maxOr0 as

让我们测试一下它们：

ghci> example
Node 3 [Node 2 [],Node 5 [Node 2 [],Node 1 []],Node 10 []]
ghci> height example
3
ghci> sumTree example  -- 3 + sum[2, 5+sum[2,1], 10] = 3+2+5+2+1+10
23
ghci> productTree example  -- 3*(2*(5*(2*1))*10) = 3*2*5*2*1*10
600
ghci> longestPath example  -- 3 + maximum [2, 5+maximum[2,1], 10]
13
ghci> toList example -- 3 : concat [[2], 5:concat[[2],[1]], [10]]
[3,2,5,2,1,10]

Answer 2

考虑将模式推广到列表：

data Tree a = Node a [Tree a] | Nil
depth Nil = 0
depth (Node _ [a]) = 1 + depth a
depth (Node _ [a,b]) = 1 + max (depth a) (depth b)
depth (Node _ [a,b,c]) = 1 + max (max (depth a) (depth b)) (depth c)
etc...

好吧，您所做的只是找到每个子树的深度(map depth)，然后找到这些数字中的最大值(maximum)：

depth Nil = 0
depth (Node _ a) = 1 + maximum (map depth a)

您可以用相同的方式展平树，只需在子树上map：

treeToList (Node n a) = n : concat (map treeToList a)

你必须使用 concat，因为map collapse返回一个列表列表，而你只需要一个列表。或者，您可以为Foldable类型类定义一个实例，并自动获得toList :: Foldable t => t a -> [a]

import Data.Foldable
import Data.Monoid
instance Foldable Tree where 
foldMap f Nil = mempty
foldMap f (Node a n) = f a `mappend` mconcat (map foldMap n)

如果你非常仔细地仔细研究foldMap的定义，你会发现它只是一个更一般的treeToList，其中:被mappend取代，[]被mempty取代。那么合乎逻辑的是，你可以用幺半群([], ++)来写treeToList：

data List a = List {getList :: [a]}
instance Monoid (List a) where 
mempty = List []
mappend (List a) (List b) = List (a ++ b)
treeToList = getList . foldMap (List . (:[]))

Answer 3

一些提示：

看看map函数，它允许您将函数应用于列表中的每个元素。在您的情况下，您希望将depth应用于子列表中的每个Tree a。

获得该部分后，您必须在列表中找到最大深度。在谷歌上搜索"Haskell最大列表"，你会找到你需要的东西。