4 ms·

The foldl in `badSort 0` has to evaluate its entire argument list. As far as I can see, this behavior propagates through to all functions shown in the article s

• gowld 8y ago
  It's foldr, not fold. That's what makes it consume absurd stack space, creating a stack of thunks of length (n-factorial-iterated-k-times, including the nested towers of folders inside each element) before it can use any laziness to shortcut the actual comparisons applied by `insert`. It creates the whole monolithic expression with all the parenthesis in pessimal positions, forcing all the comparisons in the wrong order (back to front, aka least-significant-bits first), which makes it impossible to use the short circuiting of lexicographical comparisons.