Thomas Hartman writes:
another point: "deforested" treesort is slower. The commented indicated that
-- If you deforest this algorithm (removing the intermediate tree structure) you are left with treeSort' [] = [] treeSort' (x:xs) = treeSort' (filter (<= x) xs) ++ [x] ++ treeSort' (filter (x <) xs)
So.. my take home lesson is that deforestation isn't a performance neutral thing to do. Assuming the comment is correct.
Well this was just the removal of the auxiliary *tree* formulae, but such
recursive concatenation isn't anything which should be popularized...
I don't want to start an analysis of known issues, but if you WANT to have
*similar* algorithms relatively efficient, there are two things to do:
1. Avoid two pass filtering.
2. Avoid unecessary (++), with an accumulator. For example:
qsort l = qs l [] where -- pa is the one-pass partition
qs (x:xs) ac = pa xs [] [] where
pa (y:ys) s b | x