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

Why recursive data structures?

raganwald.com

Post reply on HN
Print view View original

41–50 of 129 posts

Re: Why recursive data structures?

#41

Post by mypalmike »

stan_rogers wrote: post #26
mypalmike wrote: post #24

Earlier quoted context omitted.

Pretentious or not, the term is used erroneously here. Recursive data structures and recursive algorithms are, quite plainly, not isomorphic. They are not two equivalent representations of the same thing. Something that is isomorphic to a recursive function that works on a quadtree would be an imperative function that works on a quadtree with identical functionality. tl;dr: I think the author meant "synergistic".

"Isomorphic" literally means "of the same shape".

Even with a non-mathematical definition such as yours, I don't see the isomorphism. Recursive code that acts on a quadtree does not itself take the shape of a quadtree. Not the text, not the AST, not the machine code.

The code is treelike, but that's because all code is treelike(1).

As a counterexample, consider code that acts on arbitrary graphs. DFS on an arbitrary graph doesn't itself take the form of an arbitrary graph. It is still treelike.

(1) My old Atari 800 BASIC programs notwithstanding.

Re: Why recursive data structures?

#42

Post by Ericson2314 »

nitrix wrote: post #37

I stopped reading at the first sentence when he improperly used `isomorphic`. I thought it made no sense at all so I looked up the footnote... just to get a big middle finger from the author. What a con artist. Moving on.

If you suspend your disbelief until the end, it's an inductive anti-hypothesis. Induction is recursion under intuitionism.

Re: Why recursive data structures?

#43

Post by Bahamut »

greydius wrote: post #28
mypalmike wrote: post #24

Earlier quoted context omitted.

Pretentious or not, the term is used erroneously here. Recursive data structures and recursive algorithms are, quite plainly, not isomorphic. They are not two equivalent representations of the same thing. Something that is isomorphic to a recursive function that works on a quadtree would be an imperative function that works on a quadtree with identical functionality. tl;dr: I think the author meant "synergistic".

> They are not two equivalent representations of the same thing. Algorithms encoded as a program end up as an abstract syntax tree in the compiler. Algorithm -> Data structure. The compiler then turns that ast into some other representation (e.g. machine instructions, JavaScript) which is again the algorithm. Data structure -> algorithm. Bijection identified.

An isomorphism is more than a bijection, unless it is between sets and the category is the one of all functions from one set to another.

Isomorphism is about preserving relations as well. For example, consider the ring of integers and the field of rational numbers. One can construct a bijection between one to the other (they both have the same cardinality as the natural numbers), but they are significantly different constructs. The bijection would not be able to preserve the operations - in fact, the rational numbers as a ring is significantly different, and unless one wants to use information about the cardinality, a bijection between the two is otherwise worthless.

Re: Why recursive data structures?

#45

Post by braythwayt »

mypalmike wrote: post #41
stan_rogers wrote: post #26

Earlier quoted context omitted.

"Isomorphic" literally means "of the same shape".

Even with a non-mathematical definition such as yours, I don't see the isomorphism. Recursive code that acts on a quadtree does not itself take the shape of a quadtree. Not the text, not the AST, not the machine code. The code is treelike, but that's because all code is treelike(1). As a counterexample, consider code that acts on arbitrary graphs. DFS on an arbitrary graph doesn't itself take the form of an arbitrary…

I was speaking to the relationship between the code's runtime behaviour and the structure of the data.

When I say the word "algorithm," am I talking about the way the code is noted in a particular language? Or the steps one takes to perform the operation?

Re: Why recursive data structures?

#46

Post by bpicolo »

cousin_it wrote: post #29

Quadtrees are neat. Though I guess general purpose image processing would be better served by either raster or vector representation. Maybe a better showcase would be something like collision detection or geospatial indexing.

(You probably know this but) quadtrees are indeed used extensively for both of those things.

Whole buncha programs can use them (though there are other good options as well) for geospatial:

https://www.elastic.co/guide/en/elasticsearch/reference/curr...

Re: Why recursive data structures?

#47

Post by greydius »

Bahamut wrote: post #43
greydius wrote: post #28

Earlier quoted context omitted.

> They are not two equivalent representations of the same thing. Algorithms encoded as a program end up as an abstract syntax tree in the compiler. Algorithm -> Data structure. The compiler then turns that ast into some other representation (e.g. machine instructions, JavaScript) which is again the algorithm. Data structure -> algorithm. Bijection identified.

An isomorphism is more than a bijection, unless it is between sets and the category is the one of all functions from one set to another. Isomorphism is about preserving relations as well. For example, consider the ring of integers and the field of rational numbers. One can construct a bijection between one to the other (they both have the same cardinality as the natural numbers), but they are significantly different…

Correct. A bijection implies isomorphism in the category of sets. Thus an isomorphism exists. I suppose we need to convince ourselves that algorithms and abstract syntax trees do indeed form sets. (Exclude such things as "the algorithm that computes the set of all algorithms", etc.)

Re: Why recursive data structures?

#48

Post by skybrian »

Before reading this, I would have said that we need to use recursion to model constructs like programming languages that are specifically designed to have a recursive structure. They are naturally recursive because someone designed the language that way. (By contrast, building a basic database-backed website doesn't require any recursion, unless you're modeling a hierarchy.)

But with a compiler, there is the same pattern of converting to a recursive data structure (parsing), performing manipulations, and then converting back to a non-recursive structure (object code generation).

Re: Why recursive data structures?

#49

Post by Const-me »

Apparently, every computer science problem has easy to understand solution that’s easy to implement but awfully slow in practice.

This is one of them.

Rotating images that way isn’t CPU bound problem. It’s RAM bandwidth and RAM latency bound problem. The optimal data structure for that is not recursive, it’s 2D array of small square blocks of pixels. If pixels are bits, I’d bet on either 8x8 or 16x16 blocks. If they are RGB, one good format for those images, optimized for rotations, is BC7 https://www.opengl.org/registry/specs/ARB/texture_compressio... the decompressor being implemented right in the graphics hardware.

> If we were writing an image manipulation application, we’d provide much snappier behaviour using coloured quadtrees to represent images on screen.

That statement was true 30 years ago, no longer a case. Branch misprediction is expensive, memory latency is huge, RAM is a block device now (the block size typically being 16 bytes for dual-channel DDR). In addition, some displays now show 8+ megapixels, and most show 16M colors.

For an image manipulation application, that recursive thing ain’t good at all.

Re: Why recursive data structures?

#50

Post by Bahamut »

greydius wrote: post #47
Bahamut wrote: post #43

Earlier quoted context omitted.

An isomorphism is more than a bijection, unless it is between sets and the category is the one of all functions from one set to another. Isomorphism is about preserving relations as well. For example, consider the ring of integers and the field of rational numbers. One can construct a bijection between one to the other (they both have the same cardinality as the natural numbers), but they are significantly different…

Correct. A bijection implies isomorphism in the category of sets. Thus an isomorphism exists. I suppose we need to convince ourselves that algorithms and abstract syntax trees do indeed form sets. (Exclude such things as "the algorithm that computes the set of all algorithms", etc.)

But that is typically not how the word is used because to substitute bijection with isomorphism, it would only make sense when talking about cardinality - that is not how you used it.
Post reply on HN