Add "Elem" type synonym

[ezyang]

I'd like to write some Backpack signatures which help smooth over the difference between Char8 and Word8 ByteStrings; however, in order to write the signature, I need to declare a new type "data Elem" to parametrize over the element type of the ByteString:

signature Data.ByteString where

data ByteString
data Elem

singleton :: Elem -> ByteString

In order for a module to implement this signature, it needs to export Elem. So this is very disappointing, which is the literal Data.ByteString from bytestring doesn't implement this signature.

Could we make it implement it? Yes, very easily: just add a type synonym type Elem = Char/Word8 to each of the ByteString modules. Done. Can we? (It's an easy patch but I have to convince you guys to take it.)

[ezyang]

I discovered a neat workaround for this problem (put the Elem definition in its own signature) so this is less pressing.

[dcoutts]

I could be convinced. I'd like to see the whole signature ideally. Would that also live in the bytestring package?

[dcoutts]

@ezyang what about type family GHC.Exts.Item ByteString ? Or does that not work exactly because it has to be a single type whereas you want a different type for each module?

[ezyang]

The signature couldn't live in the bytestring package (though it could live in the repo) because you'd want to be able to depend on it directly, but you can only have one public library per package ;)

Here's an excerpt of the signature I have (I may decide to rename Elem to Chr):

signature Data.ByteString where

import System.IO (Handle)
import Foreign.C (CString, CStringLen)
import Data.ByteString.Elem

-- | A space-efficient representation of a 'Elem' vector, supporting many
-- efficient operations.
--
data ByteString

-- | /O(1)/ The empty 'ByteString'
empty :: ByteString

-- | /O(1)/ Convert a 'Elem' into a 'ByteString'
singleton :: Elem -> ByteString

The Item approach nearly works (replace Elem with Item ByteString); the primary downside is that if we want to subsequently declare that Item ByteString ~ Char, we need to declare a family instance in an hsig file, which is not currently supported. (Though, maybe it should be!)

[fumieval]

#219 added an IsList instance to ByteString but Item ByteString is always Word8 because Char8 wraps functions, not the type. I suppose we need to add type synonyms individually as https://github.com/haskell/bytestring/issues/102#issue-195719816 suggested. I almost always import Data.ByteString with qualification so I'm fine with symbol additions.

[Bodigrim]

I would love to have an enthusiastic user of Backpack to push this forward. I do not use Backpack myself, and I do not want to add such things speculatively, without knowing that this is really helpful for users.

[fumieval]

Admittedly, I haven't used backpacks seriously other than bytes-builder-shootout. I can imagine that, if bytestring had a useful example, there'll be a lot more users of backpack; looks like a chicken-egg problem.

[Bodigrim]

I'm not referencing to a slow adoption of Backpack here. The thing is that I have very little idea how Backpack works (today). Is this change required for backpackisation? Is it enough? Could someone demonstrate backpack signatures, built against forked bytestring?

[ezyang]

It's not required for Backpack-ization, but without it, I have to make a "bytestring-backpack" package that provides the bytestring module reexported PLUS the extra Elem type synonym. It just makes everything marginally more difficult to use.

[Bodigrim]

@ezyang thanks, understood. Could you possibly draft a backpack signature, assuming that there is Elem, to ensure that nothing else is missing?

[ezyang]

Here it is: https://github.com/haskell-backpack/backpack-str/blob/master/str-sig/Str.hsig

[Bodigrim]

@ezyang could you possibly suggest other improvements to bytestring which would make backpack signature better/easier/covering more?

I wonder what is better: just add a type synonym type Elem = Char8 or also replace Char8 by Elem in all signatures?

[ezyang]

It's not necessary to replace the signatures with Elem; Backpack can match even in the presence of type synonyms. https://github.com/haskell-backpack/backpack-str/blob/master/str-bytestring/Str/ByteString.hs shows the full set of "extra goop" I added to make the signatures line up. I'm not sure I'd recommend putting all of them in base, but it should give you some sense for what I found I needed to smooth over.