Short haskell program to generate equivalence classes of a relation R defined on the natural numbers such that aRb iff there exist odd integers p and q such that ap = bq

equiv.hs

-- The relation R defined as a function:
-- Takes two integers and returns true
-- if aRb and false otherwise
r :: Integer -> Integer -> Bool

-- Why gcd? The relation r can be 
-- redefined in a way that's more
-- convenient to represent computationally:
-- aRb if the numerator and denominator
-- of the simplest form of a/b are both odd.
-- E.g. if a = 10 and b = 6, since 10/6 reduces
-- to 5/3, 10R6
--
-- We can find out what the simplest numerator
-- and denominator are for a/b by dividing both
-- a and b by their greatest common divisor.

r a b =
    -- find the gcd of a and b
    let g = gcd a b in
    -- let x and y equal a / g and b / g respectively. Note: `div` is integer division
    let (x, y) = (a `div` g, b `div` g) in
    -- return whether or not both x and y are odd
    odd x && odd y 

-- Define a list of numbers representing the equivalence classes we want
-- to observe. For now, 1 through 10 is more than enough.
classes = [1..10]

-- The highest number we want to appear in our equivalence classes.
-- Any members of equivalence classes that are greater than 30 won't
-- be generated. These classes technically have infinite size, but we
-- only need to see a small part of them to find out what's going on.
maxRange = 30

-- Define a function to generate an equivalence class
-- by filtering a list of numbers from 1 through maxRange
-- according to whether or not they are related to the input
--
-- "filter" takes a "rule" and a list, and returns a new
-- list free of values from the original which do not
-- satisfy the rule. In this case, our rule is that
-- in order to be in the output list, the value of
-- the original list must be related to a. In other
-- words, aRb must be true.
genClass :: Integer -> [Integer]
genClass a = filter relatedToA [1..maxRange]
    where
        relatedToA = r a

main :: IO ()
main =
    -- The main function just outputs each equivalence class on its own line in a nice looking way
    -- It's not interesting enough to explain, but it's ugly enough to make me feel bad for not explaining
    putStr . unlines . zipWith (\n l -> show n ++ ": " ++ show l) classes . map genClass $ classes