[Haskell-beginners] Help with types
Daniel Fischer
daniel.is.fischer at web.de
Thu Apr 23 10:56:37 EDT 2009
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.
More information about the Beginners
mailing list