What is the advantage of this circular implementation?<p>Is it faster than the simple one? Does it use less memory? Is it easier to write? Is it easier to understand?<p>I think all of the above is false, but I have a limited understanding of Haskell. Please correct me if I'm wrong.
> 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.<p>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?
There's no (practical) advantage to the circular implementation; it's just a curiosity.<p>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, <a href="https://link.springer.com/article/10.1007/BF00264249" rel="nofollow">https://link.springer.com/article/10.1007/BF00264249</a>) is a good start.
It'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.