Square root calculation with Newton's method

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

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.

• It's applying a mathematical function to a value.

• It's producing a sequence by applying that function recursively.

• 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)  (guess + x / guess) / 2) initial

I wouldn't use that version, I think it's a little opaque with all of that inlin

StackExchange Code Review Q#63743, answer score: 3