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

Question

我读过,map可以定义使用foldr,即它是一个原始的递归函数.至少对于名单.

现在我的问题:为什么Functor不是可折叠的子类型？如果fmap只能根据foldr列表来定义,那么它们的特殊性是什么？

查看mapfoldr 的定义:

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

我可以使用Monoids来:

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

但遗憾的是,我对Haskell魔术师来说还远远不够cons.

Answer 1

但遗憾的是,我对Haskell魔术师来说还远远不够.

你发现了一个根本问题,就是不允许每个可折叠的玩家都成为一个玩家.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实例.