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 -> a and a variable with type a - the result has type a.

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 a: f a
with two arguments with types a and b: f a b
with three arguments with types a, b and c: 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 written as ((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 and inc!

Question: To what reduces the expression twice inc 0?

Answer: It is equivalent to ((twice inc) 0). So, we see that at the first step 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 follows:

twice inc 0 =
inc (inc 0) =
inc 1 =
2

twice inc gets first evaluated. It results in a function with type a -> a which is applied to the second argument, in this case 0.

A bit more complicated is twice twice inc 0 which is equivalent to ((twice twice) inc) 0. In this case the second defintion of 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

Question: What type has the expression twice twice?

Answer: twice has type (a -> a) -> a -> a equivalent to (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 twice as (b -> b) -> (b -> b) (with b only to distinguish it from the first twice).
The type (b -> b) -> (b -> b) matches to a -> a with (b -> b) equivalent to a. The first twice returns a -> a which, using the type of the second twice, is (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))

Question: To what reduces (what is the value of) twice twice twice inc 0?

Answer: 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 answer.

Playing with functions in Haskell

–+ На български

–+ Numbers

–+ Math

–+ Dev