[Haskell-beginners] type puzzlement

[Jürgen Doser]

El mar, 20-07-2010 a las 23:26 -0700, prad escribió:
> i'm looking at a factoring function which i've defined as:
> 
> factorList = map factors
>     where   factors p = [ f | f <- [1..fsq p], p `mod` f == 0 ]
>             fsq :: (RealFrac a, Integral b, Floating a) => a -> b
>             fsq = floor . sqrt
> 
> it goes into ghci just fine, but then when i give it something to go i
> get errors:

Btw, it only loads fine in ghci because you apparently turned of the
monomorphism restriction.

> *Main> :r 
> Ok, modules loaded: Main.
> *Main> factorList [4,8,16,32]
> 
> <interactive>:1:0:
>     Ambiguous type variable `t' in the constraints:
>       `RealFrac t' arising from a use of `it' at <interactive>:1:0-21
>       `Integral t' arising from a use of `it' at <interactive>:1:0-21
>       `Floating t' arising from a use of `it' at <interactive>:1:0-21
>     Probable fix: add a type signature that fixes these type variable(s)
> 
> 
> so i'm not sure where the unhappiness lies because there is no line
> number.

There is: <interactive>:1:0-21 says the error is in line 1, columns 0-21
of the interactive input.

It is saying that factorList is a perfectly fine function for ghci, but
it doesn't know what type its argument [4,8,16,32] should be. Should it
be a list of integers, floats, doubles, etc?  This is because number
literals are overloaded in Haskell.  And it is suggesting that you tell
ghci what type you want that list to be by giving a type signature. The
only requirement is that the element type should be in the type-classes
'RealFrac', 'Integral', and 'Floating', which is where the real problem
is: there simply is no predefined type that fulfills these type-class
constraints. Integral

Usually, you don't encounter this problem, because haskell has
defaulting rules to resolve exactly this issue. First it tries the type
Integer, then the type Double. Here, Integer is in the Integral class,
and Double is in the Floating and RealFrac classes, but neither is in
all three. And it doesn't make sense for a type to be in both Integral
and Floating, they are mutually exclusive. Only ghc does not know this.

> i examine fsq more closely, because that looks like the most
> complicated part of the whole thing and try to define it separately:
> 
> *Main> let fsq = floor . sqrt
> *Main> :t fsq
> fsq :: (RealFrac a, Integral b, Floating a) => a -> b

This is fine

> ok this seems weird to me because i would have thought things are far
> simpler with 
> 
> fsq :: Int -> Int
>
> however, i guess because we have a composition here, the compiler wants
> the fact that 
> 
> sqrt :: (Floating a) => a -> a
> floor :: (RealFrac a, Integral b) => a -> b
> 
> incorporated in the type?

exactly.

> but even if i put the 
> 
> fsq :: (RealFrac a, Integral b, Floating a) => a -> b
> 
> in to the factorList, i get errors, 

Well, you just added a type signature that ghc knew already, so what did
you expect it to do?

> though the fsq works fine on its
> own.

I guess you mean the following works:

*Main> fsq 9
3

However:

*Main> fsq (9::Int)

<interactive>:1:0:
    No instances for (Floating Int, RealFrac Int)
    ....

Again, number literals are overloaded, so the 9 without an explicit type
signature is defaulted by ghci to a Double, not an Int or an Integer,
because ghc knows that Integer doesn't work.

If you want fsq to have the type Int -> Int, you have to convert the
argument into a floating number first, before you use sqrt. like this:

*Main> let fsq = floor . sqrt . fromIntegral
*Main> :t fsq
fsq :: (Integral b, Integral a) => a -> b


But I would suggest to use a proper integer square root function,
floating point numbers have limited accuracy :)

*Main> let x = 2^53 in fsq (x * x) == x
True
*Main> let x = 2^53+1 in fsq (x * x) == x
False
*Main> fsq (9999999999999999^2)
10000000000000000

etc.

	Jürgen