haskellcomposition

Are applyN and composeN functionally equivalent?

I initially defined a function applyN to apply a given function a specific number of times to a value:

applyN :: Int -> (a -> a) -> a -> a
applyN n f = (!! n) . iterate f

Later, I wanted to eta-reduce the function argument f. While thinking about this, I realized that the type signature Int -> (a -> a) -> a -> a can also be viewed as Int -> (a -> a) -> (a -> a). This led me to suspect that applyN might be equivalent to repeated function composition. So I wrote this version:

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

My question is: Are these two implementations truly equivalent? That is, do they always return the same result for all inputs, or are there any cases where their behavior differs?

In a few simple tests, they appear to behave the same:

applyN   0 id     1 --     1
composeN 0 id     1 --     1

applyN   7 (* 2) 42 --  5376
composeN 7 (* 2) 42 --  5376

applyN   4 (^ 2)  2 -- 65536
composeN 4 (^ 2)  2 -- 65536

But I wonder if there are any subtleties in terms of laziness, performance, or edge cases that might cause them to differ.

Solution

  • Yes, they are equivalent in terms of their semantics.

    First, note that any polymorphic function of type

    Int -> (a->a) -> a -> a

    can only do one thing, i.e., compute a natural number N from the first argument, and then apply the function in the second argument N times to the third argument. If we ignore non termination, exceptions, unsafe functions and the like there is no other possible way to implement that type. This could be formally proved exploiting the so-called parametricity property of polymorphism.

    Your two implementations apply the function the same amount of times N, defining it as being equal to the first argument, so they are equivalent.

    The only difference between then is when their first argument is negative: !! causes a crash (exception), while replicate returns the empty list.

    The performance, instead, differs. Try applyN veryLargeN (const True) False against its composeN counterpart. You should observe that composeN is faster. This is because applyN must always traverse a list until the veryLargeNth position since it uses !!, while composeN can compute the result is this way:

    composeN veryLargeN (const True) False
= (foldr (.) id . replicate veryLargeN) (const True) False
= foldr (.) id (replicate veryLargeN (const True)) False
= foldr (.) id (const True : replicate (veryLargeN-1) (const True)) False
= (.) 
  (const True) 
  (foldr (.) id (replicate (veryLargeN-1) (const True)))
  False
= const True (foldr (.) id (replicate (veryLargeN-1) (const True)) False)
= True

    Essentially, composeN makes it possible to use a lazy function like const True.