CODEWITHSUNDEEP
haskell
softshipper
softshipper

Reputation: 34061

How the recursion get expanded

I have following function, that do the function composition:

applyTimes :: (Eq a, Num a) => a -> (b -> b) -> b -> b
applyTimes 0 f b = b
applyTimes n f b = f . applyTimes (n-1) f $ b

and I have following expression: 

applyTimes 5 (+1) 5

Could someone please write out the evaluation?
It is difficult to imaging, how it will be expanded.

Upvotes: 1

Views: 62

Answers (1)

Bartek Banachewicz
Bartek Banachewicz

Reputation: 39370

applyTimes 5 (+1) 5 =
  (+1) . applyTimes 4 (+1) $ 5

applyTimes 5 (+1) 5 =
  (+1) . (
    (+1) . applyTimes 3 (+1)
  ) $ 5

-- ...

applyTimes 5 (+1) 5 =
  (+1) . (                -- 4
    (+1) . (              -- 3
      (+1) . (            -- 2
        (+1) . (          -- 1
          (+1) . const    -- 0
        )
      )
    )
  ) $ 5

I put in const because that's what you get after last applyTimes 0 f is evaluated.

Or, in flattened form:

applyTimes 5 (+1) 5 = (+1) . ((+1) . ((+1) . ((+1) . ((+1) . const))))) $ 5
                    = (+1) .  (+1) .  (+1) .  (+1) .  (+1) . const      $ 5

The name can be kind of misleading, since the "apply f n times"1 is actually done by applying a function composed of n repetitions of f, once.

What I could also see as confusing is where the actual application happens; perhaps eta-reducing it makes it clearer:

applyTimes n f = f . applyTimes (n-1) f

1You could imagine a perhaps simpler implementation:

applyTimes 0 f x = x
applyTimes n f x = f $ applyTimes (n-1) x

Upvotes: 2

Related Questions