module NatGames where
import Data.Maybe
import Iso
import Games
import BasicGames
type Pos = Int
power2 0 = 1
power2 (n+1) = 2 * power2 n
log2 1 = 0
log2 n = 1 + log2 (n `div` 2)
binaryIso :: ISO Pos (Nat,Pos)
binaryIso = Iso (\p -> (log2 p, p)) snd
eliasGame :: Game Nat -> Game Pos
eliasGame natGame = depGame natGame (\n -> let m = power2 n in rangeGame m (2*m 1)) +> binaryIso
gammaGame = eliasGame unaryNatGame
isOneIso :: ISO Pos (Either () Pos)
isOneIso = Iso ask bld
where ask 1 = Left ()
ask n = Right n
bld (Left ()) = 1
bld (Right n) = n
omegaGame = Split isOneIso unitGame (eliasGame omegaGame)
primes = sieve [2..]
where
sieve (p:xs) = p : sieve [x | x<-xs, x `mod` p /= 0]
factIso :: [Int] -> ISO Int (Either Int Int)
factIso (p:ps) =
Iso (\n -> let (d,r) = divMod n p in if r==0 then Left d else Right n)
(\z -> case z of Left d -> d*p; Right n -> n)
factPosGame ps = Split isOneIso unitGame (factPosNotOneGame ps)
factPosNotOneGame (p:ps) = Split (factIso (p:ps)) (factPosGame (p:ps)) (factPosNotOneGame ps)
factGame :: Game Pos
factGame = factPosGame primes