[Haskell-beginners] Haskell type system

[Paul Sargent]

I'll try my hand at these, anybody feel free to point out all my  
deliberate mistakes.

On 27 Sep 2009, at 11:22, informationen wrote:

> Two functions f and g with the following signatures are given:
> f :: a -> a
> g :: b -> c -> b
>
> A) Give the type of the following expressions:
>
> 1) g [False] True  :: 2) g [] True

These two are simply that the result of the function g is the same as  
it's first argument. The first takes a list of Boolean, the second a  
list of an unknown type. Therefore the results are the same types  
[Boolean] and [a] respectively.

> :: 3) g (f True)      ::

The result of f is the same type as it's argument, in this case Boolean.
g's first and only argument which is the type of the result of f --  
Boolean.
As we haven't specified a second argument, the returned type is a  
function which takes an unknown type and returns a boolean.

(c -> Bool)


> 4) g f             ::

Similar to the last case except now the only argument supplied is a  
function of type (a -> a).
(c -> (a -> a))

> Answers:
>
> B) Which of the following statements is correct?
>
First two are easy, and the same.
> 1)  g f 1           c -> Int
> 2)  g (f 1)         c -> Int

Remember that the type of (.) is (b -> c) -> (a -> b) -> a -> c. That  
is, it takes two functions where they both take an argument, and the  
type of the first functions argument is the same as the seconds result.

> 3)  g . (f 1)

Here (f 1) doesn't take an argument, it's already supplied. That makes  
it's type Int, not (a -> b). That's not right.

> 4)  g . f 1

The same, the brackets where redundant in the previous expression.

> 5)  (g . f) 1

Here we're composing before giving the arguments.
So, remembering that f :: a -> a and g :: b -> c -> b, we can start  
filling in the types:

(b -> c) -> (a -> b) -> a -> c               -- To make g fit, c must  
become (c -> b)
(b -> (c -> b)) -> (a -> b) -> a -> (c -> b) -- f returns same type as  
input, so b == a
(a -> (c -> a)) -> (a -> a) -> a -> (c -> a) -- Now we've supplied f  
and g we can just worry about the result part
a -> (c -> a)                                -- This is the type of  
(g . f), but we've got an Int argument "1"
Int -> (c -> Int)                            -- So the type of the  
expression is (c->Int)

Nothing wrong with that. Type safe.

It might be easier to just start plugging types in than following that  
explanation, but it does work.

> C) A function h is given as: h p x = p (f x). Which of the following
> statements is correct.

p is obviously a function of one (or more) arguments. h takes two  
arguments, and returns the result of p, so

h :: (a -> b) -> c -> b

because we know f :: a -> a, we can say a and c are the same type

h :: (a -> b) -> a -> b

That's number 3.

(g . f) x is the same as g (f x). Therefore we can re-write h

h' p x = (p . f) x -- or
h' p = (p . f)     -- the argument is implicit

That's 4

> 3) h :: (a -> b) -> a -> b
> 4) h is equivalent to h' with h' p = p . f