haskell - 是否可以使用地图定义文件夹？

Question

在我定义map了foldr一个问题后，我想到了：

如果可以定义mapusing 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。如果我们可以实现foldrwithmap我们绝对可以实现sumwith map。我们能做到吗？

我认为sum' 签名是一个致命的打击 -sum返回一个Int，并且map总是返回一个列表。所以也许map可以做繁重的工作，但我们仍然需要另一个类型[a] -> a的函数才能获得最终结果。在我们的例子中，我们需要一个 type 的函数[Int] -> Int。这很不幸，因为这正是我们一开始就试图避免的。

所以我想答案是：你可以实现foldrusing map- 但它可能需要 using foldr:)

Answer 2

查看它的最简单方法是查看它map保留了列表的脊椎。如果您查看更一般的 fmap（它是 map，但不仅适用于列表，而且适用Functor于一般的 s），它甚至是一个定律

fmap id = id

有很多“作弊”的方法，但是在对您的问题最直接的解释中，折叠比地图更通用。Edward Kmett 的 Lens 库中有一个很好的技巧。考虑Const定义如下的 monad：

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，只要结果类型是幺半群：

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

Answer 3

如果您制作某种作弊助手功能：

f [x] a = x a
f (x:xs) a = f xs (x a)

foldr g i xs = f (map g $ reverse xs) i