2-pivot quicksort
This posting on the Java core library mailing list proposes to replace the current quicksort with a new, 2-pivot quicksort.
Ordinary quicksort in Haskell looks something like this:
quicksort [] = []
quicksort (pivot:rest) =
quicksort [x| x ← rest, x ≤ pivot] ++
[pivot] ++
quicksort [x| x ← rest, [...]
Coldplay’s ‘42’ from Viva la Vida or Death and All His Friends (starting about 1:45), Nine Inch Nails ‘Complication’ from The Fragile.
Our target for this exercise is “Things that other languages should take from Lisp”.
Bignum support
In Scheme and Common Lisp, by default you can’t overflow an integer…
Prelude> fac n = product [2..n]
Prelude> fac 100
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582
51185210916864000000000000000000000000
In Common Lisp, you can force your code to use fixed-size numbers (fixnums) for efficiency…
Prelude> let fac n = product [2..n] :: Int
Prelude> [...]
