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.