如果可以使用Foldable来定义map，为什么在Foldable的定义中没有提到Functor

Question

我读到过，可以使用foldr定义map，即它是一个原始的递归函数。至少对于列表是这样的。

现在我的问题是:为什么Functor不是Foldable的子类型类？如果fmap只能根据列表的foldr定义，那么它们的特殊之处在于什么呢？

使用foldr查看map的定义：

myMap f xs = foldr step [] xs
    where step x ys = f x : ys

我可以使用Monoid来达到以下目的：

myMap f xs = foldr step mempty xs
    where step x ys = f x : ys

但遗憾的是，我不是一个足够的哈斯克尔魔术师，无法摆脱cons。

Answer 1

，但遗憾的是，我不是一个足够的哈斯克尔魔术师，无法逃脱惩罚。

您已经发现了一个根本问题，这个问题不允许让每个可折叠的元素都成为一个函数式函数；foldr丢弃了折叠的结构，只保留(相当于)它的元素列表。你不能“得过且过”，因为你不能知道数据的结构是什么，只给了一个Foldable实例。

给定树的以下(典型)定义：

data Tree a = Bin a (Tree a) (Tree a) | Tip

instance Functor Tree where
  fmap f (Bin a l r) = Bin (f a) (fmap f l) (fmap f r)
  fmap _ Tip = Tip

instance Foldable Tree where
  foldMap f (Bin a l r) = foldMap f l <> f a <> foldMap f r
  foldMap _ Tip = mempty

比较这两个树：

let x = Bin 'b' (Bin 'a' Tip Tip) Tip
let y = Bin 'a' Tip (Bin 'b' Tip Tip)

这两个树的toList都是"ab"，但明显不同。这意味着折叠树的行为会丢失一些您无法恢复的信息(即左子树、右子树和元素之间的边界)。由于不能使用Foldable实例的结果区分x和y，因此不可能只使用这些方法编写fmap以使fmap id == id能够使用这些方法。我们不得不求助于模式匹配和使用构造函数来写出Functor实例。