In today’s Programming Praxis exercise we have to find all the ways a given number can be written as the sum of the squares of two other numbers. Let’s get started.

All we really have to do is to convert the four cases of Dijkstra’s algorithm (listed on the second page of the exercise) from English to Haskell, which is trivial. To avoid repeating ourselves, we pattern match on the result of the comparison between x*x + y*y and n instead of recalculating it three times.

squareSum :: Integer -> [(Integer, Integer)]
squareSum n = b (ceiling . sqrt $ fromIntegral n) 0 where
b x y = if x < y then [] else case compare (x*x + y*y) n of
LT -> b x (y + 1)
EQ -> (x, y) : b (x - 1) (y + 1)
GT -> b (x - 1) y

A quick test shows us that everything’s working correctly.

main :: IO ()
main = do print $ squareSum 50
print $ squareSum 48612265
print $ squareSum 999

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, dijkstra, Haskell, kata, praxis, programming, squares, sum

This entry was posted on January 5, 2010 at 1:40 pm and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply