Playing with functions in Haskell
Consider the following definitions:
> inc :: Int -> Int > inc n = n+1 > > twice :: (a -> a) -> a -> a > twice f a = f (f a)
The type of
twice is polymorphic. It says: The function can
be called with
- one argument with type
a -> a- in this case the returned expression has type
a -> a
- two arguments: a function with type
a -> aand a variable with type
a- the result has type
All functions that receive two or more parameters can be called in more than one ways.
Example: we have a function with type
a -> b -> c -> d.
It can be called in three different ways:
- with one argument with type
- with two arguments with types
f a b
- with three arguments with types
f a b c
This is possible because all functions in Haskell are curried.
This means that every function is applied only to the first argument,
the resulting expression is applied to the second and so on.
So the type of our function can be written as
a -> (b -> (c -> d)).
The braces aren't needed similar to the function application, which can be
((f a) b) c, but help for better understanding.
Let's go back to our two functions! Looking at
twice we see that it defines a double function application. So
it can be defined using the function composition operator
(function composition function)
which has type
(a -> b) -> (c -> a) -> (c -> b):
> twice f = f . f
Let's see some examples with
twice inc 0?
It is equivalent to
((twice inc) 0). So, we see that at the
twice must be applied to one argument -
inc. We want to determine what is the result from
this application in order to apply this result to the second argument.
From the definition of
twice inc 0 = inc (inc 0) = inc 1 = 2
twice inc gets first evaluated. It results in a function
a -> a which is applied to the second argument,
in this case
A bit more complicated is
twice twice inc 0 which is
((twice twice) inc) 0. In this case the second
twice is more handy. In the following reductions
is used the definition of the function composition operator:
> (.) :: (b -> c) -> (a -> b) -> (a -> c) > (f . g) x = f (g x)
twice inc 0 = (inc . inc) 0 = inc (inc 0) = inc 1 = 2
And the current one:
twice twice inc 0 = ((twice twice) inc) 0 = ((twice . twice) inc) 0 = (twice (twice inc)) 0 = (twice (inc . inc)) 0 = (inc . inc . inc . inc) 0 = (inc (inc (inc (inc 0)))) = (inc (inc (inc 1))) = (inc (inc 2)) = (inc 3) = 4
twice has type
(a -> a) -> a -> a
(a -> a) -> (a -> a).
It takes a function with type
a -> a and returns another function with the same type.
Let's view the type of the second
(b -> b) -> (b -> b)
b only to distinguish it from the first
(b -> b) -> (b -> b)
a -> a
(b -> b) equivalent to
a -> a which,
using the type of the second
(b -> b) -> (b -> b).
Therefore the type of
twice twice is
(b -> b) -> (b -> b) or
(a -> a) -> (a -> a)
(the letter that we are using to mark a polymorphic type doesn't matter).
More visually expressed:
argument result ( a -> a ) -> ( a -> a ) ((b -> b) -> (b -> b)) -> (( b-> b) -> (b -> b))
twice twice twice inc 0?
Try first alone to determine the result without executing the code.
It is good to write down all reductions as we've done it for
twice twice inc 0.
As a last alternative you may look at the