Каково правильное определение `развернуть` для нетегированного дерева?

Question

Я думал о том, как реализовать эквивалент unfold для следующего типа:

data Tree a = Node (Tree a) (Tree a) | Leaf a | Nil

Это было не сразу очевидно, так как стандарт unfold для списков возвращает значение и следующее начальное число. Для этого типа данных это не имеет смысла, так как нет никакого "значения", пока вы не достигнете конечного узла. Таким образом, имеет смысл возвращать новые семена или останавливаться на значении. Я использую это определение:

data Drive s a = Stop | Unit a | Branch s s deriving Show

unfold :: (t -> Drive t a) -> t -> Tree a
unfold fn x = case fn x of
    Branch a b -> Node (unfold fn a) (unfold fn b)
    Unit a     -> Leaf a
    Stop       -> Nil

main = print $ unfold go 5 where
    go 0 = Stop
    go 1 = Unit 1
    go n = Branch (n - 1) (n - 2)

Хотя это, кажется, работает, я не уверен, что так и должно быть. Итак, вот в чем вопрос: как правильно это сделать?

Answer 1

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

module Unfold where

Здесь мы начинаем по определению точку фиксации функтора f: это слой f затем следует еще одна точка фиксации:

newtype Fix f = InFix { outFix :: f (Fix f) }

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

data ListF a r = LNil | LCons a r
data TreeF a r = TNil | TLeaf a | TBranch r r

Списки и деревья являются соответственно точками фиксирования ListF и TreeF:

type List a = Fix (ListF a)
type Tree a = Fix (TreeF a)

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

Учитывая оригинальное семя, а также функцию взятия семени и создания одного слоя f где в рекурсивной структуре появляются новые семена, мы можем построить целую структуру:

unfoldFix :: Functor f => (s -> f s) -> s -> Fix f
unfoldFix node = go
  where go = InFix . fmap go . node

Это определение специализируется на обычном unfold в списке или ваше определение для деревьев. Другими словами: ваше определение действительно было правильным.