Adventures in Haskell

So I’ve decided that it’s time to expand my horizons and put a new programming language under my belt. I’ve been told by a number of people now that Haskell is awesome, so I decided to give learning it a go. I’ve been reading over Learn You a Haskell for Great Good! I’m not done reading through it, but I definitely recommend it to anyone who wants to learn Haskell. Anyhow, over the course of my tinkering around with Haskell, I’ve learnt that Haskell is full of freaky voodoo mathemagics (yes, that’s a word now).

Since I still haven’t managed to figure out I/O, I decided to start by rolling my own square root function. There’s a fairly simple algorithm to do this:

Suppose we want to find the square root of X. We can start by making a guess, we’ll call it G (1 tends to be a good start). We can then square our guess to see if it works out to X, if not, we can get a closer approximation by taking the average of G and G/X. We simply need to repeat this process over and over again until we converge on the square root of X.

To implement this, I wrote two simple functions. First, there was the square root function itself. It looked like this:

sqrt' :: (Floating a, Ord a) => a -> a
sqrt' x
  | x < 0 = error "square root of negative number"
  | otherwise = limit (\g -> (g + x / g) / 2) 1

Basically, the sqrt' function checks the value of its input (x), if it’s negative, it throws an error, otherwise, it calls a limit function that takes a function and a value, and repeats that function over and over until we converge on a constant value. I’ve defined the limit function as follows:

limit :: Eq a => (a -> a) -> a -> a
limit f x
  | thisTry == x = x
  | otherwise = limit f thisTry
  where thisTry = f x

Naturally, I wanted to see how quickly and accurately my function would calculate square roots, so I started out with a number with a known square root… say 4. When I ran the function, this was the instantaneous result:

*Main> sqrt' 4
2.0

Good. That’s what I would expect to see. Let’s see what happens when we try to use the function to calculate the square root of 2, comparing it to the built-in square root function.

*Main> sqrt' 2
1.414213562373095
*Main> sqrt 2
1.4142135623730951

Excellent. So we’ve now established that the function will quickly calculate square roots. Next, I wanted to try doing a little stress testing. I happen to know (from being bored in math class back in my high school days) that if you take a large nubmer and repeatedly take the square root, you’ll eventually converge on the number 1. Let’s try it with a really large number… say 10¹⁰. Putting my newly created limit function to the test, I got the following result immediately:

*Main> limit (\x -> sqrt' x) (10^10)
1.0

That’s impressive, I was expecting it to take at least a second or so to calculate, after all, 10¹⁰ is a pretty large number. It should have to loop around quite a few times before it converges on 1. Let’s try a googol (10¹⁰⁰):

*Main> limit (\x -> sqrt' x) (10^100)
1.0

Still, instantaneous? Challenge accepted. How big do we need to go before we crash the system, or at least slow it down?

As it turns out, pretty big. I got as high as 10⁴⁰⁰ before I managed to hang the machine (while still not consuming more than 2% of my total system memory). That’s pretty impressive. My previous attempt 10³⁰⁰ was still instantaneous.

The one thing I know for sure is that the next time I need to write a program that runs some serious computations, I’ll definitely be considering Haskell.

Posted in Member Blogs |
Tags: haskell, voodoo