3 ms·

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

by smadge 8y ago

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.

cryptonector 8y ago
No kidding. This is very nice. I might be taking some liberties here, but the point about the shape of the output driving the shape of the program reminds me of using schema information in SQL (think of declared foreign keys) to generate queries: the schema tells you the shape of the data in more ways than just tables and columns, and this in turn tells you about the queries you might want. If you enrich a relational schema with more metadata, then you can generate even more queries. Think of declaring the set of all relations that define authorization data, not just group memberships, but access controls that refer to groups, define ownership, and so on. So, for example, 'give me all the authorization-relevant entities "to the right" of this entity' might be a query that, given enough schema metadata, can generate a much more complex SQL query. But that abstract query itself becomes an obvious query given the shape of the data (i.e., the schema). A more concrete example is "what can this user do?" and "who can do what to this resource?", "what groups is this user a member of?", "what are all the members of this group?" (note: these are not trivial if groups nest) which are instantiations of "what are all the entities to the {left, right} of this entity, using the set {name} of relations?". In terms of SQL these are all JOINs or LEFT JOINs (depending on declared relation NULLability, or relation cardinalities), with RECURSIVE queries using UNION (not UNION ALL, to avoid infinite recursion in the presence of circular relations) for "nesting" relations (from a table to itself, perhaps crossing relations on other tables in the process). SQL is extremely powerful and expressive, but we can make these queries pithier and more obvious with a more abstract language that takes advantage of schema metadata. Indeed, graph databases are such a language. SQL needs a richer schema definition language (extensions will do) by which to formally describe more of the shape of the data.
agumonkey 8y ago
Something I've seen in most Xavier Leroy (of Ocaml) slides. It makes things so clear to me.
pwm 8y ago
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).
- tom_mellior 8y ago
  > 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 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 https://en.wikipedia.org/wiki/Tree_sort
  - 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’.

by smadge 8y ago

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.

cryptonector 8y ago

No kidding. This is very nice. I might be taking some liberties here, but the point about the shape of the output driving the shape of the program reminds me of using schema information in SQL (think of declared foreign keys) to generate queries: the schema tells you the shape of the data in more ways than just tables and columns, and this in turn tells you about the queries you might want. If you enrich a relational schema with more metadata, then you can generate even more queries. Think of declaring the set of all relations that define authorization data, not just group memberships, but access controls that refer to groups, define ownership, and so on. So, for example, 'give me all the authorization-relevant entities "to the right" of this entity' might be a query that, given enough schema metadata, can generate a much more complex SQL query. But that abstract query itself becomes an obvious query given the shape of the data (i.e., the schema). A more concrete example is "what can this user do?" and "who can do what to this resource?", "what groups is this user a member of?", "what are all the members of this group?" (note: these are not trivial if groups nest) which are instantiations of "what are all the entities to the {left, right} of this entity, using the set {name} of relations?". In terms of SQL these are all JOINs or LEFT JOINs (depending on declared relation NULLability, or relation cardinalities), with RECURSIVE queries using UNION (not UNION ALL, to avoid infinite recursion in the presence of circular relations) for "nesting" relations (from a table to itself, perhaps crossing relations on other tables in the process). SQL is extremely powerful and expressive, but we can make these queries pithier and more obvious with a more abstract language that takes advantage of schema metadata. Indeed, graph databases are such a language. SQL needs a richer schema definition language (extensions will do) by which to formally describe more of the shape of the data.

agumonkey 8y ago

Something I've seen in most Xavier Leroy (of Ocaml) slides. It makes things so clear to me.

pwm 8y ago

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

tom_mellior 8y ago
> 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 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 https://en.wikipedia.org/wiki/Tree_sort
- 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’.