Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add a bitset newtype wrapper #113

Open
Jashweii opened this issue Apr 12, 2021 · 3 comments
Open

Add a bitset newtype wrapper #113

Jashweii opened this issue Apr 12, 2021 · 3 comments

Comments

@Jashweii
Copy link

These would function the same as other set instances or n-tupled bool instances but efficiently via Bits and FiniteBits.

newtype BitSet a = BitSet a
    deriving (Eq, Bits, FiniteBits)
--  Should probably show/read as binary or a set of set bits (latter doesn't have read . show = id since it can re-order)
instance Bits a => PartialOrd (BitSet a) where
--  Avoiding complement on purpose (see finitebits note), there may be a more concise solution
    a `leq` b = (zeroBits == (a .&. (a `xor` b)))
instance Bits a => Lattice (BitSet a) where
    (\/) = (.|.)
    (/\) = (.&.)
instance Bits a => BoundedJoinSemiLattice (BitSet a) where
    bottom = zeroBits
-- see oneBits note in base 4.16 on ghc's gitlab
-- https://gitlab.haskell.org/ghc/ghc/-/blob/master/libraries/base/Data/Bits.hs#L79
instance FiniteBits a => BoundedMeetSemiLattice (BitSet a) where
--  top = oneBits -- 4.16
    top = complement zeroBits
instance FiniteBits a => Bounded (BitSet a) where
    maxBound = top
    minBound = bottom

(Natural is an example of a Bits that is not a FiniteBits, and is undefined for complement)

@phadej
Copy link
Collaborator

phadej commented Apr 12, 2021

Makes sense. PR welcome.

EDIT: I'm not sure about name though. We have Ord -> Ordered. So here I'd expect some adjective as well, but my English isn't good enough.

EDIT: instance FiniteBits a => Bounded (BitSet a) where I'm not sure why you propose it. I don't think we need it. (Bounded is tricky class, I'd rather avoid it).

@phadej
Copy link
Collaborator

phadej commented Apr 13, 2021

FWIW, I wanted to clean up Bits and FiniteBits such that complement wouldn't be in Bits, so Natural can be an instance without miss-behaving methods: https://mail.haskell.org/pipermail/libraries/2019-December/030132.html

@Jashweii
Copy link
Author

Jashweii commented Apr 13, 2021

How about Bitwise? I'm not sure if there might be some other useful Bits-based lattice other than wrappers applied to this however (like something acting as a nested Lexicographic on bits), and it doesn't really indicate the idea of a set.

I just added Bounded as they're bounds for the partial order, the docs on Bounded themselves say
"Ord is not a superclass of Bounded since types that are not totally ordered may also have upper and lower bounds"
I suppose one of the issues with Bounded is where Ord and PartialOrd don't match up, I wasn't thinking of an Ord instance but ofc then if someone wanted to put one of these in a Map directly they would be out of luck.

I have not had much luck with a show instance only requiring Bits. What I really need is a bit size that's argument dependent rather than a constant (and for read a function to check an argument can get another bit). Basically a partial isomorphism with [Bool]. The instance is possibly more hassle than it's worth over using stock show/read (either way a show instance is required by the tests).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants