4 ms·

> I think it's more because sorting is all about "efficiency", and sorting things without allocating a ton of intermediate data structures is viewed as more eff

by smadge 8y ago

> I think it's more because sorting is all about "efficiency", and sorting things without allocating a ton of intermediate data structures is viewed as more efficient. I agree that probably explains a lot of it. However the cost to efficiency is not that large and may be worth the gains in conceptual clarity. First, the traditional implementation of QuickSort has an implicit (or virtual?) intermediate data structure, the function call tree. Second, I have limited understanding of lazy evaluation, but in a lazy language I believe ‘flatten’ would begin consuming the tree as it is still being built by ‘build’.

tom_mellior 8y ago
> First, the traditional implementation of QuickSort has an implicit (or virtual?) intermediate data structure, the function call tree. That's a good point, but function calls have a constant cost in terms of stack frame allocation and deallocation. > Second, I have limited understanding of lazy evaluation, but in a lazy language I believe ‘flatten’ would begin consuming the tree as it is still being built by ‘build’. Yes, that is correct. The entire tree is not allocated at once, only the nodes that are actually needed, as well as dynamic data representing suspended computations of the rest of the data structure. But (again, ignoring compiler optimizations that would make them go away) these are allocations on the garbage-collected heap and thus incur GC costs and complexity. Overall I agree that there would be value in illustrating algorithms by also showing the version that constructs the computation tree. But I don't think it should be the one presentation of the algorithm, only a device to further understanding of the "real" implementation.
- smadge 8y ago
  Yes, definitely. For example, the explanation of MergeSort in CLRS’s “Introduction to Algorithms” has a figure which shows tree a of lists being transformed into another shorter tree of lists where the lower nodes have been merged.

by smadge 8y ago

tom_mellior 8y ago

> First, the traditional implementation of QuickSort has an implicit (or virtual?) intermediate data structure, the function call tree. That's a good point, but function calls have a constant cost in terms of stack frame allocation and deallocation. > Second, I have limited understanding of lazy evaluation, but in a lazy language I believe ‘flatten’ would begin consuming the tree as it is still being built by ‘build’. Yes, that is correct. The entire tree is not allocated at once, only the nodes that are actually needed, as well as dynamic data representing suspended computations of the rest of the data structure. But (again, ignoring compiler optimizations that would make them go away) these are allocations on the garbage-collected heap and thus incur GC costs and complexity. Overall I agree that there would be value in illustrating algorithms by also showing the version that constructs the computation tree. But I don't think it should be the one presentation of the algorithm, only a device to further understanding of the "real" implementation.

smadge 8y ago
Yes, definitely. For example, the explanation of MergeSort in CLRS’s “Introduction to Algorithms” has a figure which shows tree a of lists being transformed into another shorter tree of lists where the lower nodes have been merged.