树的深度（哈斯克尔）

Question

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

这是我的二叉树代码。

--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不仅可以使用 make 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

让我们用fmap10 来乘以所有值：

> 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 []]

使用 aMonoid组合值

Monoid 允许您组合 ( mappend) 值，并且有一个名为 的无操作/标识值mempty。列表是一个幺半群，带有mempty = []和mappend = (++)，数字以多种方式是幺半群，例如，使用(+)（幺Sum半群）、使用(*)（幺Product半群）、使用最大值（我必须手写幺Max半群）。

我们将使用foldMap我们想要使用的幺半群来标记整数：

> 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]