树的深度 (Haskell) [英] Depth of a tree (Haskell)

问题描述

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

I'm trying to figure out how to calculate the depth of a general tree in Haskell. I can figure out the solution for simple binary trees, but not for general trees with any number of leaves.

这是我的二叉树代码.

--depth of a binary tree.

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

我如何为一般的树修改这个?一般树包含一个树列表，这就是我遇到困难的地方.

How can I modify this for general trees? General trees contain a list of trees, and that is where I am encountering difficulty.

其次，我想把树变成一个列表(这样我就可以进行求和等操作)

Secondly, I want to turn the tree into a list (so I can do operations such as calculating the sum, etc.)

同样，我可以为二叉树计算出它，但不能为一般树计算出.

Again, I can figure it out for binary trees but not for general trees.

--tree into a list.

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

推荐答案

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

user2407038 的好答案 向您展示了如何手动编写一个 Foldable 实例，即非常好的建议，您可以使用foldMap 不仅可以制作treeToList，还可以制作方便的其他功能.

Use Foldable to get single values out, use Functor to map functions

user2407038's good answer shows you how to write a Foldable instance by hand, which is very good advice, and you can use foldMap not just to make treeToList, but also to make handy other functions.

GHC 可让您自动派生这些实例:

GHC lets you derive these instances automatically:

{-# LANGUAGE DeriveFunctor, DeriveFoldable #-}

import Data.Monoid
import Data.Foldable

data Tree a = Node a [Tree a] 
  deriving (Show,Functor,Foldable)

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

Let's use an example to test this out:

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

--   3
--   |
--   +--+-----+
--   2  5     10
--      |
--      +--+
--      2  1

让我们使用 fmap 将所有内容乘以 10:

Let's use fmap to multiply everything by 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 的无作为/标识值.列表是一个 Monoid，有 mempty = [] 和 mappend = (++)，数字是 moinoids 不止一种方式，例如，使用 (+)(Sum monoid)，使用 (*)(Product monoid)，使用最大值(我不得不手动 -编写 Max 幺半群).

Use a Monoid to combine values

A Monoid lets you combine (mappend) values, and has a do-nothing/identity value called mempty. Lists are a Monoid, with mempty = [] and mappend = (++), numbers are moinoids in more than one way, for example, using (+) (the Sum monoid), using (*) (the Product monoid), using maximum (I had to hand-write the Max monoid).

我们将使用 foldMap 用我们想要使用的幺半群标记 Ints:

We'll use foldMap to tag the Ints with what monoid we want to use:

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

您可以根据自己的喜好定义自己的幺半群 - 以下是制作最大幺半群的方法:

You can define your own monoid however you like - here's how to make the Max monoid:

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 询问如何将折叠推广到其他数据类型.问题的答案很好，值得一读.

The most general fold you can make

In this great question with great answers, Haskell's top asker, MathematicalOrchid asks how to generalise fold to other data types. The answers to the question are great and worth reading.

通用折叠只是将数据类型的每个构造函数替换为一个函数，然后计算得出一个值.

A generalised fold simply replaces each constructor of the data type with a function and evaluates to get a value.

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

The hand-rolled way is to look at the types of each of the constructors, and make a function that takes a function argument to match each constructor and an argument for the object itself, and returns a value.

示例:

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

[] has two constructors, (:) :: a -> [a] -> [a] and [] :: [a] so

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

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

Either a b has two constructors, Left :: a -> Either a and Right :: a -> Either so

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)

我们可以用它对树做几乎任何我们想做的事情:

we can use that to do pretty much anything we want to to a tree:

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

这篇关于树的深度 (Haskell)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！