Function Composition Types

Question

I struggle understanding function composition type results e.g

ghci> :t (id . const)
(id . const) :: a -> b -> a
ghci> :t ((:) . (+))
((:) . (+))  :: a -> [a -> a] -> [a -> a]

How do you guys generally derive function composition types?

Answer 1

That's simple, initially write down the types of both the functions:

> :t const
const :: a -> b -> a
> :t id
id :: a -> a

(id . const) gets translated to \x -> id (const x)

(const x)          :: b -> a      -- (Note that the type of `x` is `a` here)
id (const x)       :: b -> a      -- The output of id type will be the same as the input it takes
\x -> id (const x) :: a -> b -> a -- We aleady know the type of x

You can follow the same step for the next function.

Answer 2

Lets see that

> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

So in general:

1. Given two functions. Consider them as curried functions of one parameter, i.e. function of type a -> b -> c -> ... -> z we'll consider as a function a -> ( b -> c -> ... -> z ) of one parameter that returns function with one parameter less.
2. Result type of second function should be same as parameter type of first. So consider parameter of first function as result parameter of second. Denote it as b.
3. Result type of whole composition should be equal a function from parameter type of second function (denote it as a) to result type of first function (denote it as c)

> :t (id . const)

> :t id
id :: a -> a

rename it to x -> x

> :t const
const :: a -> b -> a

Note that a here is not necessary the same that in previous type equation, some rename it to y -> z -> y

a = y
b = z -> y = x
c = x = z -> y

So result is a -> c = y -> ( z -> y) same as a -> b -> c Overall semantics is equal to const

> :t ((:) . (+))

> :t (:)
(:) :: a -> [a] -> [a]

rename it to x -> [x] -> [x]

> :t (+)
(+) :: Num a => a -> a -> a

rename it to Num y => y -> y -> y

a = y
b = y -> y = x
c = [x] -> [x] = [y -> y] -> [y -> y]

Also we have restriction with type class Num y So overall type well be Num y => a -> c = y -> [y -> y] -> [y -> y] same as Num a => a -> [a -> a] -> [a -> a]
Overall semantics is "make single parameter function that adds first parameter to numeric value and prepend that function to a given list of single parameter functions"

Answer 3

Exercises: Find the types of the function compositions below, by hand, not using GHCi. Do these exercises to build intuition for reasoning about function types. Remember that type a -> a, where a is a type variable, matches not only Int -> Int or [Bool] -> [Bool], but (a -> a) -> (a -> a) too. If you can't do the exercises, read below.

1. (*3) . (+2) (easy)
2. (*) . (+2)
3. (:) . (+2)
4. (:) . (*)

What is a function? It's something, that takes an input and returns an output. Not just random output, but output that depends on that input. For the same input the same function always returns the same output. A function transforms some stuff to another stuff. Input and output can be of different types. So imagine a function as a magical one-way tube: you put one thing in the hole labeled in and get something else from another hole named out, possibly of entirely different form. Like, you put a tomato in a tube and get a machine gun from the opposite end. But remember, functions are one-way, you can't put anything in the function's out hole.

a :: Int -> Int -- take a thing of type Int and return a thing of type Int
a n = n + 2

b :: Int -> Int 
b n = n -- a function can even return the same value

c :: Int -> Bool -- an output can be of different type than input
c n = n `mod` 3 == 0

Haskell supports higher-order functions and is curried by default. This means that there are no multiple-argument functions in Haskell, every function accepts only 1 argument, but sometimes they can return functions. Haskell tubes always has one and only one hole in, but sometimes tubes pop tubes from the hole out! There are even tubes, in which you can put other tubes. Function types are right-associative, which means that a -> b -> c and a -> (b -> c) are the same thing.

:t (+) -- Num a => a -> a -> a
:t (:) -- a -> [a] -> [a]

So what's a function composition? It's when you compose functions into a new function, or when you fuse 2 tubes together, welding 1^st's out to 2^nd's in, so that whatever you put into the first tube's in hole, falls through and pops out of second tube's out hole.

A composed function then can be imagined as a long tube made out of two shorter tubes welded together. What would be the type of a composed function? Our new tube still has 2 holes in it, one labeled in, another labeled out. But remember, in of our new tube corresponded to in of a first part, and out of our new tube corresponded to out of the second part. So the type will be from whatever was input to 1^st function to whatever was output of 2^nd function.

:t (:[2,3]) . (+1) -- Num a => a -> [a]
-- why?
:t (+1)     -- Num a => a -> a
:t (:[2,3]) -- Num a =>      a -> [a]

We joint 2 functions together, first's output to second's input, and get a new function that still has one input and one output. And that's exactly what function operator's type says:

:t (.) -- (b -> c) -> (a -> b) -> (a -> c)

Due to a historical accident, function composition goes from right to left, so (*3) . (+2) is a function that first adds 2 to a number, and then multiples by 3 the result. So how to deduce a type of a function composition? You joint the the input of 2^nd function to an output of 1^st function and throw away the types in between.

a -> b
     b -> c   becomes
a    ->   c

See also: [1], [2], [3], [4] for more ideas on how to use function composition and how to reason about function types.