Puzzling type error

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Puzzling type error

Logesh Pillay-3
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


Reply | Threaded
Open this post in threaded view
|

Puzzling type error

Daniel Fischer-4
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.

Reply | Threaded
Open this post in threaded view
|

Puzzling type error

Yitzchak Gale
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
Reply | Threaded
Open this post in threaded view
|

Puzzling type error

ajb@spamcop.net
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
Reply | Threaded
Open this post in threaded view
|

Puzzling type error

ajb@spamcop.net
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