Wie lässt sich die Tiefe eines Baumes am ehesten mit einer Falte berechnen?

Question

Welche minimale (allgemeinste) Information wird benötigt, um die Tiefe eines Data.Tree zu berechnen? Ist Instanz von Data.Foldable ausreichend?

Ich versuchte zunächst fold ein Tree und blieb stecken versuchen, rechts Monoid ähnlich wie Max zu finden. Etwas sagt mir, dass, da Monoid (das würde Tiefe berechnen) muss assoziativ sein, es kann wahrscheinlich nicht verwendet werden, um jede Falte auszudrücken, die der Struktur bewusst sein muss (wie in 1 + maxChildrenDepth), aber ich bin mir nicht sicher.

Ich frage mich, welcher Denkprozess mich in solchen Fällen zur richtigen Abstraktion bringen würde.

Answer 1

Ich kann nicht sagen, ob es eine minimale/allgemeinste Menge an Informationen ist. Aber eine allgemeine Lösung ist, dass eine gegebene Struktur

• a catamorphism
• zugrunde liegenden Funktors des catamorphism ist Foldable so dass es möglich ist Unter Begriffe aufzuzählen.

Hier ist Beispielcode mit recursion-schemes. Leider verwendet Rekursionschemata Foldable für Katamorphismen, was es etwas verwirrend macht.

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

die erste Frage zu beantworten: Data.Foldableist nicht genug die Tiefe des Baumes zu berechnen. Die minimale vollständige Definition Foldable ist foldr, die folgende Semantik immer hat:

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

In anderen Worten, eine Foldable Instanz vollständig gekennzeichnet durch, wie es sich verhält auf einer Liste Projektion des Eingangs (dh toList) , die die Tiefeninformation eines Baumes wegwerfen wird.

Andere Möglichkeiten, diese Idee, dass Foldable hängt von einer Monoid Instanz beinhaltet die Überprüfung, die assoziativ oder die Tatsache sein, dass die verschiedenen fold Funktionen, um die Elemente nacheinander in einer bestimmten Reihenfolge ohne weitere Informationen zu sehen, die notwendigerweise wirft die eigentliche Baumstruktur aus. (Es muss mehr als einen Baum mit dem gleichen Satz von Elementen in der gleichen relativen Reihenfolge geben.)

Ich bin mir nicht sicher, was die minimale Abstraktion für Bäume wäre speziell, aber ich denke, der Kern Ihres Die Frage ist eigentlich ein bisschen breiter: Es wäre interessant zu sehen, welche minimale Menge an Information benötigt wird, um beliebige Fakten über einen Typ mit einer faltenartigen Funktion zu berechnen.

Um dies zu tun, müsste die eigentliche Hilfsfunktion in der Falte eine andere Art von Argument für jede Art von Datenstruktur nehmen. Dies führt uns natürlich zu Katamorphismen, die verallgemeinerte Falten über verschiedene Datentypen sind.

Sie können mehr über diese generalisierten Falten auf einer anderen Stack Overflow Frage lesen: What constitutes a fold for types other than list? (Im Interesse der Offenlegung/Eigenwerbung, schrieb ich eine der Antworten dort: P.)