[Haskell-cafe] Toy compression algorithms [was: A very edgy language]

Stefan O'Rear stefanor at cox.net
Mon Jul 9 16:31:00 EDT 2007

On Mon, Jul 09, 2007 at 09:15:07PM +0100, Andrew Coppin wrote:
> Bulat Ziganshin wrote:
>> Hello Andrew,
>> Sunday, July 8, 2007, 7:07:59 PM, you wrote:
>> i don't think that ppm is so complex - it's just probability of
>> symbol in some context. it's just too slow in naive implementation
> Oh, sure, the *idea* is simple enough. Trying to actually *implement* it 
> correctly is something else... ;-)

Took me about an hour and 50 lines of code (about a year ago - this was
one of my first Haskell programs) to implement a PPM (de)compressor that
didn't crash, always generated the same output as input, and achieved
50% ratios on its own source code (not quite as good as gzip, but what
do you expect from a completely untuned compressor?).

Peak throughput: 2 bits / sec. :)

>> the jhc is very different story
> Yes - last I heard, it's an experimental research project rather than a 
> production-ready compiler...

Correct.  It requires 5 minutes and 600MB of RAM to compile Hello,
World, and fails with internal pattern match errors on anything
significantly larger.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070709/ff94085c/attachment.bin

More information about the Haskell-Cafe mailing list