Haskell-接受函数列表的函数

Question

我需要编写一个接受函数列表和值作为参数的函数。列表中的每个函数都必须依次应用于该值。

例如，如果我的函数名为 compFuncs...

compFuncs [f,g,h] val 相当于 f(g(h val))

我已经可以看出，使用 foldr 在这里会很有用，我可以在函数列表中的每个函数之间放置 . 运算符，然后将其应用于 val。然而，我无法完成它，这是我的尝试......

compFuncs :: [(a->a->a)] -> a -> a
compFuncs [] val = val
compFuncs (x:xs) val = foldr //Im lost here

有人可以帮我吗？

Answer 1

(我相信您打算将类型写为 composeFuncs :: [a -> a] -> a -> a，因为这就是它的使用方式。)

foldr其工作原理是用您指定的替换替换列表的构造函数。例如，foldr (+) 0 [1,2,3]通过获取列表 [1,2,3] 来工作，其实际构造为 1:2:3:[] ，并替换 (:)与 (+)和[]与 0如下:

1 : 2 : 3 : []
1 + 2 + 3 + 0

如果你考虑一个函数列表 [f,g,h]您想要应用于某个值，如 \x -> f (g (h x)) ，我们可以找到foldr通过寻找 (:) 的替代品和[] 。首先，让我们使用组合:

\x -> f (g (h x))
= (definition of (.))
\x -> (f . g . h) x
= (eta reduction)
f . g . h

这很接近，但我们必须对空列表构造函数做一些事情。我们需要用某种“不执行任何操作”或“空”函数来替换它。幸运的是，我们有id ，保证不会以任何方式改变结果:

f . g . h
= (definition of id)
f . g . h . id

现在我们可以看到折叠:

f . g . h . id
f : g : h : []

我们将其写为:

composeFuncs :: [a -> a] -> a -> a
composeFuncs = foldr (.) id

顺便说一句，可以像这样用充当“身份”的元素折叠的类型称为幺半群*，以及 a -> a是Endo幺半群。

* 还有一个附加要求，即用于组合值的函数，例如 (.)对于 Endo或(+)对于 Sum ，是结合的。您会注意到，这使我能够在不需要上面括号的情况下呈现它们。

编辑

作为发现此功能的另一种方法，让我们使用 GHC 7.8 的新类型孔功能。首先，我们从 composeFuncs 的定义开始有一些漏洞:

composeFuncs :: [a -> a] -> a -> a
composeFuncs = foldr _f _z

当 GHC 类型检查时，我们得到一个类型错误，我将其简化为相关行:

tmp.hs:6:22: Found hole ‘_f’ with type: (a -> a) -> (a -> a) -> a -> a …
tmp.hs:6:25: Found hole ‘_z’ with type: a -> a …

以 _z 开头，只有一个可能的 a -> a 类型的函数，那就是id 。对于 _f ，我们需要一个组合两个函数来给出一个新函数的函数。那当然是 (.) ，所以我们写:

composeFuncs :: [a -> a] -> a -> a
composeFuncs = foldr (.) id