[Haskell-beginners] Puzzling type error

ajb at spamcop.net ajb at spamcop.net
Sun Aug 24 21:59:41 EDT 2008

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)
         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

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:


Andrew Bromage

More information about the Beginners mailing list