Haskell notes

Some notes on Haskell functions.

Function composition

1
2
(.) :: (b -> c) -> (a -> b) -> a -> c -- type declaration
f . g = \x -> f (g x)                 -- definition

From the snippet above we can see that three type parameters are involved in the type declaration of the operator . That is a, b and c. We also see that . takes three parameters: a function b -> c let's call it f, function a -> b let's call it g and last parameter a. The best way too understand how . works is to understand relationship between type parameters and parameters of .

• . return type c is the same as f. There are no other ways to get type of c, thus the last thing what definition of operator . has to do is to apply function f.
• g return type b is te same as f first parameter. Thus we can apply f to the result of g.
• . last parameter's a type is the same as function's g. Thus, we can apply g to the value of type a.

Based on relationships above we can say that operator . takes three parameters and first parameter will be applied to the result of applying second parameter to the third one. Therefore we can write definition of . as (.) f g a = f (g a). If we partially apply, we will get a function which takes one parameter (.) f g = \a -> f (g a) or in infix notation f . g = \a -> f (g a) which is original definition of .

Definition of f . g is \a -> f (g a). Therefor every time haskell's evaluator sees f . g it will change it to \a -> f (g a). Knowing that, we can use function composition instead of lambda functions with one parameter. For example,

1
2
3
4
ghci> :t \x -> succ (succ x)
\x -> succ (succ x) :: Enum a => a -> a
ghci> :t succ . succ
succ . succ :: Enum a => a -> a

As you can see the types of \x -> succ (succ x) and succ . succ are identical. Both take and return value of type a. If we fully apply both functions, then we should get same result,

1
2
3
4
ghci> (\x -> succ (succ x)) 5
7
ghci> (succ . succ) 5
7

. is right-associative, so we can compose many functions at a time. And the expression such as f (g (z (w x ))) is equivalent to (f . g . z. w ) x. For example,

1
2
ghci> (map (*9) . replicate 4 . succ) 2
[27,27,27, 27]

So, we apply composed function map (*3) . replicate 4 . succ to the value of 2. First function succ increases 2 by one and it becomes 3, then function replicate 4 is applied to the 3 which replicates 3 four times. Lastly, we multiply each member in the list [3,3,3,3] by 9, resulting [27,27,27,27].

Notice, that in the last example functions map and replicate were partially applied before composing. For example, originally function replicate takes two parameters: first one tells how many times to replicate and the second - what to replicate. By partially applying replicate to the value of 4 we create a function which takes any value (in our case 3) and replicates it 4 times.

It doesn't mean that all the functions with multiple parameters has to be partially applied before composing them.

1
2
ghci> :t filter . (&&)
filter . (&&) :: Bool -> [Bool] -> [Bool]

Both functions filter which has type of (a -> Bool) -> [a] -> [a] and && with type of Bool -> Bool -> Bool take two parameters. By composing them, we get a function with two parameters Bool and [Bool]. Let's see it in the action,

1
2
3
4
ghci> (filter . (&&)) True [True, False, True, True, False]
[True,True,True]
ghci> (filter . (&&)) False [True, False, True, True, False]
[]

It seems that the function && is partially applied to True in the first case and False in the second case, which gives us functions (&&) True and (&&) False respectively. Both of them has type of Bool -> Bool which is the same as first type of filter parameter. We can rewrite previous example without composition:

1
2
3
4
ghci> filter (True &&) [True, False, True, True, False]
[True,True,True]
ghci> (\x -> filter (x &&)) False [True, False, True, True, False]
[]