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

[Jonathan Cast]

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