Haskell: Why does RealFrac not imply Fractional?

Question

NOTE: Full source code here: https://gist.github.com/anonymous/7085509

I have the following function:

tournament n p pop = do
    winner <- (\w -> min (n - 1) (floor (log w / log (1-p)))) <$> gaRandom
    (flip S.index) winner <$> S.sort <$> seqChoose n pop

Without a type signature, the compiler tells me the tournament signature is:

tournament
  :: (Floating a, Ord a1, RealFrac a, Random a) =>
     Int -> a -> S.Seq a1 -> StateT GA Data.Functor.Identity.Identity a1

Which looks fine with me. But when I use it:

t2 = do
    g <- newStdGen
    let a = evalState (tournament 5 0.9 (S.fromList [1..10])) (GA g)
    return ()

I get the error:

GA.hs:85:37:
    No instance for (Fractional a0) arising from the literal `0.9'
    The type variable `a0' is ambiguous
    Possible fix: add a type signature that fixes these type variable(s)
    Note: there are several potential instances:
      instance Fractional Double -- Defined in `GHC.Float'
      instance Fractional Float -- Defined in `GHC.Float'
      instance Integral a => Fractional (GHC.Real.Ratio a)
        -- Defined in `GHC.Real'
      ...plus three others
    In the second argument of `tournament', namely `0.9'
    In the first argument of `evalState', namely
      `(tournament 5 0.9 (S.fromList [1 .. 10]))'
    In the expression:
      evalState (tournament 5 0.9 (S.fromList [1 .. 10])) (GA g)

Which leads to my first question, why doesn't RealFrac imply Fractional? The type signature has RealFrac, but the error complains about lack of an instance for Fractional.

Second, I copy-and-paste the type signature back into the code and add Fractional a:

tournament 
  :: (Floating a, Ord a1, RealFrac a, Fractional a, Random a) =>
     Int -> a -> S.Seq a1 -> State GA a1
tournament n p pop = do
    winner <- (\w -> min (n - 1) (floor (log w / log (1-p)))) <$> gaRandom
    (flip S.index) winner <$> S.sort <$> seqChoose n pop

And now the error I get is:

GA.hs:88:24:
    No instance for (Random a0) arising from a use of `tournament'
    The type variable `a0' is ambiguous
    Possible fix: add a type signature that fixes these type variable(s)
    Note: there are several potential instances:
      instance Random Bool -- Defined in `System.Random'
      instance Random Foreign.C.Types.CChar -- Defined in `System.Random'
      instance Random Foreign.C.Types.CDouble
        -- Defined in `System.Random'
      ...plus 33 others
    In the first argument of `evalState', namely
      `(tournament 5 0.9 (S.fromList [1 .. 10]))'
    In the expression:
      evalState (tournament 5 0.9 (S.fromList [1 .. 10])) (GA g)
    In an equation for `a':
        a = evalState (tournament 5 0.9 (S.fromList [1 .. 10])) (GA g)

Which now confuses me further because I don't have a type variable a0. Which leads to my second question: Obviously I'm misunderstanding something, but what?

Answer 1

In short, you need to fix a concrete type for 0.9 like Double. You can do that with an inline type annotation (0.9 :: Double).

In long: numeric literals are a little strange in Haskell. In general, Haskell needs a way to project syntax (0, 0.0, 0e0) into semantics (Int, Integer, Rational, Double) while maintaining generality for as long as possible (Num, Fractional, RealFrac). Let's see how it's done.

If you type numeric literals by themselves you get generic types

>>> :t 1
1 :: Num a => a

>>> :t 1.0
1.0 :: Fractional a => a

>>> :t 1e0
1e0 :: Fractional a => a

Which means that we need to fix the concrete implementation of a before it can be used. In practice, this type variable a gets carried along

>>> :t [1,2,3]
[1,2,3] :: Num a => [a]
>>> :t [1e0,2,3]
[1e0,2,3] :: Fractional a => [a]

If it's helpful, it can be useful to think of the syntax as being translated like this

1     ===   fromInteger  (1   :: Integer)   :: Num a        => a
1.0   ===   fromRational (1.0 :: Rational)  :: Fractional a => a

But we can at various times eliminate the type variable

>>> :t show 3
show 3 :: String

How does Haskell know what the type of 3 is when we've never declared it? It defaults, when possible. In particular, if you turn on -Wall you'll see this

>>> show 1e3

<interactive>:63:6: Warning:
    Defaulting the following constraint(s) to type `Double'
      (Fractional a0)
        arising from the literal `1e3' at <interactive>:63:6-8
      (Show a0) arising from a use of `show' at <interactive>:63:1-4
    In the first argument of `show', namely `1e3'
    In the expression: show 1e3
    In an equation for `it': it = show 1e3

"1000.0"

This defaulting behavior is controlled by an almost-never-used pragma default which "by default" is

default (Integer, Double)

Which works as

Each defaultable variable is replaced by the first type in the default list 
that is an instance of all the ambiguous variable's classes. It is a static 
error if no such type is found.

So, what's likely happening is that you're constraining 0.9 to some class which Double does not instantiate. During its search, Haskell is giving up after not finding the Fractional class and it introduces that new a0 variable to represent this hitherto unreferenced, unknown type of 0.9.

As stated at first, you probably want an inline annotation to Double to help the inferencer along. It's possible to add to your default list, but it's a bad idea as people rarely use that feature.

Answer 2

The problem isn't with the typeclasses, it's that GHC doesn't know which instance to use for `(Fractional a, RealFrac a, Floating a, Random a). If you specify it as

tournament 5 (0.9 :: Double) (S.fromList [1..10])

Then it should work (or at least it worked for me using your gist)