10 ms·
What is the advantage of this circular implementation? Is it faster than the simple one? Does it use less memory? Is it easier to write? Is it easier to unders
by ptspts 9mo ago
What is the advantage of this circular implementation?
Is it faster than the simple one? Does it use less memory? Is it easier to write? Is it easier to understand?
I think all of the above is false, but I have a limited understanding of Haskell. Please correct me if I'm wrong.
- TacticalCoder 9mo ago> The algorithm isn’t single-pass in the sense of Adaptive Huffman Coding: it still uses the normal Huffman algorithm, but the input is transformed in the same traversal that builds the tree to transform it. Limited understanding here too. Sounds like it's not really single pass anyway so it's not usable to process a stream in real-time either, before having all the data?
- viraptor 9mo agoIt's a weird claim about a single pass too. It's more of a "let's replace some iteration with building a tree of functions to call" and then pretends waking/executing that is not another pass.
- oisdk 9mo agoThere's no (practical) advantage to the circular implementation; it's just a curiosity. It is useful for understanding laziness and some interesting theoretical tools for traversing data structures, though. For a more in-depth look at the idea of circular programs for traversal, Bird's paper (linked in the post, https://link.springer.com/article/10.1007/BF00264249 https://link.springer.com/article/10.1007/BF00264249) is a good start.