Haskell Higher Order Functions and Associativity

3
votes

I'm learning FP and have a few confusion after playing around with GHCi.

Say I have 2 simple functions:

twice :: (a -> a) -> (a -> a)
twice f a = f (f a) -- Equation 1

double :: Int -> Int
double = \x -> x * 2

Decomposing the evaluation twice twice twice double 3 (note that 3xtwice+1xdouble), I would have:

{-
   twice twice twice double 3
== (twice twice twice double) 3
== (twice twice (twice double)) 3
== (twice (twice (double double 3))) 
== (twice ((double double) (double double 3))) 
== (((double double) (double double)) ((double double) (double double 3))) 
== 768
-}
  • Is this correct?
  • According to this, if my definition of twice is changed as twice f a = f f a -- Equation 2, I should decompose the evaluation, with left associativity, as:
{-
   twice (twice twice double) 3
== (twice twice double) (twice twice double) 3
== ((twice double)(twice double)) ((twice double)(twice double)) 3
== ((double double)(double double)) ((double double)(double double)) 3
== (double (double (double (double (double (double (double (double 3 ) ) ) ) ) ) )
== 768
-}

right?

  • However, the strangest part is GHC REPL gave me the answer of 196608 (2^16*3):
> twice twice twice double 3
196608

which then makes me so confusing. Where would I make the mistake? Thanks.

2
haskellfunctional-programmingghchigher-order-functions
Function application is left associative. So, twice twice twice double 3 is ((((twice twice) twice) double) 3. – alias
Thanks for the response. I also read the article regarding the same issue. However, it quite not make sense to me in this case. In particular, could you clarify what is the type of (twice twice) ? How the function (twice twice) takes func double in? Since :t (twice twice) is ((a -> a) -> (a -> a)) -> (a -> a) right? – Tuan
It's still > :t (twice twice) (twice twice) :: (a -> a) -> a -> a Thanks. I think I get it now. – Tuan

2 Answers

5
votes

As the comment said, function application is left associative, so:

twice twice twice double 3 == (((twice twice) twice) double) 3

which is not the same as:     twice (twice twice double 3)

As requested in your comment: note that twice returns the same type of its argument. So, the type of twice twice is just ((a -> a) -> (a -> a))

Now, let's expand the whole expression:

(((twice twice) twice) double) 3 ==> ((twice (twice twice)) double) 3
                                 ==> (((twice twice) ((twice twice) double)) 3
                                 ==> (twice (twice ((twice twice) double))) 3
                                 ==> (twice (twice (twice (twice double)))) 3

twice double ==> double^2
twice (twice double) ==> double^4
twice (twice (twice double)) ==> double^8
twice (twice (twice (twice double))) == double^16

and double^16 3 == 2^16 * 3 as you found.

1
votes

Assume that n is a natural number and g n is defined as follows, informally:

g n = \f x -> f (f (f (.... (f x))))  -- n times f on x

In your case, twice f x = g 2 f x.

Then, one can prove that

g n (g m) f x = g (m^n) f x

Indeed, 

g n (g m) f x =
(g m (g m (g m (g m .... (g m f))))) x =  -- n times (g m) on f

so it's taking the "m-times repeated f" function, and then repeating that m times to form another function, and then repeating that m-times again, ... Each step multiplies the number of applications of f by m, so we get m^n.

Back to your case

twice twice twice double 3 =
g 2 (g 2) (g 2) double 3 =
g (2^2) (g 2) double 3 =
g (2^(2^2)) double 3 =
double (double (double .... 3)) -- 2^(2^2) = 2^4 = 16 times

So, we are getting 3 doubled 16 times, obtaining 3 * 2^16 = 196608.