Haskell and General Types

Question

I'm kind of new to Haskell, and I would like to understand how general types works.

What should be a "systematic" way of thinking to get the type of an expression?

To make an example, if we have:

(\x y z -> x (y z))

The way I would think about this, would just be to use intuition, but it doesn't work always.

In this case I would say:

   (y z) :: (t -> t1) --function y takes t and return t1
 x (y z) :: (t1 -> t2) --function x takes argument of type (return type of y)

(\x y z -> x (y z)) :: (t1 -> t2) -> (t -> t1) -> t -> t2 --return type is t2 (of x) with argument of type t for function y

I'm pretty sure this should be right, but sometimes it's harder and this way go thinking doesn't seems to work.

For example if we have:

1.  (\x -> x (<))  or
2.  (.) . (.)

In this cases I would have no idea how to find the types, for the first I would guess that (<) is a function on two elements that returns a Bool but I have troubles writing the hole expression.

So the question is, what is the best way work with this kind of exercises?

---

ADDED: I know how to check the types with ghci, the question was how to actually find them without it (to understand how Haskell works).

Answer 1

You can easily check the type of an expression with :t in ghci:

Prelude> :t (\x y z -> x (y z))
(\x y z -> x (y z)) :: (r1 -> r) -> (r2 -> r1) -> r2 -> r
Prelude> :t (\x -> x (<))
(\x -> x (<)) :: Ord a => ((a -> a -> Bool) -> r) -> r
Prelude> :t (.) . (.)
(.) . (.) :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c

But I assume you want to derive the types yourself.

1. For the first we can start with looking to the variables. Those are x, y and z. We first assign "generic types" to them, so:

   x :: a
   y :: b
   z :: c
   

   Now we look to the right hand of the expression and see (y z). This means that we "call" y with z as argument. As a result we "specialize" the type of y to y :: c -> d. The type of (y z) then is (y z) :: d. Now we see that x (y z). So again we "specialize" the type of x into x :: d -> e. As a result we obtain:

   x :: d -> e
   y :: c -> d
   z :: c
   

   Finally the lambda-expression maps \x y z -> x (y z). So that means we look to the resulting type is something in "pseudo code": type(x) -> type(y) -> type(z) -> type('x (y z)'). Or:

   \x y z -> x (y z) :: (d -> e) -> (c -> d) -> c -> e
   

2. For the second expression we first have to derive the type of (<):

   Prelude> :t (<)
   (<) :: Ord a => a -> a -> Bool
   

   This is because (<) is somewhere defined in the Prelude with that type.

   Now we know that, we can look at the type signature. We will first assume a type for x :: b. Now we look to the right side, and see that we call x (<). So that means we know x has the type Ord a => (a -> a -> Bool) -> c and we know that x (<) :: c. Then again we have a lambda-expression, and as we have seen above, we can resolve it like:

   (\x -> x (<)) :: Ord a => ((a -> a -> Bool) -> c) -> c
   

3. Finally for the third expression, let is first rewrite it to:

   (.) (.) (.)
   

   Here the first (.) function, was originally the . (without brackets), but we will first remove the operator syntactical sugar.

   Next we will give the operators a name (only to make it more convenient for us to name them). This is not allowed in Haskell, but we will ignore that for now. The reason we do this is to later refer to the type of a specific (.) function:

   (.1) (.2) (.3)

   Next we lookup the type for (.):

   Prelude> :t (.)
   (.) :: (b -> c) -> (a -> b) -> a -> c
   

   So we first assign some types:

   (.1) :: (b -> c) -> (a -> b) -> a -> c
   (.2) :: (e -> f) -> (d -> e) -> d -> f
   (.3) :: (h -> i) -> (g -> h) -> g -> i
   

   Now we need to analyze these types further. We call (.1) with (.2) as argument so we know that (b -> c) (the first argument of (.1) is equivalent to (e -> f) -> (d -> e) -> d -> f. So that means that:

   (b -> c) ~ (e -> f) -> (d -> e) -> d -> f
   

   Since the type arrows are right associative, (e -> f) -> (d -> e) -> d -> f actually means (e -> f) -> ((d -> e) -> (d -> f)). So now we can make an analysis:

     b        -> c
   ~ (e -> f) -> ((d -> e) -> (d -> f))
   

   So that means b ~ (e -> f) and c ~ ((d -> e) -> (d -> f)). So we "specialize" our first (.1) :: (b -> c) -> (a -> b) -> a -> c into

   (.1) :: ((e -> f) -> ((d -> e) -> (d -> f))) -> (a -> (e -> f)) -> a -> ((d -> e) -> (d -> f))
   

   Now the type of (.1) (.2) is

   (.1) (.2) :: (a -> (e -> f)) -> a -> ((d -> e) -> (d -> f))
   

   But now we call that function with (.3) so we have to derive the type for ((.1) (.2)) (.3). Therefore again we have to do type resolution with:

     a        -> (e        -> f)
   ~ (h -> i) -> ((g -> h) -> (g -> i))
   

   So that means a ~ (h -> i), e ~ (g -> h) and f ~ (g -> i). So now we have resolved the type to:

   ((.1) (.2)) (.3) :: a -> c
   =                   (h -> i) -> ((d -> (g -> h)) -> (d -> (g -> i)))
   =                   (h -> i) -> (d -> g -> h) -> d -> g -> i
   

   The last line is only a syntactical simplification. As you can see, this maps on the type we derived from ghci.

As you can see for all three queries we obtain the same type (of course the name of the type variables is different).

Answer 2

Using the GHC compiler, you can ask about type by using type holes, _

for instance:

thing :: _
thing = (\x -> (<))

yields:

Found hole ‘_’ with type: t -> a0 -> a0 -> Bool
Where: ‘t’ is a rigid type variable bound by
           the inferred type of thing :: t -> a0 -> a0 -> Bool
           at src/Expat/Data/E.hs:555:1
       ‘a0’ is an ambiguous type variable
To use the inferred type, enable PartialTypeSignatures
In the type signature for ‘thing’: _

I sometimes use this with where clauses to isolate expressions in larger functions, e.g.

myFun :: a -> b
myFun a = otherFun thing
  where 
    thing :: _
    thing = (\x -> (<))

You can also use holes in place of terms. For instance, if I'm not sure exactly what otherFun should be, I could just substitute in _.