nonempty IntSet?

[jwaldmann]

When reading #616 I tought about IntSet. Currently,

data IntSet = Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !IntSet !IntSet
-- Invariant: Nil is never found as a child of Bin.
            | Tip {-# UNPACK #-} !Prefix {-# UNPACK #-} !BitMap
            | Nil

By making the invariant more explicit, this could be changed to something like

data IntSetNE = Bin .. | Tip ..
data IntSet = Maybe IntSetNE

with IntSetNE exported - or not, but my point is, this reduces the number of constructors of the tree (from 3 to 2), and this might give shorter code (source and machine), maybe faster code, and less memory.

[Ericson2314]

This was discussed on the libraries list a bit. We unfortunately need to do something more clever here to avoid the Just . Bin and friends double indirection / extra bottom. The earliest versions of GHC we support unfortunately give us few options.

[treeowl]

I don't think *any* extant versions give us good options. Unboxed sums don't really unpack the way we'd like them to here. If we had a (totally possible) newtype-like optimization for existential types with exactly one strict field and no class constraints, then there'd be a different option (with rather less object code, I believe). But I see no way at present without duplicating code at the root for every operation whether it otherwise needs special treatment there or not :-(.

…

On Wed, Jul 24, 2019, 9:17 PM John Ericson ***@***.***> wrote: This was discussed on the libraries list a bit. We unfortunately need to do something more clever here to avoid the Just . Bin and friends double indirection / extra bottom. The earliest versions of GHC we support unfortunately give us few options. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#669?email_source=notifications&email_token=AAOOF7PUVOSWBZJMQCQXK2LQBD5JLA5CNFSM4IFTCYNKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD2YBKMA#issuecomment-514856240>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAOOF7INHIOLYK4J6DMRSFTQBD5JLANCNFSM4IFTCYNA> .