Haskell-接受函数列表的函数

Question

我需要编写一个函数来接受函数列表和一个值作为参数.必须依次对值中的每个函数应用.

例如,如果我的函数被调用compFuncs...

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

我已经可以告诉我使用a 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

顺便说一句,可以像这样折叠的类型用作"身份"的元素被称为monoid*,并且a -> a是Endo monoid.

*还有一项要求是,用于组合值的函数(如(.)for Endo或(+)for 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