Num instance for Lazy ByteStrings (was: NumLazyByteString Package License)
Tristan and other interested parties on the Cafe,
Answering your question first, Tristan: I was going to use BSD3 (if it
isn't already) for the NumLazyByteString.
For the cafe too:
A while ago I made a Num instance for LPS; it is currently on my
code.haskell.org account. Notice this isn't on Hackage yet and the
semantics will be different soon. Most notably I want to ensure
divide and anything else implemented through 'asInteger' and
'asInteger2' results in a bytestring of length equal to the largest of
the operands.
If that isn't clear then let me be very explicit. NumLazyByteString
intentionally allows overflow! If you want operations (mod 2^40) then
you need only work with bytestrings of length 5 bytes and the
operations will result in 5 byte ByteString. This is already true for
basic operations (bit operations, +, -, *) but is not yet done for
quot, rem, quotRem, divMod, mod, /, and other you can see leverage
Integer instead of using custom code.
Any desire for non-overflowing operations (basically, re-expressing
Integer as LazyByteString) would have to be done as an newtype with a
Num instance that grows the bytestring to the necessary level,
preventing overflow prior to calling NumLazyByteString.
Finally, I intend for numerous operations to be lazy. If you add two
infinite bytestrings you should be able to get the result of that
operation (modulo some finite value) using NumLazyByteString. This is
obviously not true for those operations leveraging Integer.
Any comments or requests on the future of this Library are welcome -
I'll probably get around to finishing it and putting it on Hackage in
a couple weeks.
Cheers,
Thomas
On Sun, Mar 7, 2010 at 9:24 PM, Tristan Ravitch
I found myself adding Bits and Num instances for ByteStrings when I found your implementation (which is much better than mine was shaping up to be). Do you have any particular license in mind for it?
I used it in an implementation of the Delta Debugging algorithm (http://www.st.cs.uni-saarland.de/dd/), which I was thinking I would like to release, and wanted to make sure the licensing could work out properly.
Thanks, -- Tristan Ravitch travitch@cs.wisc.edu http://pages.cs.wisc.edu/~travitch
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.10 (GNU/Linux)
iEYEARECAAYFAkuUiiUACgkQJklRJNuIcWSxmACfVblD+gR/Fv57teNTArSfXhHg NtsAnRqBvinNesMk3mxMxDERw5MBn9jZ =Jm4O -----END PGP SIGNATURE-----
On Mon, 8 Mar 2010, Thomas DuBuisson wrote:
Tristan and other interested parties on the Cafe,
Answering your question first, Tristan: I was going to use BSD3 (if it isn't already) for the NumLazyByteString.
Is NumLazyByteString a newtype around Bytestring.Lazy that interprets the bit stream represented by the ByteString as integer? If so, could this also be done using a newtype around [Integer], where appropriately large Integers are used? If yes, you may find http://code.haskell.org/numeric-prelude/src/Number/Positional.hs useful.
Is NumLazyByteString a newtype around Bytestring.Lazy that interprets the bit stream represented by the ByteString as integer?
Not exactly. There is not newtype wrapper. NumLazyByteString is: instance Num L.ByteString where ... instance Enum L.ByteString where ... instance Integral L.ByteString where ... instance Bits L.ByteString where ...
If so, could this also be done using a newtype around [Integer], where appropriately large Integers are used? If yes, you may find http://code.haskell.org/numeric-prelude/src/Number/Positional.hs useful.
Thanks for the pointer.
Henning Thielemann wrote:
Is NumLazyByteString a newtype around Bytestring.Lazy that interprets the bit stream represented by the ByteString as integer?
Thomas DuBuisson wrote:
Not exactly. There is not newtype wrapper. NumLazyByteString is: instance Num L.ByteString where ...
Are you absolutely certain that this is the one and only canonical instance that can ever exist that makes sense? Otherwise, please use a newtype wrapper. The reason for this is one of the few remaining major warts in Haskell - that there is absolutely *no way* to prevent the export of instances from a module that you import. So it is considered good practice in current Haskell never to write an instance if anyone has ever published one previously, even if you don't foresee ever using the package in which the instance was defined. Otherwise, someone someday may write code that indirectly depends on both modules in some way, and that code will mysteriously fail to compile. In practice, that implies: never write an unwrapped instance for a datatype that you did not define yourself, and especially not for types that are published and are in common usage, unless you are absolutely certain that your instance is truly canonical and universal. By saying that this is a wart, I am not saying that I think it is a good idea to write more than one instance for the same type intentionally. It is not. But there is no way to prevent it from ever happening inadvertently. So it is important for there to be a mechanism to prevent the import of an unwanted instance when that comes up. Your desire to write this instance is yet another case that demonstrates why this is clearly a wart. Regards, Yitz
On Mar 9, 2010, at 09:41 , Yitzchak Gale wrote:
Henning Thielemann wrote:
Is NumLazyByteString a newtype around Bytestring.Lazy that interprets the bit stream represented by the ByteString as integer?
Thomas DuBuisson wrote:
Not exactly. There is not newtype wrapper. NumLazyByteString is: instance Num L.ByteString where ...
Are you absolutely certain that this is the one and only canonical instance that can ever exist that makes sense? Otherwise, please use a newtype wrapper.
Or from the other direction: you're in essence declaring that *any* ByteString can be used as a Num, etc. This strikes me as inviting confusion, at the very least; I'd strongly prefer the type system to help me distinguish ByteStrings used as Nums from those used as Strings, instead of quietly doing unexpected things (or issuing odd type errors) because I accidentally passed the wrong argument. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
Yitzchak Gale schrieb:
Henning Thielemann wrote:
Is NumLazyByteString a newtype around Bytestring.Lazy that interprets the bit stream represented by the ByteString as integer?
Thomas DuBuisson wrote:
Not exactly. There is not newtype wrapper. NumLazyByteString is: instance Num L.ByteString where ...
Are you absolutely certain that this is the one and only canonical instance that can ever exist that makes sense? Otherwise, please use a newtype wrapper.
I think there are at least two reasonable instance: One that treats all bytes individually and one that treats the whole bytestring as one binary number. Btw. I assume that in order to be lazy when computing exactly with integers you must start with the least significant bits, right? In my implementation of Positional numbers I start with the most significant digits since I implemented fractional numbers and I must use a redundant set of digits in order to stay lazy in case of carries.
The reason for this is one of the few remaining major warts in Haskell - that there is absolutely *no way* to prevent the export of instances from a module that you import.
Since this is a common issue a wrote a Wiki article on it: https://haskell.org/haskellwiki/Orphan_instance
participants (5)
-
Brandon S. Allbery KF8NH -
Henning Thielemann -
Henning Thielemann -
Thomas DuBuisson -
Yitzchak Gale