Help with types

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Help with types

Daniel Carrera-4
Hi,

I want to make a simple "average" function:

average xs = (sum xs)/(length xs)

When I try that on ghci I get the following error:

     No instance for (Fractional Int)
       arising from a use of `/' at <interactive>:1:17-36
     Possible fix: add an instance declaration for (Fractional Int)
     In the expression: (sum xs) / (length xs)
     In the definition of `average': average xs = (sum xs) / (length xs)

Ok, so 'sum' is of type (Num a => [a] -> a), length is of type ([a] ->
Int) and (/) is of type (Fractional a => a -> a -> a). Can someone
explain how I can "add an instance declaration" to my function so as to
make all these types compatible?

Thanks,
Daniel.
Reply | Threaded
Open this post in threaded view
|

Help with types

Daniel Fischer-4
Am Donnerstag 23 April 2009 14:57:58 schrieb Daniel Carrera:

> Hi,
>
> I want to make a simple "average" function:
>
> average xs = (sum xs)/(length xs)
>
> When I try that on ghci I get the following error:
>
>      No instance for (Fractional Int)
>        arising from a use of `/' at <interactive>:1:17-36
>      Possible fix: add an instance declaration for (Fractional Int)
>      In the expression: (sum xs) / (length xs)
>      In the definition of `average': average xs = (sum xs) / (length xs)
>
> Ok, so 'sum' is of type (Num a => [a] -> a), length is of type ([a] ->
> Int) and (/) is of type (Fractional a => a -> a -> a). Can someone
> explain how I can "add an instance declaration" to my function so as to
> make all these types compatible?

Don't. (you wouldn't add the instance declaration to the function, anyway, but to your
module)
Try explicitly converting the length to the appropriate type:

average xs = sum xs / fromIntegral (length xs)

will yield a working (albeit inefficient)
average :: Fractional a => [a] -> a

>
> Thanks,
> Daniel.

Reply | Threaded
Open this post in threaded view
|

Help with types

Daniel Carrera-4
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. This surprises
me. I would have thought that Fractional is a kind of Num and Int is a
kind of Fractional, 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. But I don't really get why.


> will yield a working (albeit inefficient)
> average :: Fractional a => [a] -> a

Why is it inefficient? How would you make it efficient?

Thanks for the help.

Cheers,
Daniel.
Reply | Threaded
Open this post in threaded view
|

Help with types

aditya siram-2
There is a chapter in Real World Haskell [1] devoted to this exact question
on this exact piece of code.

hth,
-deech

[1] http://book.realworldhaskell.org/read/profiling-and-optimization.html

On Thu, Apr 23, 2009 at 8:52 AM, Daniel Carrera <
[hidden email]> wrote:

> 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. This surprises
> me. I would have thought that Fractional is a kind of Num and Int is a kind
> of Fractional, 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. But I don't really get why.
>
>
>  will yield a working (albeit inefficient)
>> average :: Fractional a => [a] -> a
>>
>
> Why is it inefficient? How would you make it efficient?
>
> Thanks for the help.
>
> Cheers,
>
> Daniel.
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090423/4ba489ef/attachment.htm
Reply | Threaded
Open this post in threaded view
|

Help with types

Jason Dusek
In reply to this post by Daniel Carrera-4
2009/04/23 Daniel Carrera <[hidden email]>:
> It looks like (/) is happy with Num but doesn't like Int. This
> surprises me.  I would have thought that Fractional is a kind
> of Num and Int is a kind of Fractional, 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.

  In GHCi, let's have a look:

    Prelude> :info Int
    data Int = GHC.Types.I# GHC.Prim.Int#   -- Defined in GHC.Types
    instance Bounded Int -- Defined in GHC.Enum
    instance Enum Int -- Defined in GHC.Enum
    instance Eq Int -- Defined in GHC.Base
    instance Integral Int -- Defined in GHC.Real
    instance Num Int -- Defined in GHC.Num
    instance Ord Int -- Defined in GHC.Base
    instance Read Int -- Defined in GHC.Read
    instance Real Int -- Defined in GHC.Real
    instance Show Int -- Defined in GHC.Show

  So `Int` is not actually a kind of `Fractional` (it's
  `Integral`, in fact).

    Prelude> :t (/)
    (/) :: forall a. (Fractional a) => a -> a -> a

  So `(/)` needs some `t` that is in `Fractional`.

> 'fromIntegral' converts Int to Num. So obviously, Num is good and Int is
> bad. But I don't really get why.

  Actually, `fromIntegral` takes any type `t` that is in
  `Integral` and makes it into some other type in `Num` as
  appropriate. You can use `fromIntegral` to go from `Int` to
  `Integer` or `Word32`, as well.

  To work with `(/)` we need a type that is in `Num` and in
  `Fractional`. The compiler defaults these *class constraints*
  to select, say `Double`. Then `fromIntegral` -- which can take
  any `Num` to any other `Num` -- does the "cast" from `Int` to
  `Double` for us.

--
Jason Dusek
Reply | Threaded
Open this post in threaded view
|

Help with types

Thomas Davie
In reply to this post by Daniel Carrera-4

On 23 Apr 2009, at 15:52, Daniel Carrera wrote:

> 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. This  
> surprises me. I would have thought that Fractional is a kind of Num  
> and Int is a kind of Fractional

Int isn't a Fractional because it can't represent fractional numbers.

Bob
Reply | Threaded
Open this post in threaded view
|

Help with types

Daniel Carrera-4
In reply to this post by aditya siram-2
aditya siram wrote:
> There is a chapter in Real World Haskell [1] devoted to this exact
> question on this exact piece of code.
>
> hth,
> -deech
>
> [1] http://book.realworldhaskell.org/read/profiling-and-optimization.html

Wow. Indeed, that is the exact same piece of code. Thanks.

Daniel.
Reply | Threaded
Open this post in threaded view
|

Help with types

Daniel Carrera-4
In reply to this post by Thomas Davie
Thomas Davie wrote:
>> It looks like (/) is happy with Num but doesn't like Int. This
>> surprises me. I would have thought that Fractional is a kind of Num
>> and Int is a kind of Fractional
>
> Int isn't a Fractional because it can't represent fractional numbers.

Sure, but any integer is trivially also a fraction, so I would think
that it would be an acceptable input for (/). On the other hand, if it
is at all possible for a Num to contain something that cannot be
converted to a fraction, then a Num should not be a valid input for (/).
Reply | Threaded
Open this post in threaded view
|

Help with types

Jason Dusek
2009/04/23 Daniel Carrera <[hidden email]>:
> ...if it is at all possible for a Num to contain something
> that cannot be converted to a fraction, then a Num should not
> be a valid input for (/).

  And it isn't.

    Prelude> :t (/)
    (/) :: forall a. (Fractional a) => a -> a -> a

--
Jason Dusek
Reply | Threaded
Open this post in threaded view
|

Help with types

Thomas Davie
In reply to this post by Daniel Carrera-4

On 23 Apr 2009, at 16:25, Daniel Carrera wrote:

> Thomas Davie wrote:
>>> It looks like (/) is happy with Num but doesn't like Int. This  
>>> surprises me. I would have thought that Fractional is a kind of  
>>> Num and Int is a kind of Fractional
>> Int isn't a Fractional because it can't represent fractional numbers.
>
> Sure, but any integer is trivially also a fraction, so I would think  
> that it would be an acceptable input for (/). On the other hand, if  
> it is at all possible for a Num to contain something that cannot be  
> converted to a fraction, then a Num should not be a valid input for  
> (/).

The problem here is that (/) also *outputs* that type ? if you can't  
represent a fraction, how do you give the result of 1/4?

Bob
Reply | Threaded
Open this post in threaded view
|

Help with types

Daniel Fischer-4
In reply to this post by Daniel Carrera-4
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.


Reply | Threaded
Open this post in threaded view
|

Help with types

Daniel Carrera-4
Daniel Fischer wrote:
> 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.

Aahh....  I see. The "sum" part is making more sense now.

So let's see: "sum" is a (Num a => [a] -> a). Every function can be used
at all types that are less general than its most general type.
Fractional is a kind of Num. Therefore, "sum" can be used as (Fractional
a => [a] -> a) to make it compatible with (/).

Thanks for the detailed explanation. It's a lot clearer now.

>> 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.

This helps. I think I see the problem:

Suppose that Integral was a kind of Fractional, the way I proposed. What
happens when someone writes (x / y) `mod` z ?  Trying to apply the same
reasoning you used above:

(/) :: Fractional a => a -> a -> a
mod :: Integral a => a -> a -> a


Using the logic that you explained above, we would have to force (/) to
give an Integral result, which in general is wrong. And that is a
reasonable argument why Integral should not be an instance of Fractional.

Am I right more or less?



>> But I don't really get why.
>
> fromIntegral says, whatever Num type you want, I can give it to you.

... and 'length' says, "whatever Int type you want, I can give it to
you", but (/) says "I don't want an Int, I want a Fractional" and that's
why 'length' alone doesn't get along with (/).

I'm beginning to see the reasoning behind Haskell's behaviour, but I
think I'll need time to get used to it.

Thanks for the help.

Daniel.