haskell，数据二叉树的仿函数

Question

我正在尝试为 Tree 编写仿函数(下面给出了这种类型的形式)

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

what about more elegant [...] solutions?

完全没问题。不使用任何辅助函数的所有其他解决方案看起来或多或少相同。我唯一要改变的是 = 的对齐方式s 和姓名 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的类型:

The second issue is that lecturer wrote signature: fmap :: (a -> b) -> f a -> f b […]

首先，讲师的签名有点错误。 fmap的完整签名是

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

约束 Functor f很重要。它限制了 fmap 的使用到 Functor 的实例.现在这不是你遇到的问题:

for me, it is (a->b) -> Tree a -> Tree b, but it is not accepted by compiler ghci. Where is the point?

啊，您已经尝试为 fmap 指定类型签名在 Functor Tree例如，对吗？

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

嗯，这是不允许的。毕竟 fmap的类型不是 (a -> b) -> Tree a -> Tree b ，但上面更一般的一个。它有点——但不完全——类似于对单个绑定(bind)使用两个类型签名:

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;博士 : fmap的类型由它在 class Functor 中的声明给出，它已由您选择的 f 指定在 instance定义。