haskell - 关于haskell高阶函数

Question

我被要求编写一个具有 type 的函数“管道” [a -> a] -> [a] -> [a]，在这样的管道中，原始函数列表中的每个函数依次应用于输入的每个元素。例如，管道[(+1),(*2),pred] [1,2,3]将返回[1,3,5]。

解决方案表中的答案是pipeline = map . foldr (.) id，我不太明白。这个解决方案怎么会出现？

Answer 1

一种思考方式foldr是

foldr f z xs

将每个 (:) 替换为xswithf并将空列表替换为z

注意

[(+1), (*2)]

是简写

(+1) : (*2) : []

您现在应该能够看到什么

foldr (.) id   ((+1) : (*2) : [])

评估为。从这里，您将能够理解整个表达式。

Answer 2

折叠不知何故相当令人困惑，尽管它们实际上非常简单。尤其是正确的折叠：它基本上什么都不做，只是:用一些替代的给定函数替换列表中的每个，并将列表nil替换为 init 值。对于您的示例：

foldr (.) id [(+1),(*2),pred]
≡ foldr (.) id ( (+1) : (*2) : pred : [] )
≡                (+1) . (*2) . pred . id

所以这只是将列表中的所有函数链接到一个大组合。

一旦你有了这个链，将它应用到另一个列表中的所有值是微不足道的，对于map.

Answer 3

问题的症结在于具有类型的函数：[a -> a] -> (a -> a)即将函数列表转换为一个函数。

foldr有类型：(b -> c -> c) -> c -> [b] -> c

让我们看看类型如何匹配：

• (b -> c -> c) -> c -> [b] -> c
• 替换b为(a -> a)：((a -> a) -> c -> c) -> c -> [a -> a] -> c
• 替换c为(a -> a)：((a -> a) -> (a -> a) -> (a -> a)) -> (a -> a) -> [a -> a] -> (a -> a)
• 函数的类型(.)是(b -> c) -> (a -> b) -> a -> c，这是我们在前面签名中的第一种类型，（我们都是a），所以我们可以(.)在那里使用。
• 对于第二部分，即(a -> a)我们可以使用id函数。
• 让我们适合这些：(.) id我们只剩下[a -> a] -> (a -> a)部分，这是我们需要的
• 所以，foldr (.) id给我们[a -> a] -> (a -> a)

之后，该map部分只是将结果函数应用于foldr列表的每个元素。

注意：使用白板来理解所有这些，直到你的潜意识习惯这样做；）