Haskell, Functor для данных Binary Tree

Question

Я пытаюсь написать функтор для дерева (форма этого типа приведена ниже)

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

instance Functor Tree where 
    fmap f Empty = Empty 
    fmap f (Node a x y) = Node (f a) (fmap f x) (fmap f y) 

Это, кажется, работает, но что более элегантно (я новичок в haskell)? Вторая проблема заключается в том, что лектор написал подпись: fmap :: (a -> b) -> f a -> f b для меня, это (a->b) -> Tree a -> Tree b, но это не принято компилятором ghci. Где смысл?

Answer 1

Что касается более элегантных [...] решений?

Это прекрасно. Все другие решения, не использующие вспомогательные функции, будут выглядеть примерно одинаково. Единственное, что я хотел бы изменить это выравнивание = с и именами x и y в l и r (со ссылкой на левую и правую ветви):

instance Functor Tree where 
    fmap _ Empty  = Empty 
    fmap f (Node a l r) = Node (f a) (fmap f l) (fmap f r) 

Впрочем, это мое личное мнение. Давайте перейдем к главному вопросу, fmap «s типа:

Вторая проблема в том, что преподаватель написал подпись: fmap :: (a -> b) -> f a -> f b [...]

Прежде всего, подпись лектора является несколько неправильно. полная подпись fmap «s является

fmap :: Functor f => (a -> b) -> f a -> f b 

Ограничение Functor f важно. Он ограничивает использование fmap экземплярами Functor. Теперь это не проблема, с которой вы столкнулись:

для меня это (a->b) -> Tree a -> Tree b, но компилятор ghci не принимается. Где смысл?

Ах, вы пытались определить тип подписи для fmap в экземпляре Functor Tree, верно?

instance Functor Tree where 
    fmap :: (a -> b) -> Tree a -> Tree b 
    fmap = ... 

Ну, это недопустимо. В конце концов, fmap тип не(a -> b) -> Tree a -> Tree b, но более общий один выше. Это несколько —, но не совсем — похоже на использование двух подписей типа для одного связывания:

foo :: Eq a => a -> a -> Bool 
foo ::  () ->() -> Bool 

Это не разрешено ни. Обратите внимание, что вы можете включить подписи экземпляров with an extension, если вы действительно этого хотите.Если вы просто хотите, чтобы сделать это для документации, комментарий может быть использован вместо -XInstanceSigs:

instance Functor Tree where 
    -- fmap :: (a -> b) -> Tree a -> Tree b 
    fmap = ... 

TL; DR: тип fmap «s дается это декларация в class Functor, он уже указан ваш выбор от f в определении instance.

Answer 2

Ваше решение довольно элегантно. Другой вариант заключается в определении fmap с помощью traverse:

import Data.Traversable 

-- Preorder traversal based on the way you defined the Node constructor. Could use any traversal. 
instance Traversable Tree where 
    traverse _ Empty = pure Empty 
    traverse f (Node v l r) = Node <$> f v <*> traverse f l <*> traverse f r 

instance Functor Tree where 
    fmap = fmapDefault 

instance Foldable Tree where 
    foldMap = foldMapDefault 

Я бы не сказал, что это более элегантно, но если вы хотите, чтобы все эти случаи, и не хотят, чтобы их derive это содержательный способ сделать это.