0

I read that, map can be defined using foldr, i.e. it is a primitive recursive function. At least for lists.

Now my question: Why is Functor not a sub type class of Foldable? And if fmap can only be defined in terms of foldr for lists, what makes them special?

Looking at a definition of map with foldr:

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

I could use Monoids to get to:

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

But sadly I'm not much enough of a Haskell magician to get away with cons.

4

1 回答 1

9

但可悲的是，我还不足以成为一个 Haskell 魔术师来逃避缺点。

您发现了不允许将每个 Foldable 都设为 Functor 的根本问题；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”，但明显不同。这意味着折叠树的行为会丢失一些您无法恢复的信息（即左子树、右子树和元素之间的边界）。由于您无法使用实例的结果来区分 x 和 y Foldable，因此您不可能只使用这些方法来编写fmap这样的代码。fmap id == id我们不得不求助于模式匹配并使用构造函数来写出Functor实例。

于 2017-03-16T23:26:32.087 回答