Каков самый общий способ вычислить глубину дерева с чем-то вроде складки?

Какая минимальная (самая общая) информация требуется для вычисления глубины a Data.Tree? Достаточен ли пример a Data.Foldable?

Сначала я попытался fold a Tree и застрял, пытаясь найти подходящее Monoid, похожее на Max. Что-то подсказывает мне, что поскольку Monoid (который будет вычислять глубину) должен быть ассоциативным, он, вероятно, не может быть использован для выражения любой форы, которая должна быть осведомлена о структуре (как в 1 + maxChildrenDepth), но я не уверен.

Интересно, какой процесс мышления позволил бы мне прийти к правильной абстракции для таких случаев.

Ответы

Ответ 1

Я не могу сказать, является ли это минимальным/наиболее общим объемом информации. Но одно общее решение заключается в том, что данная структура

  • это катаморфизм
  • нижележащий функтор катаморфизма - Foldable, так что можно перечислять подтермы.

Вот пример кода с использованием рекурсивных схем.

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

Ответ 2

Чтобы ответить на первый вопрос: Data.Foldable недостаточно , чтобы вычислить глубину дерева. Минимальное полное определение Foldable foldr, которое всегда имеет следующую семантику:

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

Другими словами, экземпляр Foldable полностью характеризуется тем, как он ведет себя в проекции списка ввода (т.е. toList), который отбрасывает информацию о глубине дерева.

Другие способы проверки этой идеи связаны с тем, что Foldable зависит от экземпляра моноида, который должен быть ассоциативным, или того факта, что различные функции fold видят элементы один за другим в определенном порядке без какой-либо другой информации, что обязательно выбрасывает фактическую древовидную структуру. (В одном и том же относительном порядке должно быть несколько деревьев с одним и тем же набором элементов.)

Я не уверен, какая минимальная абстракция будет для деревьев конкретно, но я думаю, что суть вашего вопроса на самом деле немного шире: было бы интересно узнать, какой минимальный объем информации необходим для вычисления произвольных фактов о тип со складной функцией.

Чтобы сделать это, фактическая вспомогательная функция в сложении должна была бы принимать разные аргументы для каждого типа структуры данных. Это, естественно, приводит нас к катаморфизмам, которые представляют собой обобщенные складки по разным типам данных.

Вы можете узнать больше об этих обобщенных складках в другом вопросе о переполнении стека: Что представляет собой складку для типов, отличных от списка? (В интересах раскрытия/самостоятельности -промотив, я написал один из ответов: P.)