6 ms·

"I could only find a couple tutorials/guides and both were imperative" Aren't Quadtrees covered by almost all basic data-structure books? It is the most simple

by torusle 10mo ago

"I could only find a couple tutorials/guides and both were imperative" Aren't Quadtrees covered by almost all basic data-structure books? It is the most simple form of taking the binary tree into the next (2D) dimension.

pixelpoet 10mo ago
You can even build them with basically one line of code by sorting points using Morton / Z-curve order. It's linear time if you use a counting/radix sort. Edit: lol, downvoted for this post. Never change, HN.
- pavlov 10mo ago
  It’s super easy to click the downvote button by accident on mobile when you meant to upvote. And this UI will never be fixed because this is HN after all.
  - craftkiller 10mo ago
    This is precisely the reason that I do not log in to HN on my phone. My phone is read-only and if I want to upvote or comment then I have to switch to my laptop. Pretty easy with firefox because I can send tabs to other devices.
  - jasonjmcghee 10mo ago
    Zoom in or unvote/revote
  - acters 10mo ago
    That is why I like harmonic app, there is an invite button separating the upvote and downvote. Never going to have this kind of issue
  - proc0 10mo ago
    I just implemented an HN UI. This is good feedback as I'm aiming to have a mobile friendly web version. https://proc0.github.io/HackerZen https://proc0.github.io/HackerZen (it's also open source)
  - kristianp 10mo ago
    This is true, however you can see if you downvoted by the "undown" link displayed instead of "unvote".
  - deleted 10mo ago
    [deleted]
- quibono 10mo ago
  I'd love to see that. Could you link me to an implementation or explain this in more detail please?
  - johnisgood 10mo ago
    I would like to know about this more, too. Is there a code anywhere, ideally with comments? But I am fine without comments, too, I would just like to see the code and possibly with an example usage.
    - quibono 10mo ago
      Okay, I was intrigued and I did some digging. Morton / Z-order is all about interleaving the individual bits of the x and y coordinates. You end up grouping by quadrants. Python one liner: points.sort(key=lambda p: sum(((p[0]>>i&1)<<(2*i))|((p[1]>>i&1)<<(2*i+1)) for i in range(16)))
  - _jackdk_ 10mo ago
    Here's a 3D version used in the creation of sparse voxel octrees: https://forceflow.be/2013/10/07/morton-encodingdecoding-through-bit-interleaving-implementations/ https://forceflow.be/2013/10/07/morton-encodingdecoding-thro... Here's an example from AWS, where lat/long pairs are put into a Z-index, which is used as a DynamoDB sort key, letting you efficiently query for items near a point. https://aws.amazon.com/blogs/database/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-1/ https://aws.amazon.com/blogs/database/z-order-indexing-for-m...
- rdtsc 10mo ago
  Yeah good point, they are downsides for sure but it's a simple enough approach and most of all it can be shoved in a database (or b-tree or any 1d-sorted data structure). And for a z-curve, the order is basically a depth-first traversal of a quadtree.
zelphirkalt 10mo ago
The problem is rather, that most data structure tutorials and books don't even get the idea, to introduce a purely functional version, but merely state the imperative versions. Coming up with the functional versions of data structures can be difficult. Papers about it can be hard to understand and often require one to already know some niche language, that a researcher used for the paper. Even if you can find a functional implementation of a data structure, there is often not a good explanation and you need to, sort of, reverse engineer it and translate it to the language you are using. In short, it seems relatively few people have the skills to implement them and even fewer have the skills to come up with functional versions of ordinary data structures. They are almost completely absent from university lectures as well, as far as I am aware. For example for AVL trees I could only find a document from ETH from a lecture, that no longer exists or is taught. The language is Isabel and I need to understand its syntax first, before being able to translate it to Scheme. If anyone has an obscure source for implementations one can learn from and implement oneself in another language, please share.
- nanomonkey 10mo ago
  I've been looking for the same for scheme and clojure. Here are a few I've found: Functional Data Structures and Algorithms, A Proof Assistant Approach by Tobias Nipkow (Ed.) [https://fdsa-book.net/functional_data_structures_algorithms.pdf https://fdsa-book.net/functional_data_structures_algorithms....] Purely Functional Data Structures thesis by Chris Okasaki [https://www.cs.cmu.edu/~rwh/students/okasaki.pdf https://www.cs.cmu.edu/~rwh/students/okasaki.pdf] https://en.wikipedia.org/wiki/Purely_functional_data_structure https://en.wikipedia.org/wiki/Purely_functional_data_structu...
  - KPGv2 10mo ago
    Okasaki's is basically the Bible for this stuff. Anyone writing data structure libraries in a functional language will have read this or have it on their to-read list.
    - zelphirkalt 10mo ago

by torusle 10mo ago

pixelpoet 10mo ago

You can even build them with basically one line of code by sorting points using Morton / Z-curve order. It's linear time if you use a counting/radix sort. Edit: lol, downvoted for this post. Never change, HN.

pavlov 10mo ago
It’s super easy to click the downvote button by accident on mobile when you meant to upvote. And this UI will never be fixed because this is HN after all.
- craftkiller 10mo ago
  This is precisely the reason that I do not log in to HN on my phone. My phone is read-only and if I want to upvote or comment then I have to switch to my laptop. Pretty easy with firefox because I can send tabs to other devices.
- jasonjmcghee 10mo ago
  Zoom in or unvote/revote
- acters 10mo ago
  That is why I like harmonic app, there is an invite button separating the upvote and downvote. Never going to have this kind of issue
- proc0 10mo ago
  I just implemented an HN UI. This is good feedback as I'm aiming to have a mobile friendly web version. https://proc0.github.io/HackerZen https://proc0.github.io/HackerZen (it's also open source)
- kristianp 10mo ago
  This is true, however you can see if you downvoted by the "undown" link displayed instead of "unvote".
- deleted 10mo ago
  [deleted]
quibono 10mo ago
I'd love to see that. Could you link me to an implementation or explain this in more detail please?
- johnisgood 10mo ago
  I would like to know about this more, too. Is there a code anywhere, ideally with comments? But I am fine without comments, too, I would just like to see the code and possibly with an example usage.
  - quibono 10mo ago
    Okay, I was intrigued and I did some digging. Morton / Z-order is all about interleaving the individual bits of the x and y coordinates. You end up grouping by quadrants. Python one liner: points.sort(key=lambda p: sum(((p[0]>>i&1)<<(2*i))|((p[1]>>i&1)<<(2*i+1)) for i in range(16)))
- _jackdk_ 10mo ago
  Here's a 3D version used in the creation of sparse voxel octrees: https://forceflow.be/2013/10/07/morton-encodingdecoding-through-bit-interleaving-implementations/ https://forceflow.be/2013/10/07/morton-encodingdecoding-thro... Here's an example from AWS, where lat/long pairs are put into a Z-index, which is used as a DynamoDB sort key, letting you efficiently query for items near a point. https://aws.amazon.com/blogs/database/z-order-indexing-for-multifaceted-queries-in-amazon-dynamodb-part-1/ https://aws.amazon.com/blogs/database/z-order-indexing-for-m...
rdtsc 10mo ago
Yeah good point, they are downsides for sure but it's a simple enough approach and most of all it can be shoved in a database (or b-tree or any 1d-sorted data structure). And for a z-curve, the order is basically a depth-first traversal of a quadtree.

zelphirkalt 10mo ago

The problem is rather, that most data structure tutorials and books don't even get the idea, to introduce a purely functional version, but merely state the imperative versions. Coming up with the functional versions of data structures can be difficult. Papers about it can be hard to understand and often require one to already know some niche language, that a researcher used for the paper. Even if you can find a functional implementation of a data structure, there is often not a good explanation and you need to, sort of, reverse engineer it and translate it to the language you are using. In short, it seems relatively few people have the skills to implement them and even fewer have the skills to come up with functional versions of ordinary data structures. They are almost completely absent from university lectures as well, as far as I am aware. For example for AVL trees I could only find a document from ETH from a lecture, that no longer exists or is taught. The language is Isabel and I need to understand its syntax first, before being able to translate it to Scheme. If anyone has an obscure source for implementations one can learn from and implement oneself in another language, please share.

nanomonkey 10mo ago
I've been looking for the same for scheme and clojure. Here are a few I've found: Functional Data Structures and Algorithms, A Proof Assistant Approach by Tobias Nipkow (Ed.) [https://fdsa-book.net/functional_data_structures_algorithms.pdf https://fdsa-book.net/functional_data_structures_algorithms....] Purely Functional Data Structures thesis by Chris Okasaki [https://www.cs.cmu.edu/~rwh/students/okasaki.pdf https://www.cs.cmu.edu/~rwh/students/okasaki.pdf] https://en.wikipedia.org/wiki/Purely_functional_data_structure https://en.wikipedia.org/wiki/Purely_functional_data_structu...
- KPGv2 10mo ago
  Okasaki's is basically the Bible for this stuff. Anyone writing data structure libraries in a functional language will have read this or have it on their to-read list.
  - zelphirkalt 10mo ago