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 |
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. |
In reply to this post by Logesh Pillay-3
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 |
In reply to this post by Daniel Fischer-4
G'day all.
Quoting Daniel Fischer <[hidden email]>: > 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 |
Free forum by Nabble | Edit this page |