Прикрепить дополнительную информацию на каждом уровне рекурсивного типа данных?

Question

(Это не вопрос Хаскеля).

У меня рекурсивная структура данных.Я хотел бы приложить какую-то дополнительную информацию на каждом уровне.Вот упрощенный пример, в котором я добавляю X или Y к каждому уровню дерева:

import Data.Functor.Foldable

data Wrap a = X a | Y a
  deriving Show

data TreeF a b = Leaf a | TreeF a b b
  deriving Show

depth1 :: Wrap (TreeF Int ())
depth1 = X (Leaf 1)

depth2 :: Wrap (TreeF Int (Wrap (TreeF Int ())))
depth2 = Y (TreeF 1 (X $ Leaf 1) (Y $ Leaf 1))

-- depthInfinity :: Fix something something ...

(определение TreeF для меня неестественноЯ бы предпочел определить data Tree a = Leaf a | Tree a (Tree a) (Tree a), но я не могу понять, как сформулировать свой вопрос, если я это сделаю. Поэтому вместо этого я написал его в виде функтора Base, ala Data.Functor.Foldable .)

Тип Wrap может использоваться для прикрепления информации X или Y к каким-либо данным.depth1' - это глубина-1 TreeF, в которой флаг Wrap был прикреплен на каждом уровне (он имеет только один уровень).depth2 - это глубина-2 TreeF, в которой, опять же, флаг Wrap был прикреплен на каждом уровне (у него есть два уровня).

Как мне создать «Обернутое дерево» изпроизвольная глубина?Как я должен написать его тип подписи?Есть ли теоретико-категоричный термин для такого вида коллажей данных?

Answer 1

Вы можете использовать

Fix (Compose Wrap (TreeF Int))

, но я бы, наверное, не стал.Если вы определенно хотите пойти по пути открытой рекурсии, создание собственного варианта Fix, вероятно, более разумно:

data WrapData = X | Y
data LabeledFix a f = Labeled a (f (LabeledFix a f))
-- ... and then use LabeledFix WrapData (TreeF Int)

Но даже более разумным является использование простой старой закрытой рекурсии.Вам даже не нужно делать свой тип более особенным, чем он был раньше;просто:

data Tree a = Leaf a | Branch a (Tree a) (Tree a)
-- ... and then use Tree (WrapData, Int)