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

问题描述

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

以下是我用于二叉树的代码。

   - 二叉树的深度。 
 
深度:: Tree a  - >深度（深度x1）（深度x2）
深度（节点n x1 x2）= 1 + max（深度x1）
深度nil = 0 
深度
  

我怎样才能修改一般的树？普通树包含树木清单，这就是我遇到困难的地方。

其次，我想把树变成一个列表（这样我可以进行诸如计算总和等操作）。

同样，我可以计算出二叉树，但不是一般树。

   - 树形成一个列表。 
 
 treeToList :: Tree a  - > [a] 
 treeToList Nil = [] 
 treeToList（Node n x1 x2）
 = collapse x1 ++ [n] ++折叠x2 
  

解决方案

使用 Foldable Functor 映射函数

user2407038的好答案向你展示了如何手工编写 Foldable 实例，这是非常好的建议，你可以使用 foldMap 不仅仅是为了制作 treeToList ，而且还要制作其他功能。

GHC自动派生这些实例：

  { - ＃LANGUAGE DeriveFunctor，DeriveFoldable＃ - } 
 
导入Data.Monoid 
导入Data.Foldable 
 
数据树a =节点a [Tree a] 
派生（Show，Functor，Foldable）
  
 
 
 <$ c  
 $ c> example :: Tree Int 
 ex充足=节点3 [节点2 []，节点5 [节点2 []，节点1 []]，节点10 []] 
 
  -  3 
  -  | 
  -  +  -  + ----- + 
  -  2 5 10 
  -  | 
  -  +  -  + 
  -  2 1 
  
让我们使用 fmap 将所有东西都乘以10： 
 
 
 >示例
节点3 [节点2 []，节点5 [节点2 []，节点1 []]，节点10 []] 
> fmap（* 10）示例
节点30 [节点20 []，节点50 [节点60 []，节点10 []]，节点100 []] 
  pre> 
 
 
使用 Monoid 合并值
 
 
 
 Monoid允许您合并（ mappend ）值，并具有一个名为 mempty 的无所事事/标识值。 
列表是一个Monoid，其中 mempty = [] 和 mappend =（++），数字是例如，使用（+）（ Sum  monoid），使用（*）（ Product  monoid），使用最大值（我必须手工编写 Max  monoid）。
 
 
 
我们将使用 foldMap 想要使用： 
 
 
 > foldMap Sum例子
 Sum {getSum = 23} 
> foldMap产品示例
产品{getProduct = 600} 
> foldMap Max示例
 Max {unMax = 10} 
  
您可以定义自己的monoid像这样 - 这里是如何制作Max monoid：
 
 
  instance（Ord a，Bounded a）=> Monoid（Max a）其中
 mempty = Max minBound 
 mappend（Max a）（Max b）= Max $如果a> = b则a else b 
  
 
 
 
您可以制作的最普通的折叠
 
 
 
在这个很好的问题，并提供了很好的答案，Haskell的顶级提问者， MathematicalOrchid 询问如何将fold推广到其他数据类型。这个问题的答案很好，值得一读。
 
 
 
广义折叠只是用函数替换数据类型的每个构造函数，并计算得到一个值。
 
 
 
手动的方式是查看每个构造函数的类型，并创建一个函数，该函数使用函数参数来匹配每个构造函数和对象本身的参数，并返回一个值。 
 
 
 
 示例：       c $ c>有两个构造函数，（:) :: a  - > [a]  - > [a] 和 [] :: [a]  so 
  foldList ::（a  - > l  - > l） - > l  - > [a]  - > l 
 foldList useCons useEmpty = f其中
f（a：as）= useCons a（f as）
f [] = useEmpty 
  
 $ b 
  ab 有两个构造函数， Left :: a  - >无论是还是 Right :: a  - >或者 so 
  foldEither ::（a  - > e） - > （b→e）→>无论是b  - > e 
 foldEither useLeft useRight = f其中
f（Left a）= useLeft a 
f（Right b）= useRight b 
  
 
 
 
树的通用折叠
 
 
 
  generalFold ::（a  - > [ t]→t）→>树a  - > t 
 generalFold useNode = f其中
f（Node a ts）= useNode a（map f ts）
  
我们可以使用它来完成我们想要的任何事情： 
 
 
   - 最大值一个列表或零列表：
 maxOr0 [] = 0 
 maxOr0 xs =最大值xs 
 
 height：Tree a  - > Int 
 height = generalFold maxPlus1其中
 maxPlus1 a as = 1 + maxOr0 as 
 
 sumTree = generalFold sumNode其中
 sumNode a as = a + sum as 
 
 productTree = generalFold productNode其中
 productNode a as = a *产品为
 
 longestPath = generalFold最长其中
最长a as = a + maxOr0为
  
我们来测试它们： 
 
 
  ghci的>示例
节点3 [节点2 []，节点5 [节点2 []，节点1 []]，节点10 []] 
 ghci>身高例子
 3 
 ghci> sumTree示例-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>最长路径示例-3 +最大值[2,5 +最大值[2,1]，10] 
 13 
 ghci> toList示例 -  3：concat [[2]，5：concat [[2]，[1]]，[10]] 
 [3,2,5,2,1,10] 
  
 
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.


Here's the code I have for binary trees.
--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

解决方案
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 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
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 []]


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).

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


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. 

Examples:

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


Generalised fold for your tree

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
Let's test them:
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屋！