无法理解 Haskell 中的折叠

Question

我想要一个函数，它接受一个列表和一个数字，并将该列表中的所有函数应用于该数字。例如：

applyAll [(*3),(+1),\x->x+5] 2

将得到数字 24。

我的问题是我必须用 fold 来做，但我还不太明白。 LearnYouaHaskell 有点帮助，但我仍然很困惑。

关于如何执行此操作的任何帮助？

Answer 1

首先，让我们想想applyAll的类型：

applyAll :: Num a => [(a -> a)] -> a -> a

在此过程中，您从列表中创建单个值。这称为 folding（或 fold）。你的例子表明 applyAll 应该从右边开始，因为结果是

24 = 3 * (1 + (5 + (2)))

因此，它是正确的折叠。 Prelude（和一些变体）中有两个折叠列表的函数：foldl 和 foldr。后缀表示它是左折还是右折。如上所述，您需要正确的弃牌。让我们看看 foldr 的类型：

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

文档指出 (a -> b -> b) 是折叠函数，从列表（a 类型）和累加器（b 类型）中获取一个值。然后是初始值，最后是列表。

因此 applyAll 的第一个原型是

applyAll fns init = foldr ?? init fns

此时我们只使用类型。我们知道 applyAll 将列表作为第一个参数，将值作为第二个参数。我们知道 foldr 接受某种函数、一个值和一个列表。因此，初稿 正好符合 我们的目的。

我们快到了！缺少的是正确的折叠功能。请记住，我们正在寻找从列表和累加器中获取值的东西。但是，在我们的例子中，列表的值类型为 (a -> a)，累加器为 a。所以我们的函数应该有 type

?? :: (a -> a) -> a -> a

幸运的是，该功能实际上非常简单，广为人知，并且您可能经常使用。想一想：该函数应该采用另一个函数、一个值和 return 一个值。这听起来像是一个简单的函数应用程序，实际上 ($) 就是您要找的函数。

将所有这些东西放在一起创建 applyAll 留给你作为练习，但在这一点上，没有太多事情要做。

Answer 2

正如我在评论中提到的：fold（或者，更常见的是，reduce）是一个高阶函数，它对列表，另一个参数是前一个转换的 return 值；因此 "chaining" 对列表的所有元素进行转换。

使用这个逻辑，您可以直观地推断出如果您有一个函数列表，您的转换必须 return 另一个函数。但是它return应该是一个什么样的函数呢？事实证明，转换可以是函数组合操作本身。

示例（可能不是很地道，因为我明确避免使用无点符号 - 它可能会或可能不会帮助您更轻松地理解代码）：

-- composes a list of functions, the last element in the list being the innermost
applyAll :: [Int -> Int] -> (Int -> Int)
applyAll fs = foldr (.) id fs

-- usage:
main :: IO ()
main = print $ applyAll [(*3), (+1), \x->x+5] 2

无法理解 Haskell 中的折叠

Trouble understanding folds in Haskell

haskell