在haskell中对列表中的第n项应用函数n次

Question

我需要一个高阶函数g，它将另一个函数f应用于一个整数列表，使得

g = [f x1, f(f x2), f(f(f x3)), … , f^n(xn)]

我知道我可以映射像

这样的函数

g :: (Int -> Int) -> [Int] -> [Int]
g f xs = map f xs

我也可以应用n次像

这样的函数

g f xs = [iterate f x !! n | x <- xs]

其中n为应用该函数的次数。我知道我需要使用递归，所以我认为这两个选项都没有用。

预期输出:

g (+1) [1,2,3,4,5] = [2,4,6,8,10]

Answer 1

您可以使用显式递归，每次传递要应用的函数和列表的尾部，因此:

g :: (Int -> Int) -> [Int] -> [Int]
g f = go f
where go _ [] = []
go fi (x:xs) = … : go (f . fi) xs

我在这里把…部分的实现留作练习。

另一个选择是使用两个列表，一个函数列表和一个值列表。在这种情况下，函数列表是iterate (f .) f:可以应用的函数的无限列表。然后我们可以将g实现为:

g :: (Int -> Int) -> [Int] -> [Int]
g f = zipWith ($) (iterate (f .) f)

Answer 2

听起来像是foldr的另一种用法:

applyAsDeep :: (a -> a) -> [a] -> [a]
applyAsDeep f = foldr (x xs -> f x : map f xs) []
λ> applyAsDeep (+10) [1,2,3,4,5]
[11,22,33,44,55]

Answer 3

如果你想做得过火一点…

import GHC.Exts (build)
g :: (a -> a) -> [a] -> [a]
g f xs0 = 
build $ c n -> 
let go x r fi = fi x `c` r (f . fi) 
in foldr go (const n) xs0 f