2 ms·
Would a Haskell implementation of the second step (recursively call badsort and pick the first) actually exhaust all permutations of permutations before picking
by ginko 8y ago
Would a Haskell implementation of the second step (recursively call badsort and pick the first) actually exhaust all permutations of permutations before picking the first item, or would this have O(n) (or at least less than O(n!)) complexity due to lazy evaluation?
- majewsky 8y agoThe 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 since they all call `badSort 0` eventually.
- gowld 8y agoIt'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.