What is the most general way to compute the depth of a tree with something like a fold?

Question

What minimal (most general) information is required to compute depth of a Data.Tree? Is instance of a Data.Foldable sufficient?

I initially tried to fold a Tree and got stuck trying to find right Monoid similar to Max. Something tells me that since Monoid (that would compute depth) needs to be associative, it probably cannot be used to express any fold that needs to be aware of the structure (as in 1 + maxChildrenDepth), but I'm not certain.

I wonder what thought process would let me arrive at right abstraction for such cases.

Answer 1

I can't say if it's a minimal/most general amount of information. But one general solution is that a given structure

• is a catamorphism
• underlying functor of the catamorphism is Foldable so that it's possible to enumerate sub-terms.

Here is sample code using recursion-schemes.

{-# 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

Answer 2

To answer the first question: Data.Foldable is not enough to compute the depth of the tree. The minimum complete definition of Foldable is foldr, which always has the following semantics:

foldr f z = Data.List.foldr f z . toList

In other words, a Foldable instance is fully characterized by how it behaves on a list projection of the input (ie toList), which will throw away the depth information of a tree.

Other ways of verifying this idea involve the fact that Foldable depends on a monoid instance which has to be associative or the fact that the various fold functions see the elements one by one in some particular order with no other information, which necessarily throws out the actual tree structure. (There has to be more than one tree with the same set of elements in the same relative order.)

I'm not sure what the minimal abstraction would be for trees specifically, but I think the core of your question is actually a bit broader: it would be interesting to see what minimum amount of information is needed to compute arbitrary facts about a type with a fold-like function.

To do this, the actual helper function in the fold would have to take a different sort of argument for each sort of data structure. This naturally leads us to catamorphisms, which are generalized folds over different data types.

You can read more about these generalized folds on a different Stack Overflow question: What constitutes a fold for types other than list? (In the interest of disclosure/self-promotion, I wrote one of the answeres there :P.)