用折叠之类的东西计算树深度的最常用方法是什么？

Question

计算a的深度需要什么最小(最一般)的信息Data.Tree？是一个Data.Foldable足够的实例？

我起初试图fold一个Tree和被困试图找到合适的Monoid相似Max.有些东西告诉我,因为Monoid(这会计算深度)需要是关联的,它可能不能用于表达需要了解结构的任何折叠(如1 + maxChildrenDepth),但我不确定.

我想知道什么样的思维过程会让我在这种情况下得到正确的抽象.

Answer 1

我不能说它是否是最小/最一般的信息量.但一个通用的解决方案是给定的结构

• 是一种变形现象
• catamorphism的底层函子是Foldable可以枚举子项.

以下是使用递归方案的示例代码.不幸的是,递归方案Foldable用于catamorphisms,这使它有点混乱.

{-# LANGUAGE TypeFamilies, FlexibleContexts #-}

import Data.Functor.Foldable
import Data.Semigroup
import Data.Tree

depth :: (Recursive f, Foldable (Base f)) => f -> Int
depth = cata ((+ 1) . maybe 0 getMax . getOption
              . foldMap (Option . Just . Max))

-- Necessary instances for Tree:

data TreeF a t = NodeF { rootLabel' :: a, subForest :: [t] }

type instance Base (Tree a) = TreeF a

instance Functor (TreeF a) where
    fmap f (NodeF x ts) = NodeF x (map f ts)

instance Foldable (TreeF a) where
    foldMap f (NodeF _ ts) = foldMap f ts

instance Recursive (Tree a) where
    project (Node x ts) = NodeF x ts