# Haskell notes

## 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]
[]