Можно ли частично применить функтор - PullRequest
Новая
       33

Можно ли частично применить функтор

6 голосов
/ 16 апреля 2019

Я пытаюсь реализовать fmap для следующего типа: 

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

instance Functor Tree where
        fmap _ Empty=Empty
        fmap f (Leaf x)=Leaf (f x)
        fmap f (Node t left right)=Node (f t) left right

Я получаю ошибку несоответствия типов:

Ошибка 

* Couldn't match type `a' with `b'
      `a' is a rigid type variable bound by
        the type signature for:
          fmap :: forall a b. (a -> b) -> Tree a -> Tree b
        at Monad.hs:8:9-12
      `b' is a rigid type variable bound by
        the type signature for:
          fmap :: forall a b. (a -> b) -> Tree a -> Tree b
        at Monad.hs:8:9-12
      Expected type: Tree b
        Actual type: Tree a

Почему я получаю эту ошибку, но когда я также применяю fmap к дочерним узлам, она без проблем компилируется: 

fmap f (Node t left right) = Node (f t) (fmap f left) (fmap f right)

Означает ли это, что все a -sвнутри Tree должно как-то стать b -с?и я имею дело только с нефунктором в первом случае?^

1 Ответ

8 голосов
/ 16 апреля 2019

Означает ли это, что все a -ы в Tree должны как-то стать b -ами?и я имею дело только с нефунктором в первом случае?^

Да, все верно.Вы пытаетесь реализовать fmap :: (a -> b) -> Tree a -> Tree b, но когда вы пишете: 

fmap f (Node t left right) = Node (f t) left right

Вы пытаетесь вызвать Node :: b -> Tree b -> Tree b -> Tree b с аргументами f t :: b, left :: Tree a и right :: Tree a.Единственный способ превратить Tree a в Tree b - через fmap f :: Tree a -> Tree b, поэтому: 

fmap f (Node t left right) = Node (f t) (fmap f left) (fmap f right)

Работает, как и ожидалось.

...