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<y = pa ys s (y:b) | otherwise = pa ys (y:s) b pa [] s b = qs s (x:qs b ac) -- s- small; b- big; ac- buffer qs [] ac = ac Jerzy Karczmarczuk