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

On Monday 09 July 2007, Andrew Coppin wrote: <snip>

Yes, but there are limits to what an optimiser can hope to accomplish.

For example, you wouldn't implement a bubble sort and seriously expect the compiler to be able to "optimise" that into a merge sort, would you? ;-)

Something like it's been done; compilers can take in a quadratic time list reverse and substitute a linear time version: http://homepages.inf.ed.ac.uk/wadler/papers/vanish/vanish.ps.gz (pg. 2-3). One of the better all-time papers by the major Haskell researchers, I'd say. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs