折り畳みのようなものでツリーの深さを計算する最も一般的な方法は何ですか？

Question

Data.Treeの深さを計算するには最小限の（最も一般的な）情報が必要ですか？ Data.Foldableのインスタンスは十分ですか？

私は最初にfoldをTreeにしようとしましたが、Maxに似た正しいMonoidを見つけようとしました。 （1 + maxChildrenDepthのように）Monoid（深さを計算する）は結合する必要があるため、おそらく構造を認識する必要のある折り畳みを表現することはできませんが、私は確信していません。

どのようなプロセスが、私がそのような場合の正しい抽象化に到達することができるのだろうかと思います。

Answer 1

最小/最も一般的な情報量であるとは言えません。しかし、一つの一般的な解決策は、与えられた構造

• がcatamorphismのcatamorphism
• 基礎となるファンクタは、それがサブ用語を列挙することができますようにFoldableされていることです。

recursion-schemesを使用したサンプルコードです。残念なことに、再帰スキームでは、異型にはFoldableを使用しているため、多少混乱します。

{-# LANGUAGE TypeFamilies, FlexibleContexts #-} 

import qualified Data.Foldable as F 
import Data.Functor.Foldable 
import Data.Semigroup 
import Data.Tree 

depth :: (Foldable f, F.Foldable (Base f)) => f -> Int 
depth = cata ((+ 1) . maybe 0 getMax . getOption 
       . F.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 F.Foldable (TreeF a) where 
    foldMap f (NodeF _ ts) = F.foldMap f ts 

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

Answer 2

最初の質問に答えるために：Data.Foldableはツリーの深さを計算するのに十分なではありませんが。 Foldableの最小完全な定義は、常に、次の意味を有するfoldrある：すなわち

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

、Foldableインスタンスは、入力（すなわちtoList）のリスト突起上にどのように動作するかによって特徴付け完全ありますこれはツリーの深さ情報を捨て去ります。

Foldableが必然連想なければならないモノイドインスタンスや各種 fold機能がない他の情報をいくつかの特定の順序で要素一つずつ参照するという事実に依存することを含む、この考えを検証する

他の方法実際のツリー構造を破棄します。 （同一の相対的な順序で同じ要素を持つ複数のツリーが存在する必要があります）

最小限の抽象化が木の場合は何かわかりません具体的には実際には少し大きくなります。折りたたみのような機能を持つタイプについて任意の事実を計算するために必要な情報の最小量を確認することは面白いでしょう。

これを行うには、折りたたみの実際のヘルパー関数は、データ構造の各種類ごとに異なる種類の引数を取る必要があります。これは当然異なる種類のデータで一般化された折り畳みであるの変造に自然につながります。

これらの一般化されたフォールドについて、別のスタックオーバーフローに関する質問を読むことができます：What constitutes a fold for types other than list?（公開/自己宣伝のため、回答者の1人が書いています。）