Safe Haskell	Safe
Language	Haskell2010

Data.Bin

Contents

Binary natural numbers
Positive natural numbers
Showing
Extras
- Data.Bits
Aliases

Description

Binary natural numbers, Bin.

This module is designed to be imported qualified.

Synopsis

data Bin
- = BZ
- | BP BinP
toNatural :: Bin -> Natural
fromNatural :: Natural -> Bin
toNat :: Bin -> Nat
fromNat :: Nat -> Bin
cata :: a -> a -> (a -> a) -> (a -> a) -> Bin -> a
data BinP
- = BE
- | B0 BinP
- | B1 BinP
explicitShow :: Bin -> String
explicitShowsPrec :: Int -> Bin -> ShowS
predP :: BinP -> Bin
mult2 :: Bin -> Bin
mult2Plus1 :: Bin -> BinP
andP :: BinP -> BinP -> Bin
xorP :: BinP -> BinP -> Bin
complementBitP :: BinP -> Int -> Bin
clearBitP :: BinP -> Int -> Bin
bin0 :: Bin
bin1 :: Bin
bin2 :: Bin
bin3 :: Bin
bin4 :: Bin
bin5 :: Bin
bin6 :: Bin
bin7 :: Bin
bin8 :: Bin
bin9 :: Bin

Binary natural numbers

data Bin Source #

Binary natural numbers.

Numbers are represented in little-endian order, the representation is unique.

>>> mapM_ (putStrLn .  explicitShow) [0 .. 7]
BZ
BP BE
BP (B0 BE)
BP (B1 BE)
BP (B0 (B0 BE))
BP (B1 (B0 BE))
BP (B0 (B1 BE))
BP (B1 (B1 BE))

Constructors

BZ	zero
BP BinP	non-zero

Instances

Instances details

Enum Bin Source #	`>>>` `take 10 $ iterate succ BZ`[0,1,2,3,4,5,6,7,8,9] `>>>` `take 10 [BZ ..]`[0,1,2,3,4,5,6,7,8,9]
Instance details Defined in Data.Bin Methods succ :: Bin -> Bin # pred :: Bin -> Bin # toEnum :: Int -> Bin # fromEnum :: Bin -> Int # enumFrom :: Bin -> [Bin] # enumFromThen :: Bin -> Bin -> [Bin] # enumFromTo :: Bin -> Bin -> [Bin] # enumFromThenTo :: Bin -> Bin -> Bin -> [Bin] #
Eq Bin Source #
Instance details Defined in Data.Bin Methods (==) :: Bin -> Bin -> Bool # (/=) :: Bin -> Bin -> Bool #
Integral Bin Source #
Instance details Defined in Data.Bin Methods quot :: Bin -> Bin -> Bin # rem :: Bin -> Bin -> Bin # div :: Bin -> Bin -> Bin # mod :: Bin -> Bin -> Bin # quotRem :: Bin -> Bin -> (Bin, Bin) # divMod :: Bin -> Bin -> (Bin, Bin) # toInteger :: Bin -> Integer #
Data Bin Source #
Instance details Defined in Data.Bin Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Bin -> c Bin # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Bin # toConstr :: Bin -> Constr # dataTypeOf :: Bin -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c Bin) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Bin) # gmapT :: (forall b. Data b => b -> b) -> Bin -> Bin # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Bin -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Bin -> r # gmapQ :: (forall d. Data d => d -> u) -> Bin -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Bin -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Bin -> m Bin # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Bin -> m Bin # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Bin -> m Bin #
Num Bin Source #	`>>>` `0 + 2 :: Bin`2 `>>>` `1 + 2 :: Bin`3 `>>>` *`4 8 :: Bin`32 `>>>` `7 * 7 :: Bin`**49
Instance details Defined in Data.Bin Methods (+) :: Bin -> Bin -> Bin # (-) :: Bin -> Bin -> Bin # (*) :: Bin -> Bin -> Bin # negate :: Bin -> Bin # abs :: Bin -> Bin # signum :: Bin -> Bin # fromInteger :: Integer -> Bin #
Ord Bin Source #
Instance details Defined in Data.Bin Methods compare :: Bin -> Bin -> Ordering # (<) :: Bin -> Bin -> Bool # (<=) :: Bin -> Bin -> Bool # (>) :: Bin -> Bin -> Bool # (>=) :: Bin -> Bin -> Bool # max :: Bin -> Bin -> Bin # min :: Bin -> Bin -> Bin #
Real Bin Source #
Instance details Defined in Data.Bin Methods toRational :: Bin -> Rational #
Show Bin Source #	`Bin` is printed as `Natural`. To see explicit structure, use `explicitShow` or `explicitShowsPrec`
Instance details Defined in Data.Bin Methods showsPrec :: Int -> Bin -> ShowS # show :: Bin -> String # showList :: [Bin] -> ShowS #
Function Bin Source #
Instance details Defined in Data.Bin Methods function :: (Bin -> b) -> Bin :-> b #
Arbitrary Bin Source #
Instance details Defined in Data.Bin Methods arbitrary :: Gen Bin # shrink :: Bin -> [Bin] #
CoArbitrary Bin Source #
Instance details Defined in Data.Bin Methods coarbitrary :: Bin -> Gen b -> Gen b #
Bits Bin Source #
Instance details Defined in Data.Bin Methods (.&.) :: Bin -> Bin -> Bin # (.\|.) :: Bin -> Bin -> Bin # xor :: Bin -> Bin -> Bin # complement :: Bin -> Bin # shift :: Bin -> Int -> Bin # rotate :: Bin -> Int -> Bin # zeroBits :: Bin # bit :: Int -> Bin # setBit :: Bin -> Int -> Bin # clearBit :: Bin -> Int -> Bin # complementBit :: Bin -> Int -> Bin # testBit :: Bin -> Int -> Bool # bitSizeMaybe :: Bin -> Maybe Int # bitSize :: Bin -> Int # isSigned :: Bin -> Bool # shiftL :: Bin -> Int -> Bin # unsafeShiftL :: Bin -> Int -> Bin # shiftR :: Bin -> Int -> Bin # unsafeShiftR :: Bin -> Int -> Bin # rotateL :: Bin -> Int -> Bin # rotateR :: Bin -> Int -> Bin # popCount :: Bin -> Int #
NFData Bin Source #
Instance details Defined in Data.Bin Methods rnf :: Bin -> () #
Hashable Bin Source #
Instance details Defined in Data.Bin Methods hashWithSalt :: Int -> Bin -> Int # hash :: Bin -> Int #
TestEquality SBin Source #
Instance details Defined in Data.Type.Bin Methods testEquality :: forall (a :: k) (b :: k). SBin a -> SBin b -> Maybe (a :~: b) #

toNatural :: Bin -> Natural Source #

Convert Bin to Natural

>>> toNatural 0
0

>>> toNatural 2
2

>>> toNatural $ BP $ B0 $ B1 $ BE
6

fromNatural :: Natural -> Bin Source #

Convert Natural to Nat

>>> fromNatural 4
4

>>> explicitShow (fromNatural 4)
"BP (B0 (B0 BE))"

toNat :: Bin -> Nat Source #

Convert from Bin to Nat.

>>> toNat 5
5

>>> N.explicitShow (toNat 5)
"S (S (S (S (S Z))))"

fromNat :: Nat -> Bin Source #

Convert from Nat to Bin.

>>> fromNat 5
5

>>> explicitShow (fromNat 5)
"BP (B1 (B0 BE))"

cata Source #

Arguments

:: a	$0$
-> a	$1$
-> (a -> a)	$2x$
-> (a -> a)	$2x + 1$
-> Bin
-> a

Fold Bin.

Positive natural numbers

data BinP Source #

Non-zero binary natural numbers.

We could have called this type Bin1, but that's used as type alias for promoted BP BE in Data.Type.Bin.

Constructors

BE	one
B0 BinP	mult2
B1 BinP	mult2 plus 1

Instances

Instances details

Enum BinP Source #
Instance details Defined in Data.BinP Methods succ :: BinP -> BinP # pred :: BinP -> BinP # toEnum :: Int -> BinP # fromEnum :: BinP -> Int # enumFrom :: BinP -> [BinP] # enumFromThen :: BinP -> BinP -> [BinP] # enumFromTo :: BinP -> BinP -> [BinP] # enumFromThenTo :: BinP -> BinP -> BinP -> [BinP] #
Eq BinP Source #
Instance details Defined in Data.BinP Methods (==) :: BinP -> BinP -> Bool # (/=) :: BinP -> BinP -> Bool #
Integral BinP Source #
Instance details Defined in Data.BinP Methods quot :: BinP -> BinP -> BinP # rem :: BinP -> BinP -> BinP # div :: BinP -> BinP -> BinP # mod :: BinP -> BinP -> BinP # quotRem :: BinP -> BinP -> (BinP, BinP) # divMod :: BinP -> BinP -> (BinP, BinP) # toInteger :: BinP -> Integer #
Data BinP Source #
Instance details Defined in Data.BinP Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> BinP -> c BinP # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c BinP # toConstr :: BinP -> Constr # dataTypeOf :: BinP -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c BinP) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c BinP) # gmapT :: (forall b. Data b => b -> b) -> BinP -> BinP # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> BinP -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> BinP -> r # gmapQ :: (forall d. Data d => d -> u) -> BinP -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> BinP -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> BinP -> m BinP # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> BinP -> m BinP # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> BinP -> m BinP #
Num BinP Source #
Instance details Defined in Data.BinP Methods (+) :: BinP -> BinP -> BinP # (-) :: BinP -> BinP -> BinP # (*) :: BinP -> BinP -> BinP # negate :: BinP -> BinP # abs :: BinP -> BinP # signum :: BinP -> BinP # fromInteger :: Integer -> BinP #
Ord BinP Source #	`>>>` `sort [ 1 .. 9 :: BinP ]`[1,2,3,4,5,6,7,8,9] `>>>` `sort $ reverse [ 1 .. 9 :: BinP ]`[1,2,3,4,5,6,7,8,9] `>>>` `sort $ [ 1 .. 9 ] ++ [ 1 .. 9 :: BinP ]`[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9]
Instance details Defined in Data.BinP Methods compare :: BinP -> BinP -> Ordering # (<) :: BinP -> BinP -> Bool # (<=) :: BinP -> BinP -> Bool # (>) :: BinP -> BinP -> Bool # (>=) :: BinP -> BinP -> Bool # max :: BinP -> BinP -> BinP # min :: BinP -> BinP -> BinP #
Real BinP Source #
Instance details Defined in Data.BinP Methods toRational :: BinP -> Rational #
Show BinP Source #
Instance details Defined in Data.BinP Methods showsPrec :: Int -> BinP -> ShowS # show :: BinP -> String # showList :: [BinP] -> ShowS #
Function BinP Source #
Instance details Defined in Data.BinP Methods function :: (BinP -> b) -> BinP :-> b #
Arbitrary BinP Source #
Instance details Defined in Data.BinP Methods arbitrary :: Gen BinP # shrink :: BinP -> [BinP] #
CoArbitrary BinP Source #
Instance details Defined in Data.BinP Methods coarbitrary :: BinP -> Gen b -> Gen b #
Bits BinP Source #	NOTE: `.&.`, `xor`, `shiftR` and `rotateR` are __NOT_ implemented. They may make number zero.
Instance details Defined in Data.BinP Methods (.&.) :: BinP -> BinP -> BinP # (.\|.) :: BinP -> BinP -> BinP # xor :: BinP -> BinP -> BinP # complement :: BinP -> BinP # shift :: BinP -> Int -> BinP # rotate :: BinP -> Int -> BinP # zeroBits :: BinP # bit :: Int -> BinP # setBit :: BinP -> Int -> BinP # clearBit :: BinP -> Int -> BinP # complementBit :: BinP -> Int -> BinP # testBit :: BinP -> Int -> Bool # bitSizeMaybe :: BinP -> Maybe Int # bitSize :: BinP -> Int # isSigned :: BinP -> Bool # shiftL :: BinP -> Int -> BinP # unsafeShiftL :: BinP -> Int -> BinP # shiftR :: BinP -> Int -> BinP # unsafeShiftR :: BinP -> Int -> BinP # rotateL :: BinP -> Int -> BinP # rotateR :: BinP -> Int -> BinP # popCount :: BinP -> Int #
NFData BinP Source #
Instance details Defined in Data.BinP Methods rnf :: BinP -> () #
Hashable BinP Source #
Instance details Defined in Data.BinP Methods hashWithSalt :: Int -> BinP -> Int # hash :: BinP -> Int #
TestEquality SBinP Source #
Instance details Defined in Data.Type.BinP Methods testEquality :: forall (a :: k) (b :: k). SBinP a -> SBinP b -> Maybe (a :~: b) #

Showing

explicitShow :: Bin -> String Source #

show displaying a structure of Bin.

>>> explicitShow 0
"BZ"

>>> explicitShow 2
"BP (B0 BE)"

explicitShowsPrec :: Int -> Bin -> ShowS Source #

showsPrec displaying a structure of Bin.

Extras

predP :: BinP -> Bin Source #

This is a total function.

>>> map predP [1..10]
[0,1,2,3,4,5,6,7,8,9]

mult2 :: Bin -> Bin Source #

mult2Plus1 :: Bin -> BinP Source #

Data.Bits

andP :: BinP -> BinP -> Bin Source #

xorP :: BinP -> BinP -> Bin Source #

complementBitP :: BinP -> Int -> Bin Source #

clearBitP :: BinP -> Int -> Bin Source #

Aliases

bin0 :: Bin Source #

bin1 :: Bin Source #

bin2 :: Bin Source #

bin3 :: Bin Source #

bin4 :: Bin Source #

bin5 :: Bin Source #

bin6 :: Bin Source #

bin7 :: Bin Source #

bin8 :: Bin Source #

bin9 :: Bin Source #

:: a	\(0\)
-> a	\(1\)
-> (a -> a)	\(2x\)
-> (a -> a)	\(2x + 1\)
-> Bin
-> a