CODEWITHSUNDEEP
haskellrecursionhigher-order-functions
jamie
jamie

Reputation: 13

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

I want a higher-order function, g, that will apply another function, f, to a list of integers such that

g = [f x1, 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]

Upvotes: 1

Views: 299

Answers (3)

dfeuer
dfeuer

Reputation: 48611

If you want to go a bit overkill ...

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

Upvotes: 1

pedrofurla
pedrofurla

Reputation: 12783

Sounds like another use for 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]

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477210

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)

Upvotes: 3

Related Questions