[Haskell-cafe] RFC: demanding lazy instances of Data.Binary

Nicolas Frisby nicolas.frisby at gmail.com
Mon Nov 19 16:04:48 EST 2007


I've got a first draft with the newtype and just an instance for list.



If you'd prefer fewer questions, please let me know ;)



0) I've cabalised it ("lazy-binary"), but I don't have anywhere to host it.
Would it be appropriate to host on darcs.haskell.org or HackageDB (yet?).
Suggestions?

1) The fact that serialisation is fully strict for 32760 bytes but not for
32761 makes the direct application of strictCheck intractable. Do you have
any ideas how to circumvent that?

  ((unLazy . decode . encode . Lazy) `asTypeOf` id) (take 32760 (repeat ())
++ undefined)
        => undefined

  ((unLazy . decode . encode . Lazy) `asTypeOf` id) (take 32761 (repeat ())
++ undefined)
       => lots of ()s and then undefined

2) Also, any suggestions for other datatypes to provide default instances
for? Tree type structures immediately raise the question of which traversal
should be the default. I'm learning towards providing none since the goal of
constant space usage actually depends on the serialisation order matching
how the deserialised tree will be traversed.

3) I don't think it is applicable in anyway whatsoever to strict types like
Int, Data.Set, and Data.Sequence? Counter-arguments?

4) Perhaps the tight correspondence between serialisation and traversal
necessary for constant space usage does indeed mean that the instance for
the lazy list is the only appropriate one to provide. Perhaps the Chunks
data type and a function splitN :: Int -> [a] -> Chunks [a] would also be
helpful.

Thanks!

16, 2007 12:45 PM, Don Stewart <dons at galois.com> wrote:

> dons:
> > nicolas.frisby:
> > > I've noticed a few posts on the cafe, including my own experience,
> > > where the spine-strictness of the Binary instance for lists caused
> > > some confusion. I'd like to suggest an approach to preventing this
> > > confusion in the future, or at least making it easier to resolve.
> > >
> > > Having decided that it is indeed appropriate for some standard
> > > instances to be strict by default [1], I think it would be beneficial
> > > to standardize an approach for expressing that a lazy instance is
> > > expected. I propose the following newtype be added to Data.Binary. A
> > > demonstration immediately follows.
> > >
> > > > newtype Lazily a = Lazily { unLazily :: a }
> > >
> > > > -- example instance
> > > > instance Binary a => Binary (Lazily [a]) where
> > > >     -- lazy get and put
> > >
> > > Now
> > >
> > > > [1..] = (unLazily . decode . encode . Lazily) [1..]
> > >
> > > instead of
> > >
> > > > _|_ = (decode . encode) [1..]
> > >
> > > This email is a request for comments on this concept. I think it is a
> > > minimal way of expressing the intent that the serialisation be lazy
> > > [2]. Please share any concerns or suggestions. I'll submit a patch
> > > once the discussion is complete... or if it becomes inactive ;)
> >
> > I think this is a good compromise: allowing laziness for those who need
> > it, in a clean manner. How about we provie
> >
> >     Data.Binary.Lazy
> >
> > with the Lazy newtype, and lazy instances for types that make sense to
> > be so?
> >
> > For now, this can be developed as a single module depending on
> > Data.Binary . What do you think, Nick?
>
> I'd like to also use strictCheck, as we did for the stream fusion
> library, to state and check strictness properties for the instances,
> since getting this clear and correct seems to be a common FAQ with
> Binary.
>
> -- Don
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071119/3246edf9/attachment.htm


More information about the Haskell-Cafe mailing list