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

Question

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

如果可以定义 map使用 foldr ，相反呢？

从我的角度来看，这是不可能的，但我找不到合适的解释。
谢谢您的帮助!

Answer 1

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

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

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

我确信有一些创造性的方式来使用 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 :)