Instantly share code, notes, and snippets.

# rosalogia/equiv.hs

Created April 10, 2021 03:51
Show Gist options
• 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 -- 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