ersatz-0.4: A monad for expressing SAT or QSAT problems using observable sharing.

Copyright© Edward Kmett 2010-2015 © Eric Mertens 2014 Johan Kiviniemi 2013
LicenseBSD3
MaintainerEdward Kmett <ekmett@gmail.com>
Stabilityexperimental
Portabilitynon-portable
Safe HaskellNone
LanguageHaskell2010

Ersatz.Bits

Contents

Description

Bits is an arbitrary length natural number type

Synopsis

Fixed length bit vectors

newtype Bit1 #

A container of 1 Bit that encodes from and decodes to Word8

Constructors

Bit1 Bit 

Instances

Num Bit1 # 

Methods

(+) :: Bit1 -> Bit1 -> Bit1 #

(-) :: Bit1 -> Bit1 -> Bit1 #

(*) :: Bit1 -> Bit1 -> Bit1 #

negate :: Bit1 -> Bit1 #

abs :: Bit1 -> Bit1 #

signum :: Bit1 -> Bit1 #

fromInteger :: Integer -> Bit1 #

Show Bit1 # 

Methods

showsPrec :: Int -> Bit1 -> ShowS #

show :: Bit1 -> String #

showList :: [Bit1] -> ShowS #

Generic Bit1 # 

Associated Types

type Rep Bit1 :: * -> * #

Methods

from :: Bit1 -> Rep Bit1 x #

to :: Rep Bit1 x -> Bit1 #

Variable Bit1 # 

Methods

literally :: (HasSAT s, MonadState s m) => m Literal -> m Bit1 #

Codec Bit1 # 

Associated Types

type Decoded Bit1 :: * #

Methods

decode :: MonadPlus f => Solution -> Bit1 -> f (Decoded Bit1) #

encode :: Decoded Bit1 -> Bit1 #

Boolean Bit1 # 

Methods

bool :: Bool -> Bit1 #

true :: Bit1 #

false :: Bit1 #

(&&) :: Bit1 -> Bit1 -> Bit1 #

(||) :: Bit1 -> Bit1 -> Bit1 #

(==>) :: Bit1 -> Bit1 -> Bit1 #

not :: Bit1 -> Bit1 #

and :: Foldable t => t Bit1 -> Bit1 #

or :: Foldable t => t Bit1 -> Bit1 #

nand :: Foldable t => t Bit1 -> Bit1 #

nor :: Foldable t => t Bit1 -> Bit1 #

all :: Foldable t => (a -> Bit1) -> t a -> Bit1 #

any :: Foldable t => (a -> Bit1) -> t a -> Bit1 #

xor :: Bit1 -> Bit1 -> Bit1 #

choose :: Bit1 -> Bit1 -> Bit1 -> Bit1 #

Equatable Bit1 # 

Methods

(===) :: Bit1 -> Bit1 -> Bit #

(/==) :: Bit1 -> Bit1 -> Bit #

Orderable Bit1 # 

Methods

(<?) :: Bit1 -> Bit1 -> Bit #

(<=?) :: Bit1 -> Bit1 -> Bit #

(>=?) :: Bit1 -> Bit1 -> Bit #

(>?) :: Bit1 -> Bit1 -> Bit #

HasBits Bit1 # 

Methods

bits :: Bit1 -> Bits #

type Rep Bit1 # 
type Rep Bit1 = D1 (MetaData "Bit1" "Ersatz.Bits" "ersatz-0.4-Cns5wohkWT3Jqg7jF1lbWM" True) (C1 (MetaCons "Bit1" PrefixI False) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Bit)))
type Decoded Bit1 # 

data Bit2 #

A container of 2 Bits that encodes from and decodes to Word8

Constructors

Bit2 !Bit !Bit 

Instances

Num Bit2 # 

Methods

(+) :: Bit2 -> Bit2 -> Bit2 #

(-) :: Bit2 -> Bit2 -> Bit2 #

(*) :: Bit2 -> Bit2 -> Bit2 #

negate :: Bit2 -> Bit2 #

abs :: Bit2 -> Bit2 #

signum :: Bit2 -> Bit2 #

fromInteger :: Integer -> Bit2 #

Show Bit2 # 

Methods

showsPrec :: Int -> Bit2 -> ShowS #

show :: Bit2 -> String #

showList :: [Bit2] -> ShowS #

Generic Bit2 # 

Associated Types

type Rep Bit2 :: * -> * #

Methods

from :: Bit2 -> Rep Bit2 x #

to :: Rep Bit2 x -> Bit2 #

Variable Bit2 # 

Methods

literally :: (HasSAT s, MonadState s m) => m Literal -> m Bit2 #

Codec Bit2 # 

Associated Types

type Decoded Bit2 :: * #

Methods

decode :: MonadPlus f => Solution -> Bit2 -> f (Decoded Bit2) #

encode :: Decoded Bit2 -> Bit2 #

Boolean Bit2 # 

Methods

bool :: Bool -> Bit2 #

true :: Bit2 #

false :: Bit2 #

(&&) :: Bit2 -> Bit2 -> Bit2 #

(||) :: Bit2 -> Bit2 -> Bit2 #

(==>) :: Bit2 -> Bit2 -> Bit2 #

not :: Bit2 -> Bit2 #

and :: Foldable t => t Bit2 -> Bit2 #

or :: Foldable t => t Bit2 -> Bit2 #

nand :: Foldable t => t Bit2 -> Bit2 #

nor :: Foldable t => t Bit2 -> Bit2 #

all :: Foldable t => (a -> Bit2) -> t a -> Bit2 #

any :: Foldable t => (a -> Bit2) -> t a -> Bit2 #

xor :: Bit2 -> Bit2 -> Bit2 #

choose :: Bit2 -> Bit2 -> Bit2 -> Bit2 #

Equatable Bit2 # 

Methods

(===) :: Bit2 -> Bit2 -> Bit #

(/==) :: Bit2 -> Bit2 -> Bit #

Orderable Bit2 # 

Methods

(<?) :: Bit2 -> Bit2 -> Bit #

(<=?) :: Bit2 -> Bit2 -> Bit #

(>=?) :: Bit2 -> Bit2 -> Bit #

(>?) :: Bit2 -> Bit2 -> Bit #

HasBits Bit2 # 

Methods

bits :: Bit2 -> Bits #

type Rep Bit2 # 
type Decoded Bit2 # 

data Bit3 #

A container of 3 Bits that encodes from and decodes to Word8

Constructors

Bit3 !Bit !Bit !Bit 

Instances

Show Bit3 # 

Methods

showsPrec :: Int -> Bit3 -> ShowS #

show :: Bit3 -> String #

showList :: [Bit3] -> ShowS #

Generic Bit3 # 

Associated Types

type Rep Bit3 :: * -> * #

Methods

from :: Bit3 -> Rep Bit3 x #

to :: Rep Bit3 x -> Bit3 #

Variable Bit3 # 

Methods

literally :: (HasSAT s, MonadState s m) => m Literal -> m Bit3 #

Codec Bit3 # 

Associated Types

type Decoded Bit3 :: * #

Methods

decode :: MonadPlus f => Solution -> Bit3 -> f (Decoded Bit3) #

encode :: Decoded Bit3 -> Bit3 #

Boolean Bit3 # 

Methods

bool :: Bool -> Bit3 #

true :: Bit3 #

false :: Bit3 #

(&&) :: Bit3 -> Bit3 -> Bit3 #

(||) :: Bit3 -> Bit3 -> Bit3 #

(==>) :: Bit3 -> Bit3 -> Bit3 #

not :: Bit3 -> Bit3 #

and :: Foldable t => t Bit3 -> Bit3 #

or :: Foldable t => t Bit3 -> Bit3 #

nand :: Foldable t => t Bit3 -> Bit3 #

nor :: Foldable t => t Bit3 -> Bit3 #

all :: Foldable t => (a -> Bit3) -> t a -> Bit3 #

any :: Foldable t => (a -> Bit3) -> t a -> Bit3 #

xor :: Bit3 -> Bit3 -> Bit3 #

choose :: Bit3 -> Bit3 -> Bit3 -> Bit3 #

Equatable Bit3 # 

Methods

(===) :: Bit3 -> Bit3 -> Bit #

(/==) :: Bit3 -> Bit3 -> Bit #

Orderable Bit3 # 

Methods

(<?) :: Bit3 -> Bit3 -> Bit #

(<=?) :: Bit3 -> Bit3 -> Bit #

(>=?) :: Bit3 -> Bit3 -> Bit #

(>?) :: Bit3 -> Bit3 -> Bit #

HasBits Bit3 # 

Methods

bits :: Bit3 -> Bits #

type Rep Bit3 # 
type Decoded Bit3 # 

data Bit4 #

A container of 4 Bits that encodes from and decodes to Word8

Constructors

Bit4 !Bit !Bit !Bit !Bit 

Instances

Show Bit4 # 

Methods

showsPrec :: Int -> Bit4 -> ShowS #

show :: Bit4 -> String #

showList :: [Bit4] -> ShowS #

Generic Bit4 # 

Associated Types

type Rep Bit4 :: * -> * #

Methods

from :: Bit4 -> Rep Bit4 x #

to :: Rep Bit4 x -> Bit4 #

Variable Bit4 # 

Methods

literally :: (HasSAT s, MonadState s m) => m Literal -> m Bit4 #

Codec Bit4 # 

Associated Types

type Decoded Bit4 :: * #

Methods

decode :: MonadPlus f => Solution -> Bit4 -> f (Decoded Bit4) #

encode :: Decoded Bit4 -> Bit4 #

Boolean Bit4 # 

Methods

bool :: Bool -> Bit4 #

true :: Bit4 #

false :: Bit4 #

(&&) :: Bit4 -> Bit4 -> Bit4 #

(||) :: Bit4 -> Bit4 -> Bit4 #

(==>) :: Bit4 -> Bit4 -> Bit4 #

not :: Bit4 -> Bit4 #

and :: Foldable t => t Bit4 -> Bit4 #

or :: Foldable t => t Bit4 -> Bit4 #

nand :: Foldable t => t Bit4 -> Bit4 #

nor :: Foldable t => t Bit4 -> Bit4 #

all :: Foldable t => (a -> Bit4) -> t a -> Bit4 #

any :: Foldable t => (a -> Bit4) -> t a -> Bit4 #

xor :: Bit4 -> Bit4 -> Bit4 #

choose :: Bit4 -> Bit4 -> Bit4 -> Bit4 #

Equatable Bit4 # 

Methods

(===) :: Bit4 -> Bit4 -> Bit #

(/==) :: Bit4 -> Bit4 -> Bit #

Orderable Bit4 # 

Methods

(<?) :: Bit4 -> Bit4 -> Bit #

(<=?) :: Bit4 -> Bit4 -> Bit #

(>=?) :: Bit4 -> Bit4 -> Bit #

(>?) :: Bit4 -> Bit4 -> Bit #

HasBits Bit4 # 

Methods

bits :: Bit4 -> Bits #

type Rep Bit4 # 
type Decoded Bit4 # 

data Bit5 #

A container of 5 Bits that encodes from and decodes to Word8

Constructors

Bit5 !Bit !Bit !Bit !Bit !Bit 

Instances

Show Bit5 # 

Methods

showsPrec :: Int -> Bit5 -> ShowS #

show :: Bit5 -> String #

showList :: [Bit5] -> ShowS #

Generic Bit5 # 

Associated Types

type Rep Bit5 :: * -> * #

Methods

from :: Bit5 -> Rep Bit5 x #

to :: Rep Bit5 x -> Bit5 #

Variable Bit5 # 

Methods

literally :: (HasSAT s, MonadState s m) => m Literal -> m Bit5 #

Codec Bit5 # 

Associated Types

type Decoded Bit5 :: * #

Methods

decode :: MonadPlus f => Solution -> Bit5 -> f (Decoded Bit5) #

encode :: Decoded Bit5 -> Bit5 #

Boolean Bit5 # 

Methods

bool :: Bool -> Bit5 #

true :: Bit5 #

false :: Bit5 #

(&&) :: Bit5 -> Bit5 -> Bit5 #

(||) :: Bit5 -> Bit5 -> Bit5 #

(==>) :: Bit5 -> Bit5 -> Bit5 #

not :: Bit5 -> Bit5 #

and :: Foldable t => t Bit5 -> Bit5 #

or :: Foldable t => t Bit5 -> Bit5 #

nand :: Foldable t => t Bit5 -> Bit5 #

nor :: Foldable t => t Bit5 -> Bit5 #

all :: Foldable t => (a -> Bit5) -> t a -> Bit5 #

any :: Foldable t => (a -> Bit5) -> t a -> Bit5 #

xor :: Bit5 -> Bit5 -> Bit5 #

choose :: Bit5 -> Bit5 -> Bit5 -> Bit5 #

Equatable Bit5 # 

Methods

(===) :: Bit5 -> Bit5 -> Bit #

(/==) :: Bit5 -> Bit5 -> Bit #

Orderable Bit5 # 

Methods

(<?) :: Bit5 -> Bit5 -> Bit #

(<=?) :: Bit5 -> Bit5 -> Bit #

(>=?) :: Bit5 -> Bit5 -> Bit #

(>?) :: Bit5 -> Bit5 -> Bit #

HasBits Bit5 # 

Methods

bits :: Bit5 -> Bits #

type Rep Bit5 # 
type Decoded Bit5 # 

data Bit6 #

A container of 6 Bits that encodes from and decodes to Word8

Constructors

Bit6 !Bit !Bit !Bit !Bit !Bit !Bit 

Instances

Show Bit6 # 

Methods

showsPrec :: Int -> Bit6 -> ShowS #

show :: Bit6 -> String #

showList :: [Bit6] -> ShowS #

Generic Bit6 # 

Associated Types

type Rep Bit6 :: * -> * #

Methods

from :: Bit6 -> Rep Bit6 x #

to :: Rep Bit6 x -> Bit6 #

Variable Bit6 # 

Methods

literally :: (HasSAT s, MonadState s m) => m Literal -> m Bit6 #

Codec Bit6 # 

Associated Types

type Decoded Bit6 :: * #

Methods

decode :: MonadPlus f => Solution -> Bit6 -> f (Decoded Bit6) #

encode :: Decoded Bit6 -> Bit6 #

Boolean Bit6 # 

Methods

bool :: Bool -> Bit6 #

true :: Bit6 #

false :: Bit6 #

(&&) :: Bit6 -> Bit6 -> Bit6 #

(||) :: Bit6 -> Bit6 -> Bit6 #

(==>) :: Bit6 -> Bit6 -> Bit6 #

not :: Bit6 -> Bit6 #

and :: Foldable t => t Bit6 -> Bit6 #

or :: Foldable t => t Bit6 -> Bit6 #

nand :: Foldable t => t Bit6 -> Bit6 #

nor :: Foldable t => t Bit6 -> Bit6 #

all :: Foldable t => (a -> Bit6) -> t a -> Bit6 #

any :: Foldable t => (a -> Bit6) -> t a -> Bit6 #

xor :: Bit6 -> Bit6 -> Bit6 #

choose :: Bit6 -> Bit6 -> Bit6 -> Bit6 #

Equatable Bit6 # 

Methods

(===) :: Bit6 -> Bit6 -> Bit #

(/==) :: Bit6 -> Bit6 -> Bit #

Orderable Bit6 # 

Methods

(<?) :: Bit6 -> Bit6 -> Bit #

(<=?) :: Bit6 -> Bit6 -> Bit #

(>=?) :: Bit6 -> Bit6 -> Bit #

(>?) :: Bit6 -> Bit6 -> Bit #

HasBits Bit6 # 

Methods

bits :: Bit6 -> Bits #

type Rep Bit6 # 
type Decoded Bit6 # 

data Bit7 #

A container of 7 Bits that encodes from and decodes to Word8

Constructors

Bit7 !Bit !Bit !Bit !Bit !Bit !Bit !Bit 

Instances

Show Bit7 # 

Methods

showsPrec :: Int -> Bit7 -> ShowS #

show :: Bit7 -> String #

showList :: [Bit7] -> ShowS #

Generic Bit7 # 

Associated Types

type Rep Bit7 :: * -> * #

Methods

from :: Bit7 -> Rep Bit7 x #

to :: Rep Bit7 x -> Bit7 #

Variable Bit7 # 

Methods

literally :: (HasSAT s, MonadState s m) => m Literal -> m Bit7 #

Codec Bit7 # 

Associated Types

type Decoded Bit7 :: * #

Methods

decode :: MonadPlus f => Solution -> Bit7 -> f (Decoded Bit7) #

encode :: Decoded Bit7 -> Bit7 #

Boolean Bit7 # 

Methods

bool :: Bool -> Bit7 #

true :: Bit7 #

false :: Bit7 #

(&&) :: Bit7 -> Bit7 -> Bit7 #

(||) :: Bit7 -> Bit7 -> Bit7 #

(==>) :: Bit7 -> Bit7 -> Bit7 #

not :: Bit7 -> Bit7 #

and :: Foldable t => t Bit7 -> Bit7 #

or :: Foldable t => t Bit7 -> Bit7 #

nand :: Foldable t => t Bit7 -> Bit7 #

nor :: Foldable t => t Bit7 -> Bit7 #

all :: Foldable t => (a -> Bit7) -> t a -> Bit7 #

any :: Foldable t => (a -> Bit7) -> t a -> Bit7 #

xor :: Bit7 -> Bit7 -> Bit7 #

choose :: Bit7 -> Bit7 -> Bit7 -> Bit7 #

Equatable Bit7 # 

Methods

(===) :: Bit7 -> Bit7 -> Bit #

(/==) :: Bit7 -> Bit7 -> Bit #

Orderable Bit7 # 

Methods

(<?) :: Bit7 -> Bit7 -> Bit #

(<=?) :: Bit7 -> Bit7 -> Bit #

(>=?) :: Bit7 -> Bit7 -> Bit #

(>?) :: Bit7 -> Bit7 -> Bit #

HasBits Bit7 # 

Methods

bits :: Bit7 -> Bits #

type Rep Bit7 # 
type Decoded Bit7 # 

data Bit8 #

A container of 8 Bits that encodes from and decodes to Word8

Constructors

Bit8 !Bit !Bit !Bit !Bit !Bit !Bit !Bit !Bit 

Instances

Show Bit8 # 

Methods

showsPrec :: Int -> Bit8 -> ShowS #

show :: Bit8 -> String #

showList :: [Bit8] -> ShowS #

Generic Bit8 # 

Associated Types

type Rep Bit8 :: * -> * #

Methods

from :: Bit8 -> Rep Bit8 x #

to :: Rep Bit8 x -> Bit8 #

Variable Bit8 # 

Methods

literally :: (HasSAT s, MonadState s m) => m Literal -> m Bit8 #

Codec Bit8 # 

Associated Types

type Decoded Bit8 :: * #

Methods

decode :: MonadPlus f => Solution -> Bit8 -> f (Decoded Bit8) #

encode :: Decoded Bit8 -> Bit8 #

Boolean Bit8 # 

Methods

bool :: Bool -> Bit8 #

true :: Bit8 #

false :: Bit8 #

(&&) :: Bit8 -> Bit8 -> Bit8 #

(||) :: Bit8 -> Bit8 -> Bit8 #

(==>) :: Bit8 -> Bit8 -> Bit8 #

not :: Bit8 -> Bit8 #

and :: Foldable t => t Bit8 -> Bit8 #

or :: Foldable t => t Bit8 -> Bit8 #

nand :: Foldable t => t Bit8 -> Bit8 #

nor :: Foldable t => t Bit8 -> Bit8 #

all :: Foldable t => (a -> Bit8) -> t a -> Bit8 #

any :: Foldable t => (a -> Bit8) -> t a -> Bit8 #

xor :: Bit8 -> Bit8 -> Bit8 #

choose :: Bit8 -> Bit8 -> Bit8 -> Bit8 #

Equatable Bit8 # 

Methods

(===) :: Bit8 -> Bit8 -> Bit #

(/==) :: Bit8 -> Bit8 -> Bit #

Orderable Bit8 # 

Methods

(<?) :: Bit8 -> Bit8 -> Bit #

(<=?) :: Bit8 -> Bit8 -> Bit #

(>=?) :: Bit8 -> Bit8 -> Bit #

(>?) :: Bit8 -> Bit8 -> Bit #

HasBits Bit8 # 

Methods

bits :: Bit8 -> Bits #

type Rep Bit8 # 
type Decoded Bit8 # 

Variable length bit vectors

newtype Bits #

Constructors

Bits [Bit] 

Instances

Num Bits # 

Methods

(+) :: Bits -> Bits -> Bits #

(-) :: Bits -> Bits -> Bits #

(*) :: Bits -> Bits -> Bits #

negate :: Bits -> Bits #

abs :: Bits -> Bits #

signum :: Bits -> Bits #

fromInteger :: Integer -> Bits #

Show Bits # 

Methods

showsPrec :: Int -> Bits -> ShowS #

show :: Bits -> String #

showList :: [Bits] -> ShowS #

Codec Bits # 

Associated Types

type Decoded Bits :: * #

Methods

decode :: MonadPlus f => Solution -> Bits -> f (Decoded Bits) #

encode :: Decoded Bits -> Bits #

Equatable Bits # 

Methods

(===) :: Bits -> Bits -> Bit #

(/==) :: Bits -> Bits -> Bit #

Orderable Bits # 

Methods

(<?) :: Bits -> Bits -> Bit #

(<=?) :: Bits -> Bits -> Bit #

(>=?) :: Bits -> Bits -> Bit #

(>?) :: Bits -> Bits -> Bit #

HasBits Bits # 

Methods

bits :: Bits -> Bits #

type Decoded Bits # 

class HasBits a where #

HasBits provides the bits method for embedding fixed with numeric encoding types into the arbitrary width Bits type.

Minimal complete definition

bits

Methods

bits :: a -> Bits #

Instances

HasBits Bit # 

Methods

bits :: Bit -> Bits #

HasBits Bits # 

Methods

bits :: Bits -> Bits #

HasBits Bit8 # 

Methods

bits :: Bit8 -> Bits #

HasBits Bit7 # 

Methods

bits :: Bit7 -> Bits #

HasBits Bit6 # 

Methods

bits :: Bit6 -> Bits #

HasBits Bit5 # 

Methods

bits :: Bit5 -> Bits #

HasBits Bit4 # 

Methods

bits :: Bit4 -> Bits #

HasBits Bit3 # 

Methods

bits :: Bit3 -> Bits #

HasBits Bit2 # 

Methods

bits :: Bit2 -> Bits #

HasBits Bit1 # 

Methods

bits :: Bit1 -> Bits #

isEven :: HasBits b => b -> Bit #

Predicate for even-valued Bitss.

isOdd :: HasBits b => b -> Bit #

Predicate for odd-valued Bitss.

sumBit :: Foldable t => t Bit -> Bits #

Optimization of sumBits enabled when summing individual Bits.

sumBits :: (Foldable t, HasBits a) => t a -> Bits #

Compute the sum of a source of Bits values.

Adders

fullAdder #

Arguments

:: Bit 
-> Bit 
-> Bit 
-> (Bit, Bit)

(sum, carry)

Compute the sum and carry bit from adding three bits.

halfAdder #

Arguments

:: Bit 
-> Bit 
-> (Bit, Bit)

(sum, carry)

Compute the sum and carry bit from adding two bits.