Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to design co-programs

patternsinfp.wordpress.com

Post reply on HN
Print view View original

11–20 of 23 posts

Re: How to design co-programs

#11

Post by justinpombrio »

emmanueloga_ wrote: post #8

Funny how the author gave this talk in honor of Felleisen's on his 60th birthday. "Hi, to honor you I'll talk about how one of your better known works is incomplete and only shows half of the picture". I started reading HTDP long ago but at the time I made the huge mistake of taking a detour to learn Racket, and later Scheme... HTDP provides small languages just to save students from the herculean effort of having to…

Matthias once told me that the people who point out flaws in your work are your friends.

Re: How to design co-programs

#12

Post by pwm »

smadge wrote: post #4

The intermediate representation of the binary tree for QuickSort in this article was a “eureka” moment for me. I think algorithm and data structure curriculums should take this approach.

Completely agree. Maybe it’s because CS curricula tends to teach searching/sorting algorithms before data structures, specifically BSTs. Not sure why...

If you think about it a BST defines order and a sorting algorithm achieves it so naturally the output of a sort can be seen as a BST (flattening it to a list is somewhat irrelevant).

Re: How to design co-programs

#13

Post by jer_gib »

dfee wrote: post #3
dfee wrote: post #2

Ads on the blog but you’re too cheap to move to your own TLD. I don’t know why I find great humor in this, but the advertisement “Casinos hate this site...” made me laugh (and hate your site -> and swipe back to HN). Sorry, I’m away from my house and so there’s no pi-hole enabled.

As a follow-up, I think the humor is that I imagine this blog might have valuable information, but you’re turning off your target audience with low-brow ads.

For the record, the ads are all Wordpress's doing, not mine. I have no control over them, and derive no benefit from them (on the contrary, they put me off too!).

Re: How to design co-programs

#14

Post by tom_mellior »

pwm wrote: post #12
smadge wrote: post #4

The intermediate representation of the binary tree for QuickSort in this article was a “eureka” moment for me. I think algorithm and data structure curriculums should take this approach.

Completely agree. Maybe it’s because CS curricula tends to teach searching/sorting algorithms before data structures, specifically BSTs. Not sure why... If you think about it a BST defines order and a sorting algorithm achieves it so naturally the output of a sort can be seen as a BST (flattening it to a list is somewhat irrelevant).

> 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 tree in the QuickSort example. But now we're straying pretty far from a simple sorting algorithm in a first high-level algorithms course to a more complex and less abstract beast that is only maximally efficient if you assume a heroic compiler.

As a side note, heap sort (https://en.wikipedia.org/wiki/Heapsort) does perform sorting by constructing an intermediate heap data structure. It's just that the data structure is implicit as it is built in-place in the array to be sorted.

> If you think about it a BST defines order and a sorting algorithm achieves it so naturally the output of a sort can be seen as a BST (flattening it to a list is somewhat irrelevant).

Or, similarly, the construction of a BST is a sort: https://en.wikipedia.org/wiki/Tree_sort

Re: How to design co-programs

#15

Post by emmanueloga_ »

justinpombrio wrote: post #11
emmanueloga_ wrote: post #8

Funny how the author gave this talk in honor of Felleisen's on his 60th birthday. "Hi, to honor you I'll talk about how one of your better known works is incomplete and only shows half of the picture". I started reading HTDP long ago but at the time I made the huge mistake of taking a detour to learn Racket, and later Scheme... HTDP provides small languages just to save students from the herculean effort of having to…

Matthias once told me that the people who point out flaws in your work are your friends.

This is a nice philosophy, thanks for sharing that :-)

Re: How to design co-programs

#16

Post by smadge »

tom_mellior wrote: post #14
pwm wrote: post #12

Earlier quoted context omitted.

Completely agree. Maybe it’s because CS curricula tends to teach searching/sorting algorithms before data structures, specifically BSTs. Not sure why... If you think about it a BST defines order and a sorting algorithm achieves it so naturally the output of a sort can be seen as a BST (flattening it to a list is somewhat irrelevant).

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

Re: How to design co-programs

#17

Post by guest2143 »

geezerjay wrote: post #9
emmanueloga_ wrote: post #8

Funny how the author gave this talk in honor of Felleisen's on his 60th birthday. "Hi, to honor you I'll talk about how one of your better known works is incomplete and only shows half of the picture". I started reading HTDP long ago but at the time I made the huge mistake of taking a detour to learn Racket, and later Scheme... HTDP provides small languages just to save students from the herculean effort of having to…

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

Re: How to design co-programs

#18

Post by emmanueloga_ »

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

I don't know, I heard this interpretation before but honestly the phrase makes sense when interpreted the other way around too, so way not just take the first meaning.

The dig at Hook is a fun knowledge nugget anyway, that silly Isaac. :-p

Re: How to design co-programs

#19

Post by atopos »

Nice article!

Something along these lines is still present, I think, in HtDP, at least in the Chapter about abstractions (16.1, 16.5, and 16.6).

Basically, when designing a function one can use existing abstractions (or, I would add, design her own abstraction) whose whole signature, output included, matches the purpose and signature of the function to be designed.

So, if the problem at hand is to design a function that takes a natural number and produces a list, that calls for using the built-in `build-list`, whose signature is `N [N -> X] -> [List-of X]`. Or if the output of a function on lists is a Boolean value, one has to keep an eye on `ormap`/`andmap`, etc. So the output is also essential to choose the suitable abstraction.

Re: How to design co-programs

#20

Post by nuclx »

atopos wrote: post #19

Nice article! Something along these lines is still present, I think, in HtDP, at least in the Chapter about abstractions (16.1, 16.5, and 16.6). Basically, when designing a function one can use existing abstractions (or, I would add, design her own abstraction) whose whole signature, output included, matches the purpose and signature of the function to be designed. So, if the problem at hand is to design a function t…

This reminds me of type-driven programming as in Idris using the Type-Define-Refine workflow as described by Brady.
Post reply on HN