apply a function n times to the n-th item in a list in haskell-CodePudding

I want a higher-order function, g, that will apply another function, f, to a list of integers such that g = [fx1, f(f x2), f(f(f x3)), … , f^n(xn)]

I know I can map a function like

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

and I could also apply a function n-times like

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

where n the number of times to apply the function. I know I need to use recursion, so I don't think either of these options will be useful.

Expected output:

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

CodePudding user response：

You can work with explicit recursion where you pass each time the function to apply and the tail of the list, so:

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

I here leave implementing the … part as an exercise.

Another option is to work with two lists, a list of functions and a list of values. In that case the list of functions is iterate (f .) f: an infinite list of functions that can be applied. Then we can implement g as:

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