无法用仿函数构造无限类型

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将是Leafand我将应用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))，这可能是有用的，但不是你想要的！）