[Haskell-beginners] Help with types

[Daniel Fischer]

Am Donnerstag 23 April 2009 15:52:00 schrieb Daniel Carrera:
> Daniel Fischer wrote:
> > Try explicitly converting the length to the appropriate type:
> >
> > average xs = sum xs / fromIntegral (length xs)
>
> Thanks. Could you help me understand what's happening?
>
> 1. length returns Int.
> 2. sum returns Num.
> 3. (/) wants Fractional.
>
> It looks like (/) is happy with Num but doesn't like Int.

Not quite. (/) needs a type which is an instance of Fractional. All instances of 
Fractional are also instances of Num, so Fractional is more specific than Num.
If you divide the result of sum using (/), sum is used at the less general type 
(Fractional a => [a] -> a).
Every function can be used at all types which are less general than its most general type.
In this case it goes like this:

The type checker sees

average xs = sum xs / fromIntegral (length xs)

so average is a function, having type arg -> result where

xs :: arg
sum xs / fromIntegral (length xs) :: result

Now the right hand side, the expression sum xs / fromIntegral (length xs), is typed.

(/) has the type Fractional a => a -> a -> a, so from that we can deduce that

sum xs :: Fractional a => a
fromIntegral (length xs) :: Fractional a => a
result = Fractional a => a

, all for the same a.

sum has the type (Num n => [n] -> n), so for the expression sum xs to be well formed, xs 
must have the type (Num  n => [n]), and then 

sum xs :: Num n => n

Now that type has to be unified with the type deduced for this subexpression above. Since 
the first says whichever type, as long as it's a member of class Fractional and the second 
says whichever type, as long as it's a member of class Num, the unification yields 
"whichever type, as long as it's a member of both, class Fractional and class Num",  
(Fractional a, Num a) => a.
Since Fractional is a subclass of Num, the second condition is implied by the first and 
the type simplifies to Fractional a => a. Since the type of xs' elements is th same as the 
type of sum xs, the Fractional constraint has to be added to the type of xs too, giving 
xs :: Fractional a => [a]
arg = Fractional a => [a]

fromIntegral has type (Integral a, Num b) => a -> b. Since length xs :: Int and Int is a 
member of Integral,

fromIntegral (length xs) :: Num n => n

This has to be unified with the type deduced above, giving

fromIntegral (length xs) :: Fractional a => a

, too. Note that (sum xs) and (fromIntegral (length xs)) have the type Fractional a => a 
*as subexpressions of sum xs / fromIntegral (length xs)*, in isolation, both would have 
the type Num n => n.

Assembling all that, we find

average :: Fractional a => [a] -> a

> This surprises
> me. I would have thought that Fractional is a kind of Num and Int is a
> kind of Fractional,

No, Int is an instance of Integral, which is sort of the opposite of Fractional.
Fractional means that you can freely divide (excluding division by 0 of course), things 
like 3.24 make sense, Integral means that things like mod or gcd make sense.
Though it is possible to make a type an instance of both, Fractional and Integral, that 
doesn't really make sense.

> so a function that expects Fractional would be happy
> with an Int but maybe not with a Num. But clearly that's not the way it
> works.
>
> 'fromIntegral' converts Int to Num. So obviously, Num is good and Int is
> bad.

The thing is that the types are implicitly universally quantified, so the type of 
fromIntegral is really

forall a b. (Integral a, Num b) => a -> b

and the type of 
fromIntegral something
is 
forall b. Num b => b

> But I don't really get why.

fromIntegral says, whatever Num type you want, I can give it to you. In particular, if the 
caller wants a Double, fromIntegral provides a Double. If the caller wants any type, as 
long as it's a member of Fractional, fromIntegral provides that.

Int is a fixed type, the caller cannot choose which type shall be returned, it's always 
just Int, so the caller can only use operations which are defined on Int. (/) is not 
defined on Int, because the result of dividing two Ints is rarely an Int. For divisions of 
Integral types, there are div and quot (with mod and rem for the remainders).

>
> > will yield a working (albeit inefficient)
> > average :: Fractional a => [a] -> a
>
> Why is it inefficient? How would you make it efficient?

It's inefficient because the list has to be traversed twice, once for the sum and once for 
the length. Also, the whole list is kept in memory between the two traversals, which is a 
very bad thing for long lists.
To make it efficient, calculate the sum and the length together, as in

average xs = loop 0 0 xs
    where
        loop sm ln [] = sm / fromIntegral ln
        loop sm ln (y:ys) = loop (sm+y) (ln+1) ys

although that probably needs strictness annotations on sm and ln to be efficient 
(otherwise, the running sum and length may not be evaluated but build up large thunks 
which are only forced at the end and may cause a stack overflow then).

>
> Thanks for the help.
>
> Cheers,
> Daniel.