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

Building a data compression utility in Haskell using Huffman codes

lazamar.github.io

Post reply on HN
Print view View original

41–50 of 94 posts

Re: Building a data compression utility in Haskell using Huffman codes

#41

Post by lazamar »

bdahz wrote: post #34
lazamar wrote: post #30

Earlier quoted context omitted.

I’d say unbeatable! The goal was simplicity of implementation and code clarity. For this kind of thing I say Haskell performs the best.

For the simplicity of implementation and code clarity, I need to know how much I need to pay for it. If the Haskell implementation is 3x slower than C/C++/Rust implementation, it would be acceptable. If it's 30x slower, I would rather choose C/C++/Rust even the implementation won't be simple. If it is even possible to be 3x faster than C/C++/Rust, then why not the mainstream programmers adopt Haskell everywhere?

The goal of this implementation is not to be fast, but to be clear.

I am doing some inefficient things (like two pass encoding) on purpose to keep things simple and clear. So using this particular piece of code to judge a language's performance potential is not really the way to go here.

Re: Building a data compression utility in Haskell using Huffman codes

#42

Post by tossandthrow »

random3 wrote: post #38
benreesman wrote: post #20

Haskell is a really nice language. In general I don’t identify as an X programmer for any value of X: I tend to write in a half dozen languages daily and they all suck in their own special way. But on two separate occasions I made important career decisions with opportunity cost to work with highly lethal GHC contributors: those people are just really good. If Haskell sucks like all languages it’s because Haskell exc…

How do you distinguish data shuffling from computation? What’s actual computation from this perspective?

Philosophically speaking there is no difference.

What parent commenter probably refers to is that you think in terms of computations and not in terms of data units.

And that is just tremendously elegant.

Re: Building a data compression utility in Haskell using Huffman codes

#43

Post by lifthrasiir »

SassyBird wrote: post #36
lifthrasiir wrote: post #11

Earlier quoted context omitted.

Huffman codes are conceptually isomorphic to arithmetic codes where all probabilities are 2^-k with k integer, so they have an obvious disadvantage due to more inaccurate symbol distribution.

Hopefully k is natural. ;)

Implied because any symbol distribution which probabilities do not sum to 1 is invalid anyway ;-)

Re: Building a data compression utility in Haskell using Huffman codes

#44

Post by zarathustreal »

mrkeen wrote: post #33
lazamar wrote: post #30

Earlier quoted context omitted.

I’d say unbeatable! The goal was simplicity of implementation and code clarity. For this kind of thing I say Haskell performs the best.

That wasn't really the spirit of the question as I read it. 'Performance' has a narrower definition than that.

The point they’re making is that there is no performance without tradeoffs and “fast” is meaningless unless you define what you’re measuring. Asking the question implies a misunderstanding of the intent of the implementation, OP was trying to subtly let them know.

Re: Building a data compression utility in Haskell using Huffman codes

#45

Post by lucianbr »

random3 wrote: post #38
benreesman wrote: post #20

Haskell is a really nice language. In general I don’t identify as an X programmer for any value of X: I tend to write in a half dozen languages daily and they all suck in their own special way. But on two separate occasions I made important career decisions with opportunity cost to work with highly lethal GHC contributors: those people are just really good. If Haskell sucks like all languages it’s because Haskell exc…

How do you distinguish data shuffling from computation? What’s actual computation from this perspective?

Reading a row from a database and putting it on the screen, and reading some numbers from the keyboard and putting them in the database. These things I would not call computation. I mean sure, displaying needs to compute coordinates for where to light up pixels, but that's all already written. I just call it. Same with updating btrees when writing to the db.

I'm guessing if all you do is this kind of db - screen - keyboard and back stuff, haskell is not very useful, if not actively a hindrance.

Re: Building a data compression utility in Haskell using Huffman codes

#46

Post by agumonkey »

mjan22640 wrote: post #13
mrkeen wrote: post #8

There exists an array-based, in-place algorithm for this, reducing the need to allocate trees and chase pointers. I mention this only because, when I learned the tree-based approach at uni, I simply wasn't aware that there was another way to do it, and I'm wondering how many of you that's true for as well. While the tree approach is intuitive and illuminating, it probably makes more sense to work with in-place arrays…

> and I'm wondering how many of you that's true for as well the phrasing sounds like a list comprehension

true, tickles my brain in all kinds of funny ways

Re: Building a data compression utility in Haskell using Huffman codes

#48

Post by [deleted] »

benreesman wrote: post #20

Haskell is a really nice language. In general I don’t identify as an X programmer for any value of X: I tend to write in a half dozen languages daily and they all suck in their own special way. But on two separate occasions I made important career decisions with opportunity cost to work with highly lethal GHC contributors: those people are just really good. If Haskell sucks like all languages it’s because Haskell exc…

[deleted]

Re: Building a data compression utility in Haskell using Huffman codes

#49

Post by blandblender »

benreesman wrote: post #20

Haskell is a really nice language. In general I don’t identify as an X programmer for any value of X: I tend to write in a half dozen languages daily and they all suck in their own special way. But on two separate occasions I made important career decisions with opportunity cost to work with highly lethal GHC contributors: those people are just really good. If Haskell sucks like all languages it’s because Haskell exc…

> I tend to write in a half dozen languages daily

6 languages per day? Are they the same six the next day?

> they all suck in their own special way.

Not surprising if you're writing 6 different languages per day.

> Haskell excels at using computers to compute something

Can you please explain how Haskell computes medians more elegantly than say C?

Re: Building a data compression utility in Haskell using Huffman codes

#50

Post by agentultra »

mrkeen wrote: post #8

There exists an array-based, in-place algorithm for this, reducing the need to allocate trees and chase pointers. I mention this only because, when I learned the tree-based approach at uni, I simply wasn't aware that there was another way to do it, and I'm wondering how many of you that's true for as well. While the tree approach is intuitive and illuminating, it probably makes more sense to work with in-place arrays…

It’s mentioned at the end and left as an exercise to the reader.
Post reply on HN