{-
   Title: Finding all the Pythagorean triples
   Author: Robin Cockett
   Date: 22 Jan 2002
   Purpose: to illustrate an application of list comprepension

-}

--  This is a straightforward statement of the problem: the resulting code 
--  is rather inefficient ... also it produces reducible triples

pythag n = [(x,y,z) | x <- [1..n]
                    , y <- [1..n]
                    , z <- [1..n]
                    , pyth(x,y,z)
                    , x <= y] where
         pyth (x,y,z) = (x*x + y*y == z*z)

--  Here is a more sophisticated version which is more efficient 
--  and only produces irreducible Pythagorean triples (try it for 
--  numbers less than a thousand.  Can you see why it is more efficient?

pythagor:: Integer -> [(Integer,Integer,Integer)]
pythagor n = [(x,y,z) | x <- [1..n]
                      , y <- [(x+1)..(min (bound x n) (div (x*x) 2))]
                      , hcf x y == 1
                      , z <- [y+1..(min n (x+y))]
                      , pyth (x,y,z)] where
         hcf n m
           | n==m  = n
           | n < m = hcf n (m-n)
           | n > m = hcf m (n-m)
         min n m
           | n < m = n
           | otherwise = m
         pyth (x,y,z) = (x*x + y*y == z*z)
         bound x n = floor( sqrt (fromInteger(n*n - x*x)))