Подтвердить что ты не робот

Tree Functor и Foldable, но с узлами. Есть ли какое-либо обобщение по этому поводу?

data Tree t = Empty | Node t (Tree t) (Tree t)

Мы можем создать экземпляр Functor и использовать

fmap :: (t -> a) -> Tree t -> Tree a

Но что, если вместо (t → a) я хочу (Tree t → a), чтобы я мог получить доступ к целому (Node t) не только t

treeMap :: (Tree t -> a) -> Tree t -> Tree a
treeMap f Empty = Empty
treeMap f [email protected](Node _ l r) = Node (f n) (treeMap f l) (treeMap f r)

То же самое со словом

treeFold :: (Tree t -> a -> a) -> a -> Tree t -> a

Существует ли какое-либо обобщение над такими функциями?

map :: (f t -> a) -> f t -> f a
fold ::  (f t -> a -> a) -> a -> f t -> a
4b9b3361

ОТВЕТЫ

Ответ 1

Вы только что обнаружили comonads! Ну, почти.

class Functor f => Comonad f where
  extract :: f a -> a
  duplicate :: f a -> f (f a)

instance Comonad Tree where
  extract (Node x _ _) = x   -- this one only works if your trees are guaranteed non-empty
  duplicate [email protected](Node n b1 b2) = Node t (duplicate b1) (duplicate b2)

С помощью duplicate вы можете реализовать свои функции:

treeMap f = fmap f . duplicate
freeFold f i = foldr f i . duplicate

Чтобы сделать это правильно, вы должны обеспечить непустоту системой типов:

type Tree' a = Maybe (Tree'' a)

data Tree'' t = Node' t (Tree' t) (Tree' t)
   deriving (Functor)

instance Comonad Tree'' where
  extract (Node' x _ _) = x
  duplicate [email protected](Node' _ b1 b2) = Node' t (fmap duplicate b1) (fmap duplicate b2)