{"header":{"message":"Initial commit","description":null,"timestamp":"2024-04-18T04:20:15Z","authors":[{"email":"noiioiu@cocaine.ninja","name":"noiioiu"}]},"hash":"VRPOSMITS7VRSIJU6YNEBELCUBTHPMPJD6F6F5PE35R2KECS42KAC","authors":[],"deps":{"hashes":[["VRPOSMITS7VRSIJU6YNEBELCUBTHPMPJD6F6F5PE35R2KECS42KAC","Initial commit"],["AA",null]],"deps":[],"known":[]},"hunks":[{"AddRoot":{"inode":{"change":1,"pos":0},"atom":{"NewVertex":{"up_context":[{"change":0,"pos":1}],"down_context":[],"flag":"BLOCK | FOLDER","start":2,"end":2,"inode":{"change":1,"pos":0}}},"name":{"NewVertex":{"up_context":[{"change":1,"pos":0}],"down_context":[],"flag":"BLOCK | FOLDER","start":1,"end":1,"inode":{"change":1,"pos":0}}}}},{"FileAdd":{"meta":{"basename":"test","metadata":576},"context":[{"change":0,"pos":2}],"contents":[]}},{"FileAdd":{"meta":{"basename":"Main.hs","metadata":0},"context":[{"change":0,"pos":4}],"contents":[{"Add":"{-# OPTIONS_GHC -Wno-orphans #-}"},{"Add":"module Main (main) where"},{"Add":""},{"Add":"import Nimbers"},{"Add":"import Test.QuickCheck"},{"Add":"import System.Exit (exitFailure)"},{"Add":"import Control.Monad (unless)"},{"Add":""},{"Add":"instance Arbitrary Nimber where"},{"Add":" arbitrary = fromInteger <$> arbitrary"},{"Add":""},{"Add":"prop_neg :: Nimber -> Bool"},{"Add":"prop_neg a = a+a == 0"},{"Add":""},{"Add":"prop_assoc_add :: Nimber -> Nimber -> Nimber -> Bool"},{"Add":"prop_assoc_add a b c = a+(b+c) == (a+b)+c"},{"Add":""},{"Add":"prop_assoc_mul :: Nimber -> Nimber -> Nimber -> Bool"},{"Add":"prop_assoc_mul a b c = a*(b*c) == (a*b)*c"},{"Add":""},{"Add":"prop_distrib :: Nimber -> Nimber -> Nimber -> Bool"},{"Add":"prop_distrib a b c = a*(b+c) == a*b+a*c"},{"Add":""},{"Add":"main :: IO ()"},{"Add":"main = check prop_neg >> check prop_assoc_add >> check prop_assoc_mul >> check prop_distrib"},{"Add":" where check prop = do result <- verboseCheckResult prop"},{"Add":" unless (isSuccess result) exitFailure"}]}},{"FileAdd":{"meta":{"basename":"src","metadata":576},"context":[{"change":0,"pos":2}],"contents":[]}},{"FileAdd":{"meta":{"basename":"Nimbers.hs","metadata":0},"context":[{"change":0,"pos":863}],"contents":[{"Add":"-- | In combinatorial game theory, nimbers represent the values of impartial games. They are the simplest way of making the ordinals into a Field."},{"Add":"-- See /On Numbers and Games/ by John Conway."},{"Add":"--"},{"Add":"-- Nimber addition is defined by \$\\alpha+\\beta = \\operatorname{mex}\\{\\alpha'+\\beta, \\alpha+\\beta'\\}\$."},{"Add":"--"},{"Add":"-- Nimber multiplication is defined by \$\\alpha\\cdot\\beta = \\operatorname{mex}\\{\\alpha'\\cdot\\beta + \\alpha\\cdot\\beta' - \\alpha'\\cdot\\beta'\\}\$."},{"Add":"--"},{"Add":"-- This module implements /finite/ nimbers. The set of finite nimbers is the quadratic closure of the field with two elements."},{"Add":"module Nimbers where"},{"Add":""},{"Add":"import Data.Set qualified as S"},{"Add":""},{"Add":"type Natural = Int"},{"Add":""},{"Add":"-- | 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."},{"Add":"-- 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."},{"Add":"newtype Nimber = Nimber {getNimber :: S.Set (S.Set Natural)}"},{"Add":" deriving (Show, Eq)"},{"Add":""},{"Add":"nimberToNatural :: Nimber -> Natural"},{"Add":"-- nimberToInteger = sum . S.map ((^) @_ @Integer 2 . sum . S.map (2^)) . getNimber"},{"Add":"nimberToNatural = sum . S.map (product . S.map ((^) @_ @Natural 2 . (2 ^))) . getNimber"},{"Add":""},{"Add":"-- | Nimbers are ordinals, so they are ordered. They also form a field, but they are not an ordered field."},{"Add":"instance Ord Nimber where"},{"Add":" n `compare` m = nimberToNatural n `compare` nimberToNatural m"},{"Add":""},{"Add":"instance Enum Nimber where"},{"Add":" toEnum = fromInteger . fromIntegral"},{"Add":" fromEnum = fromIntegral . nimberToNatural"},{"Add":""},{"Add":"twoPowers :: Natural -> S.Set Natural"},{"Add":"twoPowers 0 = S.empty"},{"Add":"twoPowers m ="},{"Add":" if even m"},{"Add":" then S.map (+ 1) $ twoPowers (m `div` 2)"},{"Add":" else S.insert 0 . S.map (+ 1) $ twoPowers (m `div` 2)"},{"Add":""},{"Add":"delta :: (Ord a) => S.Set a -> S.Set a -> S.Set a"},{"Add":"delta x y = (x S.\\\\ y) `S.union` (y S.\\\\ x)"},{"Add":""},{"Add":"instance Num Nimber where"},{"Add":" fromInteger = Nimber . S.map twoPowers . twoPowers . abs . fromIntegral"},{"Add":""},{"Add":" -- \\| Finite nimber addition is calculated as follows: the nimber sum of a two-power and itself is 0, while the nimber sum of two distinct two-powers is their ordinary sum."},{"Add":" Nimber a + Nimber b = Nimber $ (a S.\\\\ b) `S.union` (b S.\\\\ a)"},{"Add":" (-) = (+)"},{"Add":""},{"Add":" -- \\| Finite nimber multiplication is calculated as follows: the nimber square of a Fermat two-power is its sesquimultiple, while the nimber product of two distinct Fermat two-powers is their ordinary product."},{"Add":" a * b"},{"Add":" | a == 1 = b"},{"Add":" | b == 1 = a"},{"Add":" | otherwise = sum $ do"},{"Add":" x <- S.toList $ getNimber a"},{"Add":" y <- S.toList $ getNimber b"},{"Add":" let cs = x `S.intersection` y"},{"Add":" p = product $ S.map (\\c -> Nimber $ S.fromList [S.singleton c, S.fromList [0 .. c - 1]]) cs"},{"Add":" d = Nimber $ S.singleton $ x `delta` y"},{"Add":" -- (*d) . Nimber . S.singleton <$> S.toList (getNimber p)"},{"Add":" pure $ p * d"},{"Add":" negate = id"},{"Add":" abs = id"},{"Add":" signum = id"},{"Add":""},{"Add":"mex :: S.Set Int -> Int"},{"Add":"mex s = if 0 `notElem` s then 0 else 1 + mex (S.map (+ (-1)) s)"},{"Add":""},{"Add":"-- | Compute nimber sum directly from the definition. This is very slow."},{"Add":"nimberAdd :: Int -> Int -> Int"},{"Add":"nimberAdd = (!!) . (nimberSumTable !!)"},{"Add":""},{"Add":"nimberSumTable :: [[Int]]"},{"Add":"nimberSumTable = fmap add <$> [(i,) <$> [0 ..] | i <- [0 ..]]"},{"Add":" where"},{"Add":" add (a, b) = mex $ S.fromList [nimberSumTable !! a' !! b | a' <- [0 .. a - 1]] `S.union` S.fromList [nimberSumTable !! a !! b' | b' <- [0 .. b - 1]]"},{"Add":""},{"Add":"-- | Compute nimber product directly from the definition. This is very slow."},{"Add":"nimberMul :: Int -> Int -> Int"},{"Add":"nimberMul = (!!) . (nimberProdTable !!)"},{"Add":""},{"Add":"nimberProdTable :: [[Int]]"},{"Add":"nimberProdTable = fmap mul <$> [(i,) <$> [0 ..] | i <- [0 ..]]"},{"Add":" where"},{"Add":" 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]]"}]}},{"FileAdd":{"meta":{"basename":"nimbers.cabal","metadata":0},"context":[{"change":0,"pos":2}],"contents":[{"Add":"cabal-version: 3.4"},{"Add":"-- The cabal-version field refers to the version of the .cabal specification,"},{"Add":"-- and can be different from the cabal-install (the tool) version and the"},{"Add":"-- Cabal (the library) version you are using. As such, the Cabal (the library)"},{"Add":"-- version used must be equal or greater than the version stated in this field."},{"Add":"-- Starting from the specification version 2.2, the cabal-version field must be"},{"Add":"-- the first thing in the cabal file."},{"Add":""},{"Add":"-- Initial package description 'nimbers' generated by"},{"Add":"-- 'cabal init'. For further documentation, see:"},{"Add":"-- http://haskell.org/cabal/users-guide/"},{"Add":"--"},{"Add":"-- The name of the package."},{"Add":"name: nimbers"},{"Add":""},{"Add":"-- The package version."},{"Add":"-- See the Haskell package versioning policy (PVP) for standards"},{"Add":"-- guiding when and how versions should be incremented."},{"Add":"-- https://pvp.haskell.org"},{"Add":"-- PVP summary: +-+------- breaking API changes"},{"Add":"-- | | +----- non-breaking API additions"},{"Add":"-- | | | +--- code changes with no API change"},{"Add":"version: 0.1.0.0"},{"Add":""},{"Add":"-- A short (one-line) description of the package."},{"Add":"synopsis: finite nimbers"},{"Add":""},{"Add":"-- A longer description of the package."},{"Add":"-- description:"},{"Add":""},{"Add":"-- The license under which the package is released."},{"Add":"license: ISC"},{"Add":""},{"Add":"-- The file containing the license text."},{"Add":"license-file: LICENSE"},{"Add":""},{"Add":"-- The package author(s)."},{"Add":"author: noiioiu"},{"Add":""},{"Add":"-- An email address to which users can send suggestions, bug reports, and patches."},{"Add":"maintainer: noiioiu@"},{"Add":""},{"Add":"-- A copyright notice."},{"Add":"-- copyright:"},{"Add":"category: Math"},{"Add":"build-type: Simple"},{"Add":""},{"Add":"-- Extra doc files to be distributed with the package, such as a CHANGELOG or a README."},{"Add":"extra-doc-files: CHANGELOG.md"},{"Add":""},{"Add":"-- Extra source files to be distributed with the package, such as examples, or a tutorial module."},{"Add":"-- extra-source-files:"},{"Add":""},{"Add":"common warnings"},{"Add":" ghc-options: -Wall"},{"Add":""},{"Add":"library"},{"Add":" -- Import common warning flags."},{"Add":" import: warnings"},{"Add":""},{"Add":" -- Modules exported by the library."},{"Add":" exposed-modules: Nimbers"},{"Add":""},{"Add":" -- Modules included in this library but not exported."},{"Add":" -- other-modules:"},{"Add":""},{"Add":" -- LANGUAGE extensions used by modules in this package."},{"Add":" -- other-extensions:"},{"Add":""},{"Add":" -- Other library packages from which modules are imported."},{"Add":" build-depends: base >=4.16.4.0,"},{"Add":" containers,"},{"Add":""},{"Add":" -- Directories containing source files."},{"Add":" hs-source-dirs: src"},{"Add":""},{"Add":" -- Base language which the package is written in."},{"Add":" default-language: GHC2021"},{"Add":""},{"Add":"test-suite nimbers-test"},{"Add":" -- Import common warning flags."},{"Add":" import: warnings"},{"Add":""},{"Add":" -- Base language which the package is written in."},{"Add":" default-language: GHC2021"},{"Add":""},{"Add":" -- Modules included in this executable, other than Main."},{"Add":" -- other-modules:"},{"Add":""},{"Add":" -- LANGUAGE extensions used by modules in this package."},{"Add":" -- other-extensions:"},{"Add":""},{"Add":" -- The interface type and version of the test suite."},{"Add":" type: exitcode-stdio-1.0"},{"Add":""},{"Add":" -- Directories containing source files."},{"Add":" hs-source-dirs: test"},{"Add":""},{"Add":" -- The entrypoint to the test suite."},{"Add":" main-is: Main.hs"},{"Add":""},{"Add":" -- Test dependencies."},{"Add":" build-depends:"},{"Add":" base >=4.16.4.0,"},{"Add":" QuickCheck,"},{"Add":" nimbers"}]}},{"FileAdd":{"meta":{"basename":"LICENSE","metadata":0},"context":[{"change":0,"pos":2}],"contents":[{"Add":"Copyright (c) 2024 noiioiu"},{"Add":""},{"Add":"Permission to use, copy, modify, and/or distribute this software for any purpose"},{"Add":"with or without fee is hereby granted, provided that the above copyright notice"},{"Add":"and this permission notice appear in all copies."},{"Add":""},{"Add":"THE SOFTWARE IS PROVIDED \"AS IS\" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH"},{"Add":"REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND"},{"Add":"FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,"},{"Add":"INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS"},{"Add":"OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER"},{"Add":"TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF"},{"Add":"THIS SOFTWARE."}]}},{"FileAdd":{"meta":{"basename":"CHANGELOG.md","metadata":0},"context":[{"change":0,"pos":2}],"contents":[{"Add":"# Revision history for nimbers"},{"Add":""},{"Add":"## 0.1.0.0 -- YYYY-mm-dd"},{"Add":""},{"Add":"* First version. Released on an unsuspecting world."}]}}],"owner":"noiioiu","repo":"nimbers","token":"f2RIe4nKwHkP3kEUV0amgRfMKTd3XVID5N5koXxO804=","login":null}

…

Dependencies

Change contents