是否可以使用地图定义foldr？

Question

在我定义map使用foldr问题之后,我想到了:

如果可以定义map使用foldr,相反的是什么？

从我的观点来看,这是不可能的,但我找不到合适的解释.谢谢您的帮助!

Answer 1

让我们从一些类型签名开始.

foldr :: (a -> b -> b) -> b -> [a] -> b
map :: (a -> b) -> [a] -> [b]

我们可以模拟map使用fold因为fold是一个通用运算符(这是一个关于这个属性的更数学但非常友好的论文).

我确信有一些创造性的方法可以map用来模拟foldr.这肯定是一个有趣的练习.但我不认为这是一个直截了当的,而不是"疯狂的无点"解决方案,为了解释它,让我们foldr暂时忘掉并专注于一个更简单的累积功能:

sum :: [Int] -> Int

sum == foldr (+) 0,这意味着foldr实现sum.如果我们可以实现foldr用map我们肯定可以实现sum用map.我们能做到吗？

我认为sum签名是一个崩溃的打击 - sum返回一个Int,并map始终返回一个东西的列表.所以也许map可以做重物,但我们仍然需要另一种类型的功能[a] -> a才能获得最终结果.在我们的例子中,我们需要一个类型的函数[Int] -> Int.这是非常不幸的,因为这正是我们首先想要避免的.

所以我猜答案是:你可以实现foldr使用map- 但它可能需要使用foldr:)

Answer 2

查看它的最简单方法是查看map保留列表的主干.如果你看一下更通用的fmap(这是map,但不仅仅是列表,而是Functor一般的s),它甚至是一个法则

fmap id = id

有许多方法可以"作弊",但在对问题的最直接解释中,折叠比地图更为通用.有一个很好的技巧,在Edward Kmett的镜头库中使用了很多.考虑Constmonad,其定义如下:

newtype Const a b = Const { runConst :: a }

instance Functor (Const a) where fmap _ (Const a) = Const a
instance (Monoid a) => Monad (Const a) where
    return _ = Const mempty
    Const a >>= Const b = Const (a <> b)

现在,你可以在一元映射操作方面制定倍mapM,只要结果类型为monoidal:

fold :: Monoid m => [m] -> m
fold = runConst . mapM Const