Search code examples
haskellpointfree

Function composition and its representations

I wonder:

1) are the following functions exactly the same:

inc = (+1)
double = (*2)

func1 = double . inc
func2 x = double $ inc x
func3 x = double (inc x)
func4 = \x -> double (inc x)

2) why doesn't func5 compile?

func5 = double $ inc        -- doesn't work
Solution

  • Are these functions exactly the same?

    Actually, no! There are some very subtle differences. First of all, read about the dreaded monomorphism restriction. In short, class-polymorphic functions are given different types by default if they're "obviously" functions or not. In your code, this difference won't manifest, because inc and double aren't "obviously" functions and so are given monomorphic types. But if we make a slight change:

    inc, double :: Num a => a -> a
inc = (+1)
double = (*2)

func1 = double . inc
func2 x = double $ inc x
func3 x = double (inc x)
func4 = \x -> double (inc x)

    then in ghci we can observe that func1 and func4 -- which are not "obviously" functions -- are given a monomorphic type:

    *Main> :t func1
func1 :: Integer -> Integer
*Main> :t func4
func4 :: Integer -> Integer

    whereas func2 and func3 are given a polymorphic type:

    *Main> :t func2
func2 :: Num a => a -> a
*Main> :t func3
func3 :: Num a => a -> a

    The second slight difference is that these implementations may have (very slightly) different evaluation behavior. Since (.) and ($) are functions, you may find that invoking func1 and func2 requires a little bit of evaluation before they can run. For example, perhaps the first invocation of func1 3 proceeds like this:

    func1 3
= {- definition of func1 -}
(double . inc) 3
= {- definition of (.) -}
(\f g x -> f (g x)) double inc 3
= {- beta reduction -}
(\g x -> double (g x)) inc 3
= {- beta reduction -}
(\x -> double (inc x)) 3

    whereas the first invocation of, e.g, func4 3 gets to this point in a much more straightforward manner:

    func3 3
= {- definition of func3 -}
(\x -> double (inc x)) 3

    However, I wouldn't worry about this too much. I expect that in GHC with optimizations turned on, saturated calls to both (.) and ($) get inlined, eliminating this possible difference; and even if not, it's going to be a very small cost indeed, since this will likely happen only once per definition (not once per invocation).

    Why doesn't func5 compile?

    Because you don't want it to compile! Imagine it did. Let's see how we would evaluate func5 3. We'll see that we "get stuck".

    func5 3
= {- definition of func5 -}
(double $ inc) 3
= {- definition of ($) -}
(\f x -> f x) double inc 3
= {- beta reduction -}
(\x -> double x) inc 3
= {- beta reduction -}
double inc 3
= {- definition of double -}
(\x -> x*2) inc 3
= {- beta reduction -}
(inc * 2) 3
= {- definition of inc -}
((\x -> x+1) * 2) 3

    Now we are trying to multiply a function by two. At the moment, we haven't said what multiplication of functions should be (or even, in this case, what "two" should be!), and so we "get stuck" -- there's nothing further that we can evaluate. That's not good! We don't want to "get stuck" in such a complicated term -- we want to only get stuck on simple terms like actual numbers, functions, that kind of thing.

    We could have prevented this whole mess by observing right at the beginning that double only knows how to operate on things that can be multiplied, and inc isn't a thing that can be multiplied. So that's what the type system does: it makes such observations, and refuses to compile when it's clear that something wacky is going to happen down the line.