最初の質問に答えるために: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人が書いています。)
「最小限の情報」の意味を定義します。私は、ツリー自体は、それが得られるほどシンプルであると思っています。 – leftaroundabout
私はこの質問がたくさん好きです。おそらく、関連する質問は、折りたたみ式「Functor」の「Alternative」と「Applicative」構造の両方を使用するTraversableのようなものがありますか? –
(私が思っていることのいくつかの詳細:明らかな 'Functor'インスタンスで' data Depth a = Depth Nat'を定義するのは難しくありません。 'Applicative'モノイドは'(+、0) –