Huffman coding comparison

Philippe Sigaud philippe.sigaud at gmail.com
Sat May 29 12:25:41 PDT 2010


On Sat, May 29, 2010 at 03:27, bearophile <bearophileHUGS at lycos.com> wrote:

>Now and then it's very useful to compare how to write in D2 a small
interesting program
>written in another language, the comparison can help find problems,
possible improvements,
>performance problems, and so on.
>
>Time ago I have tried to convert to D2 a small Python program that finds
the Huffman encoding
> of a given string, but Phobos2 was not mature enough, and I didn't produce
a good enough D2 program.
>I have tried again and this time things are good enough.

(snip)

Hey, cool. And you made it generic to boot. I'd vote that to be put in
std.algorithm.


Simen kjaeraas:
>
> > I'm now so tired of hearing this, I started writing something that
> > does it:
>
>Now, granted, I have little to no experience with list comprehension,
>and as such this might not be what is needed. Still, it was fun to
>play around with, and I kinda like what it turned out as.

That's fun to see, the syntax is cool. I never thought of using operator
overloading for this.

I did a range comprehension also, a few months ago. It's called comp in
http://svn.dsource.org/projects/dranges/trunk/dranges/docs/algorithm2.html

Like yours, it takes any range and is lazy, the main difference it that it's
multirange: you can give it any number of range as input, it will create the
combinations of elements (aka product of ranges), filter it with the
predicate and map the generative function on it.

Syntax is     comp!(mappingFunction, predicate)(ranges...)

The classical example for Haskell list comprehension is generating the
pythagorean triplets:

pyth n = [ ( a, b, c ) | a <- [1..n],          -- Pythagorean Triples
                         b <- [1..n],
                         c <- [1..n],
                         a + b + c <= n,
                         a^2 + b^2 == c^2 ]


In my case, it would be:

auto pyth(int n)
{
    return comp ! ("tuple(a,b,c)", "a*a+b*b==c*c && a<b")
(iota(1,n),iota(1,n), iota(1,n));
}

pyth(11) -> (3,4,5), (6,8,10)


   Philippe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100529/c93fec51/attachment.html>


More information about the Digitalmars-d mailing list