Skip to content

Instantly share code, notes, and snippets.

Created April 10, 2021 03:51
Show Gist options
  • Save rosalogia/7f88da5ea4a08c51d6f01f2c98bed51e to your computer and use it in GitHub Desktop.
Save rosalogia/7f88da5ea4a08c51d6f01f2c98bed51e to your computer and use it in GitHub Desktop.
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
-- 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]
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment