{"header":{"message":"Represent nimbers as natural numbers instead of sets of sets","description":null,"timestamp":"2024-04-21T04:32:15Z","authors":[{"email":"noiioiu@cocaine.ninja","name":"noiioiu"}]},"hash":"PMF36FUOINXVVNP5XW6ZOFPPWFBRK62O4VCX45NE4Y4GDPL2Z3BQC","authors":[],"deps":{"hashes":[["PMF36FUOINXVVNP5XW6ZOFPPWFBRK62O4VCX45NE4Y4GDPL2Z3BQC","Represent nimbers as natural numbers instead of sets of sets"],["AA",null],["6U24OB4HZGUVZZTOEHQKTBOHGV5FKEE4EQDGJF6IP3QQ3HXNNWUQC","Add tests for additive and multiplicative identities"],["ASGE7I4JJ3HTHHSQKVNL74ZVZQ6WTYX6M54FYKOUE4PCPRPUNSUQC","Add Nat type for small natural numbers"],["XBKUMBMDBZ37XISOWRJU3QRUUYP3TDT7MO6GYKTLCSTRPESASJTQC","Use a different algorithm for division"],["VG2W2CCBAB7KY4FSDKB4ZLBRYO763USFRDHUOA3GQOTVNS6XQLSAC","Add test for involutivity"],["V7A5CRSQQY3WTZFNH73E6J4YOKE7YJMEW2XW7YJTM37UNTWRMZJQC","Add Fractional instance and test"],["2JT446RMTHP23QL57CULGRWI7A7ATV7HRV2D5FZ4SULIDU5AD4KAC","Add haddock for Num instance"],["ADE3QH6CJXDMZNXCPR7YTFLUHUV6TFP7Z3V7SMKUELP3JVGCACXQC","Add definition of mex operator"],["VRPOSMITS7VRSIJU6YNEBELCUBTHPMPJD6F6F5PE35R2KECS42KAC","Initial commit"]],"deps":["6U24OB4HZGUVZZTOEHQKTBOHGV5FKEE4EQDGJF6IP3QQ3HXNNWUQC","ASGE7I4JJ3HTHHSQKVNL74ZVZQ6WTYX6M54FYKOUE4PCPRPUNSUQC"],"known":["VRPOSMITS7VRSIJU6YNEBELCUBTHPMPJD6F6F5PE35R2KECS42KAC","ADE3QH6CJXDMZNXCPR7YTFLUHUV6TFP7Z3V7SMKUELP3JVGCACXQC","2JT446RMTHP23QL57CULGRWI7A7ATV7HRV2D5FZ4SULIDU5AD4KAC","V7A5CRSQQY3WTZFNH73E6J4YOKE7YJMEW2XW7YJTM37UNTWRMZJQC","VG2W2CCBAB7KY4FSDKB4ZLBRYO763USFRDHUOA3GQOTVNS6XQLSAC","XBKUMBMDBZ37XISOWRJU3QRUUYP3TDT7MO6GYKTLCSTRPESASJTQC"]},"hunks":[{"Edit":{"inode":{"change":4,"pos":22},"path":"test/Main.hs","line":4,"atom":{"NewVertex":{"up_context":[{"change":2,"pos":80}],"down_context":[{"change":4,"pos":2}],"flag":"BLOCK","start":2,"end":35,"inode":{"change":4,"pos":22}}},"contents":[{"Add":"{-# LANGUAGE TemplateHaskell #-}"}]}},{"Edit":{"inode":{"change":4,"pos":22},"path":"test/Main.hs","line":12,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":58}],"down_context":[{"change":4,"pos":183}],"flag":"BLOCK","start":36,"end":62,"inode":{"change":4,"pos":22}}},"contents":[{"Add":"import Data.Word (Word64)"}]}},{"Replacement":{"inode":{"change":4,"pos":22},"path":"test/Main.hs","line":15,"ins":{"up_context":[{"change":4,"pos":216}],"down_context":[{"change":4,"pos":256}],"flag":"BLOCK","start":63,"end":123,"inode":{"change":4,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":216},"to":{"change":4,"start":216,"end":256},"introduced_by":4}],"inode":{"change":4,"pos":22}},"ins_contents":[{"Add":" arbitrary = fromIntegral @Word64 . getLarge <$> arbitrary"}],"del_contents":[{"Del":" arbitrary = fromInteger <$> arbitrary\n"}]}},{"Edit":{"inode":{"change":4,"pos":22},"path":"test/Main.hs","line":40,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":98}],"down_context":[{"change":4,"pos":98}],"flag":"BLOCK","start":124,"end":234,"inode":{"change":4,"pos":22}}},"contents":[{"Add":""},{"Add":"pure []"},{"Add":"runTests :: IO Bool"},{"Add":"runTests = $forAllProperties $ verboseCheckWithResult stdArgs {maxSuccess = 200}"}]}},{"Replacement":{"inode":{"change":4,"pos":22},"path":"test/Main.hs","line":46,"ins":{"up_context":[{"change":4,"pos":605}],"down_context":[],"flag":"BLOCK","start":235,"end":302,"inode":{"change":4,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":605},"to":{"change":2,"start":237,"end":410},"introduced_by":2},{"previous":"","flag":"DELETED","from":{"change":4,"pos":230},"to":{"change":4,"start":415,"end":527},"introduced_by":4},{"previous":"","flag":"DELETED","from":{"change":2,"pos":410},"to":{"change":4,"start":415,"end":527},"introduced_by":2},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":415},"to":{"change":4,"start":415,"end":527},"introduced_by":4}],"inode":{"change":4,"pos":22}},"ins_contents":[{"Add":"main = do success <- runTests"},{"Add":" unless success exitFailure"}],"del_contents":[{"Del":"main = check prop_neg >> check prop_add_id >> check prop_mult_id >> check prop_assoc_add >> check prop_assoc_mul >> check prop_distrib >> check prop_recip >> check prop_inv\n"},{"Del":" where\n check prop = do\n result <- verboseCheckResult prop\n unless (isSuccess result) exitFailure\n"}]}},{"Edit":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":1,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":880}],"down_context":[{"change":4,"pos":530}],"flag":"BLOCK","start":305,"end":341,"inode":{"change":4,"pos":880}}},"contents":[{"Add":"{-# LANGUAGE DerivingStrategies #-}"}]}},{"Edit":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":13,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1489},"to":{"change":4,"start":1489,"end":1490},"introduced_by":4},{"previous":"","flag":"DELETED","from":{"change":4,"pos":609},"to":{"change":4,"start":1490,"end":1521},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1490},"to":{"change":4,"start":1490,"end":1521},"introduced_by":4}],"inode":{"change":4,"pos":880}}},"contents":[{"Del":"\n"},{"Del":"import Data.Set qualified as S\n"}]}},{"Replacement":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":14,"ins":{"up_context":[{"change":3,"pos":5}],"down_context":[{"change":4,"pos":1521}],"flag":"BLOCK","start":342,"end":359,"inode":{"change":4,"pos":880}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5},"to":{"change":3,"start":5,"end":48},"introduced_by":3}],"inode":{"change":4,"pos":880}},"ins_contents":[{"Add":"import Data.Bits"}],"del_contents":[{"Del":"-- | Small natural numbers.\ntype Nat = Int\n"}]}},{"Edit":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":16,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1522},"to":{"change":3,"start":49,"end":89},"introduced_by":3}],"inode":{"change":4,"pos":880}}},"contents":[{"Del":"-- | Arbitrarily large natural numbers.\n"}]}},{"Edit":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":17,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":4,"pos":710},"to":{"change":4,"start":1541,"end":1853},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1541},"to":{"change":4,"start":1541,"end":1853},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1853},"to":{"change":3,"start":90,"end":147},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":147},"to":{"change":4,"start":1914,"end":2146},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1914},"to":{"change":4,"start":1914,"end":2146},"introduced_by":4}],"inode":{"change":4,"pos":880}}},"contents":[{"Del":"\n-- | A finite nimber is represented as a sum of distinct 2-powers, each of which is represented as a product of distinct Fermat 2-powers.\n-- Hence @'Nimber' {'getNimber' = s}@ represents \$\\sum\\limits_{t \\in s} \\prod\\limits_{n \\in t} 2^{2^n}\$. This representation makes sums and products easy to calculate.\n"},{"Del":"newtype Nimber = Nimber {getNimber :: S.Set (S.Set Nat)}\n"},{"Del":" deriving (Show, Eq)\n\nnimberToNatural :: Nimber -> Natural\n-- nimberToInteger = sum . S.map ((^) @_ @Integer 2 . sum . S.map (2^)) . getNimber\nnimberToNatural = sum . S.map (product . S.map ((^) @_ @Natural 2 . (2 ^))) . getNimber\n"}]}},{"Replacement":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":18,"ins":{"up_context":[{"change":4,"pos":2147}],"down_context":[{"change":4,"pos":2455}],"flag":"BLOCK","start":360,"end":454,"inode":{"change":4,"pos":880}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":2147},"to":{"change":4,"start":2147,"end":2455},"introduced_by":4}],"inode":{"change":4,"pos":880}},"ins_contents":[{"Add":"newtype Nimber = Nimber {getNimber :: Natural}"},{"Add":" deriving newtype (Show, Eq, Ord, Enum, Bits)"}],"del_contents":[{"Del":"-- | Nimbers are ordinals, so they are ordered. They also form a field, but they are not an ordered field.\ninstance Ord Nimber where\n n `compare` m = nimberToNatural n `compare` nimberToNatural m\n\ninstance Enum Nimber where\n toEnum = fromInteger . fromIntegral\n fromEnum = fromIntegral . nimberToNatural\n"}]}},{"Replacement":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":21,"ins":{"up_context":[{"change":4,"pos":2456}],"down_context":[{"change":4,"pos":2516}],"flag":"BLOCK","start":455,"end":525,"inode":{"change":4,"pos":880}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":2456},"to":{"change":3,"start":148,"end":202},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":202},"to":{"change":4,"start":2494,"end":2516},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":2494},"to":{"change":4,"start":2494,"end":2516},"introduced_by":4}],"inode":{"change":4,"pos":880}},"ins_contents":[{"Add":"twoPowers :: (Num a, Bits a, Integral b) => a -> [b]"},{"Add":"twoPowers 0 = []"}],"del_contents":[{"Del":"twoPowers :: (Integral a, Integral b) => a -> S.Set b\n"},{"Del":"twoPowers 0 = S.empty\n"}]}},{"Replacement":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":24,"ins":{"up_context":[{"change":4,"pos":2530}],"down_context":[{"change":4,"pos":2645}],"flag":"BLOCK","start":526,"end":606,"inode":{"change":4,"pos":880}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":2530},"to":{"change":4,"start":2530,"end":2645},"introduced_by":4}],"inode":{"change":4,"pos":880}},"ins_contents":[{"Add":" (if m `testBit` 0 then (0 :) else id) . fmap (+ 1) $ twoPowers (m `shiftR` 1)"}],"del_contents":[{"Del":" if even m\n then S.map (+ 1) $ twoPowers (m `div` 2)\n else S.insert 0 . S.map (+ 1) $ twoPowers (m `div` 2)\n"}]}},{"Replacement":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":26,"ins":{"up_context":[{"change":4,"pos":2646}],"down_context":[{"change":4,"pos":2740}],"flag":"BLOCK","start":607,"end":744,"inode":{"change":4,"pos":880}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":2646},"to":{"change":4,"start":2646,"end":2740},"introduced_by":4}],"inode":{"change":4,"pos":880}},"ins_contents":[{"Add":"floorLog :: (Num a, Bits a, Num b) => a -> b"},{"Add":"floorLog 0 = error \"Logarithm of 0\""},{"Add":"floorLog 1 = 0"},{"Add":"floorLog n = 1 + floorLog (n `shiftR` 1)"}],"del_contents":[{"Del":"delta :: (Ord a) => S.Set a -> S.Set a -> S.Set a\ndelta x y = (x S.\\\\ y) `S.union` (y S.\\\\ x)\n"}]}},{"Replacement":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":38,"ins":{"up_context":[{"change":4,"pos":2767}],"down_context":[{"change":4,"pos":3082}],"flag":"BLOCK","start":745,"end":801,"inode":{"change":4,"pos":880}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":2767},"to":{"change":4,"start":2767,"end":2841},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":2841},"to":{"change":3,"start":203,"end":258},"introduced_by":3}],"inode":{"change":4,"pos":880}},"ins_contents":[{"Add":" fromInteger = Nimber . fromIntegral . abs"},{"Add":" (+) = xor"}],"del_contents":[{"Del":" fromInteger = Nimber . S.map twoPowers . twoPowers . abs . fromIntegral\n"},{"Del":" (+) = (Nimber .) . (. getNimber) . delta . getNimber\n"}]}},{"Replacement":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":45,"ins":{"up_context":[{"change":4,"pos":3376}],"down_context":[{"change":4,"pos":3707}],"flag":"BLOCK","start":802,"end":993,"inode":{"change":4,"pos":880}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":3376},"to":{"change":4,"start":3376,"end":3707},"introduced_by":4}],"inode":{"change":4,"pos":880}},"ins_contents":[{"Add":" x <- twoPowers a"},{"Add":" y <- twoPowers b"},{"Add":" let cs = twoPowers $ x .&. y"},{"Add":" p = product $ fmap (\\c -> bit (bit c) + bit (bit c - 1)) cs"},{"Add":" d = bit $ x `xor` y"}],"del_contents":[{"Del":" x <- S.toList $ getNimber a\n y <- S.toList $ getNimber b\n let cs = x `S.intersection` y\n p = product $ S.map (\\c -> Nimber $ S.fromList [S.singleton c, S.fromList [0 .. c - 1]]) cs\n d = Nimber $ S.singleton $ x `delta` y\n -- (*d) . Nimber . S.singleton <$> S.toList (getNimber p)\n"}]}},{"Replacement":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":60,"ins":{"up_context":[{"change":4,"pos":18}],"down_context":[{"change":3,"pos":608}],"flag":"BLOCK","start":994,"end":1259,"inode":{"change":4,"pos":880}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":18},"to":{"change":4,"start":18,"end":51},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":51},"to":{"change":3,"start":259,"end":608},"introduced_by":3}],"inode":{"change":4,"pos":880}},"ins_contents":[{"Add":" recip n ="},{"Add":" let m = floorLog @Int $ floorLog n -- D = 2^2^m is the largest Fermat 2-power less than or equal to n"},{"Add":" a = n `shiftR` bit m -- n = aD+b"},{"Add":" aD = a `shiftL` bit m"},{"Add":" b = n `xor` aD"},{"Add":" semiD = bit (bit m - 1) -- semimultiple of D"}],"del_contents":[{"Del":" recip Nimber {getNimber = s} =\n"},{"Del":" let m = foldl max 0 $ S.unions s -- D = 2^2^m is the largest Fermat 2-power less than or equal to n\n aD = Nimber $ S.filter (S.member m) s -- n = aD+b\n b = Nimber $ S.filter (S.notMember m) s\n a = Nimber $ S.map (S.delete m) $ getNimber aD\n semiD = Nimber . S.singleton $ S.fromList [0 .. m - 1] -- semimultiple of D\n"}]}},{"Edit":{"inode":{"change":4,"pos":880},"path":"src/Nimbers.hs","line":67,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":4,"pos":466},"to":{"change":4,"start":3767,"end":4689},"introduced_by":4},{"previous":"","flag":"DELETED","from":{"change":3,"pos":663},"to":{"change":4,"start":3767,"end":4689},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":4,"pos":2158},"to":{"change":4,"start":3767,"end":4689},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":3767},"to":{"change":4,"start":3767,"end":4689},"introduced_by":4}],"inode":{"change":4,"pos":880}}},"contents":[{"Del":"\nmex :: S.Set Int -> Int\nmex s = if 0 `notElem` s then 0 else 1 + mex (S.map (+ (-1)) s)\n\n-- | Compute nimber sum directly from the definition. This is very slow.\nnimberAdd :: Int -> Int -> Int\nnimberAdd = (!!) . (nimberSumTable !!)\n\nnimberSumTable :: [[Int]]\nnimberSumTable = fmap add <$> [(i,) <$> [0 ..] | i <- [0 ..]]\n where\n add (a, b) = mex $ S.fromList [nimberSumTable !! a' !! b | a' <- [0 .. a - 1]] `S.union` S.fromList [nimberSumTable !! a !! b' | b' <- [0 .. b - 1]]\n\n-- | Compute nimber product directly from the definition. This is very slow.\nnimberMul :: Int -> Int -> Int\nnimberMul = (!!) . (nimberProdTable !!)\n\nnimberProdTable :: [[Int]]\nnimberProdTable = fmap mul <$> [(i,) <$> [0 ..] | i <- [0 ..]]\n where\n mul (a, b) = mex $ S.fromList [(nimberProdTable !! a' !! b) `nimberAdd` (nimberProdTable !! a !! b') `nimberAdd` (nimberProdTable !! a' !! b') | a' <- [0 .. a - 1], b' <- [0 .. b - 1]]\n"}]}},{"Edit":{"inode":{"change":4,"pos":4726},"path":"nimbers.cabal","line":72,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":7009},"to":{"change":4,"start":7009,"end":7043},"introduced_by":4}],"inode":{"change":4,"pos":4726}}},"contents":[{"Del":" containers,\n"}]}}],"owner":"noiioiu","repo":"nimbers","token":"pCSAtfLHWYAKNm6p3XBnk2x1dUuo6TZ8wt3C3zonzF4=","login":null}

…

Dependencies

Change contents