Need help understanding Haskell id function-CodePudding

Hello I have two versions of this function and I am having some trouble.

iter :: Int -> (a -> a) -> (a -> a)
iter n f
  | n > 0 = f . iter (n-1) f
  | otherwise = id

iter' :: Int -> (a -> a) -> (a -> a)
iter' n = foldr (.) id . replicate n

I cannot understand even after googling what does id actually do here.

Like for example if we come to the function with n = 3 and f x = x 1. When we iterate through the whole n and come to the point when id is being called what happens with our variables?

I am very big newbie so could you please explain as simplistically as possible.

CodePudding user response：

Summing a list xs = [x1,x2,...,xn] can be visualized as

x1   x2   ...   xn   0

Note that 0 at the very end. Its purpose is to handle the case where the list is empty, i.e. xs = [] and n=0. In such case the sum above reduces to 0, which is the correct sum for an empty list.

Also note that when the list is not empty the extra 0 has no impact ont the sum, so it's harmless. We indeed choose 0 since it is the neutral element for addition: x 0 = x for all x.

If we want to compute a product, we would write

x1 * x2 * ... * xn * 1

Note that * 1 at the end. Its role is exactly the same as the 0 seen above. Also note that 1 is the neutral element of multiplication: x * 1 = x for all x.

If we want to compute the composition of a list of functions, we would write

f1 . f2 . ... . fn . id

Note that . id at the end. Its role is exactly the same as the 0 and * 1 seen above. Also note that id is the neutral element of composition f . id = f for all f.

Hopefully this will help you understand why, every time we compute a fold like

x1 op x2 op ... op xn

where op is any binary operation, we want to end with ... op neutral_element so to handle the empty list case, and still act as a good base case for non-empty lists.

CodePudding user response：

You can inline:

iter 3 f
f . iter 2 f
f . (f . iter 1 f)
f . (f . (f . iter 0 f)
f . (f . (f . id))

-- adding the argument x
iter 3 f x
(f . (f . (f . id))) x
-- using (g . h) x == g (h x)
f ((f . (f . id)) x)
f (f ((f . id) x))
f (f (f (id x)))
f (f (f x))

And in the case of iter':

iter' 3 f
(foldr (.) id . replicate 3) f
foldr (.) id (replicate 3 f)
foldr (.) id [f, f, f]
(.) f (foldr (.) id [f, f]]
(.) f ((.) f (foldr (.) id [f]))
(.) f ((.) f ((.) f (foldr (.) id [])))
(.) f ((.) f ((.) f id))
f . (f . (f . id))