Persistant (as in on disk) data

Malcolm Wallace Malcolm.Wallace@cs.york.ac.uk
Fri, 7 Mar 2003 09:40:46 +0000


"mike V" <mivori@hotmail.com> writes:

> >The nhc98 compiler already accepts a `deriving Binary' clause.
> >DrIFT likewise already supports {-! derives : Binary !-}.
> 
> What was the strategy employed to derive instances of sum types, i.e. the 
> binary representation?

For a sum-of-products type with n constructors, represent the
constructor as a bit sequence of length ceiling(log n), and then
simply append the binary representation of each product component.

This gives a nice generic scheme, although of course it is possible to
write instances manually that yield a higher compression.  For instance
in some applications we used Huffman encoding based on the frequency
of occurrence of each constructor.

Regards,
    Malcolm