I've written the following implementation of the algorithm in this article http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec02.pdf sqRoot n scale = sqRoot' (5*n) 5 where sqRoot' a b | floor (logBase 10 b) >= scale = div b 10 | a >= b = sqRoot' (a-b) (b+10) | otherwise = sqRoot' (a*100) ((100 * (div b 10)) + (mod b 10)) Since this involves whole numbers only, I was surprised by the following run-time error. *Main> sqRoot 2 5 <interactive>:1:0: Ambiguous type variable `t' in the constraints: `RealFrac t' arising from a use of `sqRoot' at <interactive>:1:0-9 `Floating t' arising from a use of `sqRoot' at <interactive>:1:0-9 `Integral t' arising from a use of `sqRoot' at <interactive>:1:0-9 Probable fix: add a type signature that fixes these type variable(s) What am I missing? Logesh Pillay
Logesh Pillay wrote:
Since this involves whole numbers only, I was surprised by the following run-time error...
The type of logBase is Floating a => a -> a -> a So by using b as an argument to logBase, you are forcing it to be in a type that is an instance of Floating. Use "fromIntegral b". Regards, Yitz
Am Sonntag, 24. August 2008 19:38 schrieb Logesh Pillay:
I've written the following implementation of the algorithm in this article http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec02.pdf
sqRoot n scale = sqRoot' (5*n) 5 where sqRoot' a b
| floor (logBase 10 b) >= scale = div b 10 | a >= b = sqRoot' (a-b) (b+10) | otherwise = sqRoot' (a*100) ((100 * (div b
10)) + (mod b 10))
Since this involves whole numbers only, I was surprised by the following run-time error.
*Main> sqRoot 2 5
<interactive>:1:0: Ambiguous type variable `t' in the constraints: `RealFrac t' arising from a use of `sqRoot' at <interactive>:1:0-9 `Floating t' arising from a use of `sqRoot' at <interactive>:1:0-9 `Integral t' arising from a use of `sqRoot' at <interactive>:1:0-9 Probable fix: add a type signature that fixes these type variable(s)
What am I missing?
Logesh Pillay
There is no automatic conversion between different numeric types, you must do that explicitly, except for numeric literals. From the guard a >= b (and the expression a-b) follows that a and b must have the same type. From the expressions (b `div` 10) and (b `mod` 10) follows that that type must belong to the type class Integral. From the use of logBase follows that that type must belong to the type class Floating. Finally, from the use of floor follows that that type must also belong to the type class RealFrac. If you ask GHCi for the type of sqRoot, it will tell you: *Main> :t sqRoot sqRoot :: (Integral t, Floating t, RealFrac t, Integral b) => t -> b -> t The problem occurs when you want to evaluate sqRoot, because then the types t and b must be decided. Since only standard numeric type classes are involved, GHCi is willing to default the ambiguous types, so it will look if it can find a type which simultaneously belongs to all three type classes in the default list (I think the default list GHCi uses is (Integer, Double)). Of course it doesn't find such a type, so it complains. Note, however, that it doesn't complain about the scale parameter, that can be defaulted to Integer without any problem. The ugly (and insane) fix would be to provide instances of Fractional, RealFrac and Floating for Integer or an instance of Integral for Double. The good fix is to insert calls to the apprpriate conversion function where necessary, for example sqRoot n scale = sqRoot' (5*n) 5 where sqRoot' a b | floor (logBase 10 $ fromIntegral b) >= scale = div b 10 | a >= b = sqRoot' (a-b) (b+10) | otherwise = sqRoot' (a*100) ((100 * (div b 10)) + (mod b 10)) works. HTH, Daniel
G'day all.
Quoting Daniel Fischer
The good fix is to insert calls to the apprpriate conversion function where necessary, for example
sqRoot n scale = sqRoot' (5*n) 5 where sqRoot' a b | floor (logBase 10 $ fromIntegral b) >= scale = div b 10 | a >= b = sqRoot' (a-b) (b+10) | otherwise = sqRoot' (a*100) ((100 * (div b 10)) + (mod b 10))
The problem here is that floating-point numbers do not have arbitrary precision, whereas Integers do. For very large numbers, the conversion might not be possible. Option #1: sqRoot n scale = sqRoot' (5*n) 5 where sqRoot' a b | b >= invScale = div b 10 | a >= b = sqRoot' (a-b) (b+10) | otherwise = sqRoot' (a*100) ((100 * (div b 10)) + (mod b 10)) invScale = 10^scale Option #2: sqRoot n scale = sqRoot' (5*n) 5 where sqRoot' a b | length (show b) >= scale = div b 10 -- May be an off-by-one error here. | a >= b = sqRoot' (a-b) (b+10) | otherwise = sqRoot' (a*100) ((100 * (div b 10)) + (mod b 10)) Sadly, option #2 (and option #3, not shown, which is essentially to implement your own integer-only floor-log-base-10) destroys the pretty "mostly subtraction only" property of the algorithm. Cheers, Andrew Bromage
G'day all. One more thing, a quick comment on Haskell style. I wrote:
sqRoot n scale = sqRoot' (5*n) 5 where sqRoot' a b | b >= invScale = div b 10 | a >= b = sqRoot' (a-b) (b+10) | otherwise = sqRoot' (a*100) ((100 * (div b 10)) + (mod b 10)) invScale = 10^scale
In this kind of algorithm, you are almost always better off decoupling the end-of-loop test from the main computation stuff: sqRoot n scale = findEnd (sqRoot' (5*n) 5) where findEnd ((a,b):rest) | b >= 10^scale = b `div` 10 | otherwise = findEnd rest -- Rewrote this a bit. I don't like the "case" sqRoot' a b = (a,b) : case () of _ | a >= b -> sqRoot' (a - b) (b + 10) otherwise -> let (q,r) = b `divMod` 10 in sqRoot' (a * 100) (100 * q + r) There are several reasons why this is better. The main one is testability. You have, in your specification, an execution trace of the algorithm on some sample data. Use it. A second reason is because you would have tracked down your type error quicker, because it would only have been in one of these functions. A third reason is that there are circumstances where you might like to change termination conditions. This is especially true in this sort of numeric iterate-to-fixpoint algorithm. For more information, see: http://www.haskell.org/haskellwiki/Data_structures_not_functions Cheers, Andrew Bromage
participants (4)
-
ajb＠spamcop.net -
Daniel Fischer -
Logesh Pillay -
Yitzchak Gale