Не может создать бесконечный тип с функтором

Question

Я пытаюсь определить экземпляры для Functor, Applicative и Monad для следующих type:

 data BTree a=Leaf a | Node  (BTree a) (BTree a) deriving (Eq,Show)

Я попытался реализовать экземпляр Functor следующим образом:

 instance Functor BTree where
        fmap f (Leaf t) =Leaf (f t)
        fmap f (Node a b) =Node (f a) (f b)

Что сработало

fmap f (Node a b)=Node (fmap f a) (fmap f b)

Я понимаю, что это неправильно, так как, будучи экземпляром functor, форма должна быть сохранена f a-> f b (в нашем случае Node).и в моей реализации вы получите f a -> b.

Что я не понимаю:

Почему это бесконечный тип?Учитывая Node (f a )(f b) где-то в иерархии, дочерний элемент Node будет Leaf, и я буду применять f к нему.

Answer 1

Вы пытаетесь применить f к значениям типа a (в Leaf (f t)) и к значениям типа BTree a (в Node (f a) (f b)).Чтобы это работало, средство проверки типов должно найти способ объединения a и BTree a, что возможно только в том случае, если a представляет собой бесконечно вложенный стек типов BTree;добавление еще одного слоя BTree поверх a не приведет к его эффективному изменению.

Изменение Node (f a) (f b) на Node (fmap f a) (fmap f b) гарантирует, что f будет только , примененным кзначения типа a.

Answer 2

Это бесконечный тип, потому что в этом случае f :: (a -> b) применяется к левому и правому поддеревьям, имеющим тип BTree a.

Это означает, что a - это то же самое, что и BTree a, что потребует, чтобы a был бесконечным типом (который для записи можно определить как Fix BTree, где Fix f = Fix (f (Fix f)), что может быть полезным, но не то, что вы хотите здесь!)