When I first learned the C programming language I found data compression 
algorithms very educational. Does anyone have references to toy data 
compression implementations written in OCaml?

There was a thread in the Haskell mailing list recently about a 
Burrows-Wheeler implementation that is very concise and quite efficient in 
Haskell. In particular, it uses the lazy sort to get the kth smallest element 
in O(n) time trick... :-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e