Square root calculation with Newton's method

Question

I am currently learning Haskell in parallel of following the Scala course proposed by Coursera.

To practice Haskell I try to implement exercices and/or course example from this course.

So there is a simpler square root estimation implementation:

sqrt' :: Double -> Double -> Double
sqrt' x guess
 | guessIsGoodEnough = guess
 | otherwise = sqrt' x improvedGuess
 where
 -- Test the precision of the guess
 precision = 0.001
 guessIsGoodEnough = abs (guess * guess - x) < precision * x
 -- Improve our guessed square
 improvedGuess = (guess + x / guess) / 2

I welcome any feedback on this, I mostly aim for clarity and simplicity (one-liner welcome, but I do not specificaly aim for that ;) ).

Answer 1

Somewhere between primitive recursion and grossly clever one-liners we can find a happy medium using functions from the Prelude.

To start though I'll look at the cosmetic. Immediately I'm confused by name and signature of the function, the square root is a function of a single number, not two. It's confusing for your function to be named sqrt' when typically the tick mark is used in Haskell to distinguish strict functions from lazy ones, or to name successive iterations on some value. When you're browsing your Haddock documentation later or coming back to this code in three years you'll be stupefied by sqrt', but probably have a pretty good idea what refineSqrtGuess might do.

Next, I would rewrite the function so that x isn't copied around everywhere. Since its value doesn't change, make that clear.

refineSqrtGuess :: Double -> Double -> Double
refineSqrtGuess x = refine
 where
 refine guess
 | guessIsGoodEnough = guess
 | otherwise = refine improvedGuess
 where
 -- Test the precision of the guess
 precision = 0.001
 guessIsGoodEnough = abs (guess * guess - x) < precision * x
 -- Improve our guessed square
 improvedGuess = (guess + x / guess) / 2

Also those comments are unnecessary, I think it's fairly clear from your descriptive names what's going on.

Alright now for the fun stuff. Let's begin by identifying the individual components of what your function is doing.

1. It's applying a mathematical function to a value.
2. It's producing a sequence by applying that function recursively.
3. It's choosing the first value from that sequence which matches a predicate.

Your function is a very imperative, monolithic implementation of those three components, but in Haskell-land composition is king. Let's try tackling each separately and see how they can be composed.

Number one is easy since we already know the math we're going to be doing, just roll up the improvedGuess value into a function.

next :: Double -> Double -> Double
next x guess = (guess + x / guess) / 2

Number two requires we know a bit about creating sequences in Haskell, which of course are usually lists, so we can take a look at the documentation for Data.List. As it turns out there's a function that repeatedly applies a function f to a value x for us, iterate. Here's how we'd use it.

guesses :: Double -> Double -> [Double]
guesses x initial = iterate (next x) initial

Now the third bullet on my list should really be broken in two, one bullet point for the predicate, and another for searching the sequence with it. But that's alright of course, our personal design documents don't have to be perfect from the get-go to be useful.

The predicate is of course the guessIsGoodEnough value, expressed as a function.

acceptGuess :: Double -> Double -> Bool
acceptGuess x guess = abs (guess * guess - x) < precision * x
 where precision = 0.001

And if we look back at the documentation for Data.List, sure enough under the section heading "Searching with a predicate" find looks like it does what we want, just note that it returns a Maybe a value. This is of course because the predicate we provide might not match any element of the given list, which now obligates me to point out that you should always code defensively and consider the totality of your functions on any given input. I'll address some concerns in iterations on my solution but here's how we'd put it all together.

import Data.List (find)
import Data.Maybe (fromJust)
refineSqrtGuess :: Double -> Double -> Double
refineSqrtGuess x initial = fromJust $ find (acceptGuess x) (guesses x initial)

By using higher order functions to handle the iterative and recursive aspects of the problem, we end up with a solution that almost reads like prose.

Appendix: Edge Cases & Errors

There's a lot that could go in this section, so I'll just point out a few things so this doesn't get tedious.

fromJust should be avoided, it isn't total and if we did call it on a Nothing value we'd get a big fat *** Exception: .... Consider changing the signature of the function to return a Maybe Double.

This could happen if we changed our code to not produce an infinite list of guesses (guesses x initial = take 500 $ iterate ...). What if precision was changed to 0 by another programmer (or future you) or floating point math throws you a curveball?

Appendix: Two-liner

After writing your function in terms of higher order functions it's usually trivial to then turn it into a one-liner, just inline all of the function calls. In this particular case we've got a two-liner unless your terminal happens to be very wide.

refineSqrtGuess :: Double -> Double -> Maybe Double
refineSqrtGuess x initial = find (\guess -> abs (guess^2 - x) < 0.001 * x)
 $ iterate (\guess -> (guess + x / guess) / 2) initial

I wouldn't use that version, I think it's a little opaque with all of that inlined math. But I would definitely use this one.

refineSqrtGuess :: Double -> Double -> Maybe Double
refineSqrtGuess x initial = find withinPrecision $ iterate newtons initial
 where
 withinPrecision guess = abs (guess^2 - x) < 0.001 * x
 newtons guess = (guess + x / guess) / 2

• Mayeu: Thank you for your really complete feedback on this! I am wondering how do you choose to make function out of a where clause? The only benefit I see for that (in case you do not need to reuse it elsewhere obviously) is that you have better control of the type signature. About the error handling, I did not already went through the different error handling possibility for Haskell, but indeed the current code is not safe enough for real use! (And will iterate infinitely sometimes, like with a precision = 0)
• bisserlis: Like the refine function in my first code snippet you mean? I would generally do this whenever you're passed a value in the initial call of the function that then never changes, as x does. You can see that in my version it doesn't get passed to each new recursive step, but instead every call of refine uses the same original binding of x from the call to refineSqrtGuess. If refine were to take x as a parameter that would imply that it was changing or could change with each call, since it doesn't, it's clear that its value is fixed.
• Mayeu: No I am speaking about the guessIsGoodEnough and improvedGuess that you choose to extract from their where in your implementation :)
• bisserlis: Ah gotcha. Well you can see in my final version at the bottom (edited in after your first comment) I did end up moving those definitions back into a where clause. I extracted it originally to emphasize composing small functions that are each responsible for just one thing. This makes them easier to test, replace or reuse, especially useful when you're exploring your code on the REPL. Imagine reusing your code to find cube roots, you could pass guesses a new generating function (cubeNext) and use a different predicate (acceptCubeGuess), if you parameterize sufficiently. Make sense?
• Mayeu: Thank you for detailling your reason :) Totally making sense!