Haskell Higher Order Functions and Associativity

user_10643419 0
Viewed 113

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.

higher-order-functions ghc functional-programming haskell
2 Answers

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.

comingstorm_2102110

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.

user_32349590
Related