无法用函子构造无限类型

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 -> b) 应用于类型为 BTree a 的左右子树。

这强制 a 与 BTree a 相同，这将要求 a 是无限类型（为了记录，您可以将其定义为 Fix BTree，其中 Fix f = Fix (f (Fix f))，这可能有用，但不是您想要的！）

Answer 2

您正在尝试将 f 应用于 a 类型的值（在 Leaf (f t) 中）和 BTree a 类型的值（在 Node (f a) (f b) 中） .为此，类型检查器需要找到某种方法来统一 a 和 BTree a，这只有在 a 是 BTree 类型的无限嵌套堆栈时才有可能；在 a 之上再添加一层 BTree 不会有效地改变它。

将 Node (f a) (f b) 更改为 Node (fmap f a) (fmap f b) 可确保 f 仅应用于 a.[=25 类型的值=]

无法用函子构造无限类型

Cannot construct infinite type with functor

haskell

functor