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. |
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. |
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. |
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 > An HTML attachment was scrubbed... URL: http://www.haskell.org/pipermail/beginners/attachments/20090423/4ba489ef/attachment.htm |
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 |
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 |
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. |
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 (/). |
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 |
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 |
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. |
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. |
Free forum by Nabble | Edit this page |