Module Data.Bits

Fast sets for small integers and enumerations, implemented as bit operations on Long There may be at most 64 elements, due to the bit size of Long.

Imports

• import Data.Monoid as Monoid
• import frege.Prelude as Prelude
• import Prelude.PreludeArrays as PreludeArrays
• import Prelude.PreludeBase as PreludeBase
• import Prelude.PreludeDecimal as PreludeDecimal
• import Prelude.PreludeIO as PreludeIO
• import Prelude.PreludeList as PreludeList
• import Prelude.PreludeMonad as PreludeMonad
• import Prelude.PreludeText as PreludeText
• import Java.util.Regex as Regexp

Table of Content

• Definitions

  class (Eq a, Ord a, Num a) ⇒ Bits a

  data BitSet e

• Instances

  instance Bits Int

  instance Bits Integer

  instance Bits Long

  instance Eq (BitSet a)

  instance ListEmpty BitSet

  instance Monoid (BitSet a)

  instance Ord (BitSet a)

  instance (Show a, Enum a) ⇒ Show (BitSet a)

• Functions and Values by Type

Definitions

data BitSet e

Constructors

BitSet {set ∷ Long}

Member Functions

difference ∷ BitSet α → BitSet α → BitSet α

a `difference` b -- a set with all elements that are members of a and not members of b

differenceE ∷ Enum 𝖆 ⇒ BitSet 𝖆 → 𝖆 → BitSet 𝖆

a `differenceE` e = a `difference` {e}

fromList ∷ Enum 𝖆 ⇒ [𝖆] → BitSet 𝖆

convert a list to a BitSet

intersection ∷ BitSet α → BitSet α → BitSet α

a `intersection` b -- a set with all elements that are members of a and members of b

intersectionE ∷ Enum 𝖆 ⇒ BitSet 𝖆 → 𝖆 → BitSet 𝖆

a `intersectionE` e = a `intersection` {e}

member ∷ Enum α ⇒ α → BitSet α → Bool

Predicate to tell if an element is a member of a set

set ∷ BitSet 𝖆 → Long

access field set

singleton ∷ Enum α ⇒ α → BitSet α

A set with one argument

size ∷ BitSet 𝖆 → Int

tell the number of elements in a BitSet

subset ∷ BitSet α → BitSet α → Bool

Predicate that tells if one set is a subset of another

toList ∷ Enum α ⇒ BitSet α → [α]

convert a BitSet to a list

union ∷ BitSet α → BitSet α → BitSet α

a `union` b -- a set with all elements that are members of a or members of b

unionE ∷ Enum 𝖆 ⇒ BitSet 𝖆 → 𝖆 → BitSet 𝖆

a `unionE` e = a `union` {e}

universal ∷ (Enum α, Bounded α) ⇒ BitSet α

The universal set

class (Eq a, Ord a, Num a) ⇒ Bits a

The Bits class defines bitwise operations over integral types.

Bits are numbered from 0 with bit 0 being the least significant bit.

Minimal complete definition: .&., .|., .^., Bits.complement, (Bits.shift or (Bits.shiftL and Bits.shiftR)), (Bits.rotate or (Bits.rotateL and Bits.rotateR)), Bits.bitSize and Bits.isSigned.

Known Instances

Integer, Int, Long

Member Functions

.&. ∷ Bits a ⇒ a → a → a
infixl  11

Bitwise \"and\"

.^. ∷ Bits a ⇒ a → a → a
infixl  10

Bitwise \"xor\"

.|. ∷ Bits a ⇒ a → a → a
infixl  10

Bitwise \"or\"

bit ∷ Bits a ⇒ Int → a

bit i is a value with the ith bit set

bitCount ∷ Bits a ⇒ a → Int

Returns the number of one-bits in the two's complement binary representation of the specified value.

Also known as "population count" or "Hamming Weight" of a bit string.

See also Hamming Weight.

bitSize ∷ Bits a ⇒ a → Int

Return the number of bits in the type of the argument. The actual value of the argument is ignored. The function Bits.bitSize is undefined for types that do not have a fixed bitsize, like Integer.

clearBit ∷ Bits a ⇒ a → Int → a

x \`clearBit\` i is the same as x .&. complement (bit i)

complement ∷ Bits a ⇒ a → a

Reverse all the bits in the argument

complementBit ∷ Bits a ⇒ a → Int → a

x \`complementBit\` i is the same as x \`.^.\` bit i

isSigned ∷ Bits a ⇒ a → Bool

Return true if the argument is a signed type. The actual value of the argument is ignored

rotate ∷ Bits a ⇒ a → Int → a
infixl  12

Bits.rotate x i rotates x left by i bits if i is positive, or right by -i bits otherwise.

For unbounded types like Integer, Bits.rotate is equivalent to Bits.shift.

An instance can define either this unified Bits.rotate or Bits.rotateL and Bits.rotateR, depending on which is more convenient for the type in question.

rotateL ∷ Bits a ⇒ a → Int → a
infixl  12

Rotate the argument left by the specified number of bits (which must be non-negative).

An instance can define either this and Bits.rotateR or the unified Bits.rotate, depending on which is more convenient for the type in question.

rotateR ∷ Bits a ⇒ a → Int → a
infixl  12

Rotate the argument right by the specified number of bits (which must be non-negative).

An instance can define either this and Bits.rotateL or the unified Bits.rotate, depending on which is more convenient for the type in question.

setBit ∷ Bits a ⇒ a → Int → a

x \`setBit\` i is the same as x .|. bit i

shift ∷ Bits a ⇒ a → Int → a
infixl  12

Bits.shift x i shifts x left by i bits if i is positive, or right by -i bits otherwise. Right shifts perform sign extension on signed number types; i.e. they fill the top bits with 1 if the x is negative and with 0 otherwise.

An instance can define either this unified Bits.shift or Bits.shiftL and Bits.shiftR, depending on which is more convenient for the type in question.

shiftL ∷ Bits a ⇒ a → Int → a
infixl  12

Shift the argument left by the specified number of bits (which must be non-negative).

An instance can define either this and Bits.shiftR or the unified Bits.shift, depending on which is more convenient for the type in question.

shiftR ∷ Bits a ⇒ a → Int → a
infixl  12

Shift the first argument right by the specified number of bits (which must be non-negative). Right shifts perform sign extension on signed number types; i.e. they fill the top bits with 1 if the x is negative and with 0 otherwise.

An instance can define either this and Bits.shiftL or the unified Bits.shift, depending on which is more convenient for the type in question.

testBit ∷ Bits a ⇒ a → Int → Bool

Return true if the nth bit of the argument is 1

ushiftR ∷ Bits a ⇒ a → Int → a
infixl  12

Unsigned shift right

xor ∷ Bits a ⇒ a → a → a
infixl  10

Haskell compatibility. Same as `.^.`

Instances

instance Bits Int

Member Functions

.&. ∷ Int → Int → Int
pure native &
infixl  11

Computes binary /and/ of two integers. Uses the java &-operator.

.^. ∷ Int → Int → Int
pure native ^
infixl  10

Computes binary /exclusive or/ of two integers. Uses the java ^-operator.

.|. ∷ Int → Int → Int
pure native |
infixl  10

Computes binary /or/ of two integers. Uses the java |-operator.

bit ∷ Int → Int

inherited from Bits.bit

bitCount ∷ Int → Int
pure native java.lang.Integer.bitCount

bitSize ∷ Int → Int

clearBit ∷ Int → Int → Int

inherited from Bits.clearBit

complement ∷ Int → Int
pure native ~

complementBit ∷ Int → Int → Int

inherited from Bits.complementBit

isSigned ∷ Int → Bool

rotate ∷ Int → Int → Int
infixl  12

inherited from Bits.rotate

rotateL ∷ Int → Int → Int
pure native java.lang.Integer.rotateLeft
infixl  12

Returns the value obtained by rotating the two's complement binary representation of the specified int value left

by the specified number of bits.

rotateR ∷ Int → Int → Int
pure native java.lang.Integer.rotateRight
infixl  12

Returns the value obtained by rotating the two's complement binary representation of the specified int value

right by the specified number of bits.

setBit ∷ Int → Int → Int

inherited from Bits.setBit

shift ∷ Int → Int → Int
infixl  12

inherited from Bits.shift

shiftL ∷ Int → Int → Int
pure native <<
infixl  12

shiftR ∷ Int → Int → Int
pure native >>
infixl  12

testBit ∷ Int → Int → Bool

inherited from Bits.testBit

ushiftR ∷ Int → Int → Int
pure native >>>
infixl  12

unsigned right shift

xor ∷ Int → Int → Int
infixl  10

inherited from Bits.xor

instance Bits Integer

Member Functions

.&. ∷ Integer → Integer → Integer
pure native and
infixl  11

.^. ∷ Integer → Integer → Integer
pure native xor
infixl  10

.|. ∷ Integer → Integer → Integer
pure native or
infixl  10

bit ∷ Int → Integer

inherited from Bits.bit

bitCount ∷ Integer → Int
pure native bitCount

Returns the number of bits in the two's complement representation of this Integer that differ from its sign bit.

Note that this is slightly different from data types with a fixed bit size!

Best to be used after masking a certain number of bits with some all-1-bit pattern.

bitSize ∷ Integer → Int

Returns the number of bits in the minimal two's-complement representation of this Integer, excluding a sign bit.

clearBit ∷ Integer → Int → Integer

inherited from Bits.clearBit

complement ∷ Integer → Integer
pure native not

complementBit ∷ Integer → Int → Integer

inherited from Bits.complementBit

isSigned ∷ Integer → Bool

rotate ∷ Integer → Int → Integer
infixl  12

rotateL ∷ Integer → Int → Integer
infixl  12

inherited from Bits.rotateL

rotateR ∷ Integer → Int → Integer
infixl  12

inherited from Bits.rotateR

setBit ∷ Integer → Int → Integer

inherited from Bits.setBit

shift ∷ Integer → Int → Integer
infixl  12

inherited from Bits.shift

shiftL ∷ Integer → Int → Integer
pure native shiftLeft
infixl  12

shiftR ∷ Integer → Int → Integer
pure native shiftRight
infixl  12

testBit ∷ Integer → Int → Bool

inherited from Bits.testBit

ushiftR ∷ Integer → Int → Integer
infixl  12

unsigned right shift on big integers does not really make sense ...

xor ∷ Integer → Integer → Integer
infixl  10

inherited from Bits.xor

instance Bits Long

Member Functions

.&. ∷ Long → Long → Long
pure native &
infixl  11

Computes binary and of two integers. Uses the java &-operator.

.^. ∷ Long → Long → Long
pure native ^
infixl  10

Computes binary exclusive or of two long integers. Uses the java ^-operator.

.|. ∷ Long → Long → Long
pure native |
infixl  10

Computes binary or of two long integers. Uses the java |-operator.

bit ∷ Int → Long

inherited from Bits.bit

bitCount ∷ Long → Int
pure native java.lang.Long.bitCount

bitSize ∷ Long → Int

clearBit ∷ Long → Int → Long

inherited from Bits.clearBit

complement ∷ Long → Long
pure native ~

complementBit ∷ Long → Int → Long

inherited from Bits.complementBit

isSigned ∷ Long → Bool

rotate ∷ Long → Int → Long
infixl  12

inherited from Bits.rotate

rotateL ∷ Long → Int → Long
pure native java.lang.Long.rotateLeft
infixl  12

Returns the value obtained by rotating the two's complement binary representation

of the specified long value left by the specified number of bits.

rotateR ∷ Long → Int → Long
pure native java.lang.Long.rotateRight
infixl  12

Returns the value obtained by rotating the two's complement binary representation

of the specified long value right by the specified number of bits.

setBit ∷ Long → Int → Long

inherited from Bits.setBit

shift ∷ Long → Int → Long
infixl  12

inherited from Bits.shift

shiftL ∷ Long → Int → Long
pure native <<
infixl  12

shiftR ∷ Long → Int → Long
pure native >>
infixl  12

testBit ∷ Long → Int → Bool

inherited from Bits.testBit

ushiftR ∷ Long → Int → Long
pure native >>>
infixl  12

unsigned right shift

xor ∷ Long → Long → Long
infixl  10

inherited from Bits.xor

instance Eq (BitSet a)

Member Functions

!= ∷ BitSet 𝖆 → BitSet 𝖆 → Bool
infix  7

inherited from Eq.!=

== ∷ BitSet 𝖆 → BitSet 𝖆 → Bool
infix  7

hashCode ∷ BitSet 𝖆 → Int

instance ListEmpty BitSet

Member Functions

empty ∷ BitSet 𝖆

The empty set

null ∷ BitSet 𝖆 → Bool

Predicate to tell if the set is empty

instance Monoid (BitSet a)

Member Functions

mappend ∷ BitSet 𝖆 → BitSet 𝖆 → BitSet 𝖆
infixr  13

mconcat ∷ [BitSet 𝖆] → BitSet 𝖆

inherited from Monoid.mconcat

mempty ∷ BitSet 𝖆

mtimes ∷ Int → BitSet 𝖆 → BitSet 𝖆

inherited from Monoid.mtimes

sconcat ∷ [BitSet 𝖆] → BitSet 𝖆

inherited from Semigroup.sconcat

stimes ∷ Int → BitSet 𝖆 → BitSet 𝖆

inherited from Semigroup.stimes

instance Ord (BitSet a)

Member Functions

< ∷ BitSet 𝖆 → BitSet 𝖆 → Bool
infix  9

inherited from Ord.<

<= ∷ BitSet 𝖆 → BitSet 𝖆 → Bool
infix  9

inherited from Ord.<=

<=> ∷ BitSet 𝖆 → BitSet 𝖆 → Ordering
infix  8

> ∷ BitSet 𝖆 → BitSet 𝖆 → Bool
infix  9

inherited from Ord.>

>= ∷ BitSet 𝖆 → BitSet 𝖆 → Bool
infix  9

inherited from Ord.>=

compare ∷ BitSet 𝖆 → BitSet 𝖆 → Ordering
infix  8

inherited from Ord.compare

max ∷ BitSet 𝖆 → BitSet 𝖆 → BitSet 𝖆

inherited from Ord.max

min ∷ BitSet 𝖆 → BitSet 𝖆 → BitSet 𝖆

inherited from Ord.min

instance (Show a, Enum a) ⇒ Show (BitSet a)

Member Functions

display ∷ (Show 𝖆, Enum 𝖆) ⇒ BitSet 𝖆 → String

inherited from Show.display

show ∷ (Show 𝖆, Enum 𝖆) ⇒ BitSet 𝖆 → String

showChars ∷ (Show 𝖆, Enum 𝖆) ⇒ BitSet 𝖆 → [Char]

inherited from Show.showChars

showList ∷ (Show 𝖆, Enum 𝖆) ⇒ [BitSet 𝖆] → String → String

inherited from Show.showList

showsPrec ∷ (Show 𝖆, Enum 𝖆) ⇒ Int → BitSet 𝖆 → String → String

inherited from Show.showsPrec

showsub ∷ (Show 𝖆, Enum 𝖆) ⇒ BitSet 𝖆 → String

inherited from Show.showsub

Functions and Values by Type

Int → Int → Bool

Bits_Int.testBit

Int → Int → Int

Bits_Int.xor, Bits_Int.shift, Bits_Int.rotate, Bits_Int.complementBit, Bits_Int.clearBit, Bits_Int.setBit

Int → Bool

Bits_Int.isSigned

Int → Int

Bits_Int.bitSize, Bits_Int.bit, Bits_Int.bitCount

Int → Integer

Bits_Integer.bit

Int → Long

Bits_Long.bit

Integer → Int → Bool

Bits_Integer.testBit

Integer → Int → Integer

Bits_Integer.shift, Bits_Integer.rotateR, Bits_Integer.rotate, Bits_Integer.rotateL, Bits_Integer.setBit, Bits_Integer.clearBit, Bits_Integer.complementBit

Integer → Integer → Integer

Bits_Integer.xor

Integer → Bool

Bits_Integer.isSigned

Integer → Int

Bits_Integer.bitSize, Bits_Integer.bitCount

Long → Int → Bool

Bits_Long.testBit

Long → Int → Long

Bits_Long.shift, Bits_Long.rotate, Bits_Long.complementBit, Bits_Long.clearBit, Bits_Long.setBit

Long → Long → Long

Bits_Long.xor

Long → Bool

Bits_Long.isSigned

Long → Int

Bits_Long.bitSize, Bits_Long.bitCount

BitSet α → BitSet α → BitSet α

BitSet.union, BitSet.intersection, BitSet.difference

BitSet α → BitSet α → Bool

BitSet.subset

BitSet 𝖆 → BitSet 𝖆 → BitSet 𝖆

Monoid_BitSet.mappend, Ord_BitSet.min, Ord_BitSet.max

BitSet 𝖆 → BitSet 𝖆 → Bool

Eq_BitSet.!=, Eq_BitSet.==, Ord_BitSet.>=, Ord_BitSet.<, Ord_BitSet.<=, Ord_BitSet.>

BitSet 𝖆 → BitSet 𝖆 → Ordering

Ord_BitSet.compare, Ord_BitSet.<=>

BitSet 𝖆 → Bool

ListEmpty_BitSet.null

BitSet 𝖆 → Int

Eq_BitSet.hashCode, BitSet.size

BitSet 𝖆 → Long

BitSet.set

[BitSet 𝖆] → BitSet 𝖆

Monoid_BitSet.sconcat, Monoid_BitSet.mconcat

Int → BitSet 𝖆 → BitSet 𝖆

Monoid_BitSet.stimes, Monoid_BitSet.mtimes

Long → BitSet e

BitSet.BitSet

𝖆 → Bool

BitSet.has$set

Bits a ⇒ Int → a

Bits.bit

Bits a ⇒ a → Int → Bool

Bits.testBit

Bits a ⇒ a → Int → a

Bits.ushiftR, Bits.shiftL, Bits.setBit, Bits.rotateR, Bits.shift, Bits.shiftR, Bits.rotate, Bits.clearBit, Bits.complementBit, Bits.rotateL

Bits a ⇒ a → a → a

Bits.xor, Bits..|., Bits..&., Bits..^.

Bits a ⇒ a → Bool

Bits.isSigned

Bits a ⇒ a → Int

Bits.bitCount, Bits.bitSize

Bits a ⇒ a → a

Bits.complement

Enum α ⇒ BitSet α → [α]

BitSet.toList

Enum α ⇒ α → BitSet α → Bool

BitSet.member

Enum α ⇒ α → BitSet α

BitSet.singleton

Enum 𝖆 ⇒ BitSet 𝖆 → 𝖆 → BitSet 𝖆

BitSet.unionE, BitSet.intersectionE, BitSet.differenceE

Enum 𝖆 ⇒ [𝖆] → BitSet 𝖆

BitSet.fromList

(Show 𝖆, Enum 𝖆) ⇒ BitSet 𝖆 → String

Show_BitSet.showsub, Show_BitSet.display, Show_BitSet.show

(Show 𝖆, Enum 𝖆) ⇒ BitSet 𝖆 → [Char]

Show_BitSet.showChars

(Show 𝖆, Enum 𝖆) ⇒ [BitSet 𝖆] → String → String

Show_BitSet.showList

(Show 𝖆, Enum 𝖆) ⇒ Int → BitSet 𝖆 → String → String

Show_BitSet.showsPrec

BitSet 𝖆

ListEmpty_BitSet.empty, Monoid_BitSet.mempty

(Enum α, Bounded α) ⇒ BitSet α

BitSet.universal

BitSet 𝖆 → (Long→Long) → BitSet 𝖇

BitSet.chg$set

BitSet 𝖆 → Long → BitSet 𝖇

BitSet.upd$set