How to design co-programs • Hacker News Board

Re: How to design co-programs

#21

Post by geezerjay » Sat, Dec 01, 2018, 10:57 AM UTC

guest2143 wrote: post #17

geezerjay wrote: post #9

Earlier quoted context omitted.

> "Hi, to honor you I'll talk about how one of your better known works is incomplete and only shows half of the picture". ...or, you know, that old "standing on the shoulders of giants" thing.

Newton's "..standing on the shoulders of giants..." was a dig at Hook (who was short). It's Isaac being an arrogant jerk, which he was in spades. (Even if he revolutionized thinking in a number of areas.) It's not a statement of humbleness..

> Newton's "..standing on the shoulders of giants..." was a dig at Hook

The quote precedes Newton by half a millennia.

https://en.wikipedia.org/wiki/Standing_on_the_shoulders_of_g...

Re: How to design co-programs

#22

Post by tom_mellior » Sun, Dec 02, 2018, 12:31 PM UTC

smadge wrote: post #16

tom_mellior wrote: post #14

Earlier quoted context omitted.

> Maybe it’s because CS curricula tends to teach searching/sorting algorithms before data structures, specifically BSTs. 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. The blog does mention the deforestation optimization, which (if implemented sufficiently heroically) would remove the intermediate tr…

> 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,…

> 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.

Re: How to design co-programs

#23

Post by smadge » Tue, Dec 04, 2018, 5:28 AM UTC

tom_mellior wrote: post #22

smadge wrote: post #16

Earlier quoted context omitted.

> 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,…

> 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, 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.