Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Huffman Tree in LISP

Name: Anonymous 2010-12-30 1:10


huff xs -> xs.sort.{[x@xs ys:_:@{l=>l.lhd!=x}]=>[[x@xs] @ys.rec]}
           |> map x~>[x.len x.lhd] |> sort by={a b => a|0 < b|0}
           |> {[x]=>x|1;[a b @xs]=>nins a|0+b|0 [a|1 b|1] xs |> rec}
           |> {bs x=>[[x bs]]; bs [a b]=>conc rec,[@bs 0],a rec,[@bs 1],b} []
usage example:

(repl "huff \"The algorithm for generating a Huffman tree is very simple.\"")
((\y (0 0 0 0 0))   (\h (0 0 0 0 1))   (\m (0 0 0 1))   
 (\n (0 0 1 0))     (\t (0 0 1 1))     (\f (0 1 0 0))   
 (\g (0 1 0 1))     (\e (0 1 1))       (\u (1 0 0 0 0 0))
 (\v (1 0 0 0 0 1)) (\. (1 0 0 0 1 0)) (\H (1 0 0 0 1 1))
 (\T (1 0 0 1 0 0)) (\p (1 0 0 1 0 1)) (\l (1 0 0 1 1)) 
 (\o (1 0 1 0 0))   (\s (1 0 1 0 1))   (\a (1 0 1 1))   
 (\i (1 1 0 0))     (\r (1 1 0 1))     (\Space (1 1 1))  )

Name: Anonymous 2010-12-30 1:12

VALID PERL CODE

Name: Anonymous 2010-12-30 1:45

>>2
Try doing it in C/C++/Java, infindel!

Name: Anonymous 2010-12-30 1:51

With C++ it goes like that...

typedef { SimpleType, CompoundType } TypeOfNode;                         //<<<
class Node {
    private:                                                             //<<<
        TypeOfNode nodeType;                                             //<<<
    protected:
        int freq;
    public:
        Node() : nodeType(TypeOfNode nodetype) : nodeType(nodetype) { }  //<<<
        int getFreq(){
            return freq;
        }
        virtual char getChar() = 0;
        virtual Node * getLeft() = 0;
        virtual Node * getRight() = 0;
        void TransverseNodes(Node * thisNode);
};

class Simple_Node : public Node {
    private:
        char element;
    public:
        char getChar(){
            return element;
        }
 
        Simple_Node(char ch, int count) : Node(SimpleNode) { //<<<
            //Default freq is 1
            freq = count + 1;
            element = ch;
        }
 
        Node * getLeft(){
            return NULL;
        }
 
        Node * getRight(){
            return NULL;
        }
};

...

Name: Anonymous 2010-12-30 2:33

>>3
HuffmanTree t = new HuffmanTree(inputString);

Name: Anonymous 2010-12-30 2:49

>>5
define "HuffmanTree"

Name: Anonymous 2010-12-30 2:54

>>6
Definitions of huffman tree on the Web:

    * In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. ...
      en.wikipedia.org/wiki/Huffman_tree

Name: Anonymous 2010-12-30 3:03

>>7
C++ understands "Definitions of huffman tree on the Web"?

Name: Anonymous 2010-12-30 4:03

>>8
C++ understand nothing, it is a language not a living being.
You are a very strange fellow.

Name: Anonymous 2010-12-30 4:54

>>1
It's... beautiful. It has an operator for everything like Perl 6.

Name: Anonymous 2010-12-30 6:51

>>10
That may be, but it also expresses a higher code density than Perl6 could achieve. This is what makes haskal so mena.

Name: Anonymous 2010-12-30 6:57

>>9
Lisp understands something, because it mutates like it is living!

Name: Anonymous 2010-12-30 8:22

I just found that semantics of `by` keyword to `sort` should be changed to column selector, instead of comparator, so with a little rethinking code got compressed into 3 lines of 80 columns each.

huff xs -> xs.sort.{[x@xs ys:_:@(nb x)]=>[[xs.len+1 x] @ys.rec]}
           |> sort by=0 |> {[x]=>x|1;[a b @xs]=>nins a|0+b|0 [a|1 b|1] xs|>rec}
           |> {bs x=>[[x bs]]; bs [a b]=>conc rec,[@bs 0],a rec,[@bs 1],b} []

Name: Anonymous 2010-12-30 8:26

>>13
Note, that the last line just converts tree to more readable linear form, so it is unrelated to actual computation.

Name: Anonymous 2010-12-30 8:32

So... where's the Lisp?

Name: Anonymous 2010-12-30 8:54

Anyway, this `by` keyword is pretty neat...

(repl "class Person name age")
no
NIL
(repl "persons=:[10++(Person name=['Jacob 'Ethan 'Michael 'Isabella 'Emma 'Olivia].rand age=90.rand)]")
([:Person name=Jacob age=73]  [:Person name=Olivia age=21]
 [:Person name=Olivia age=59] [:Person name=Jacob age=16]
 [:Person name=Jacob age=49]  [:Person name=Olivia age=78]
 [:Person name=Emma age=13]   [:Person name=Ethan age=29]
 [:Person name=Michael age=2] [:Person name=Ethan age=32] )
NIL
(repl "sort by=age persons")
([:Person name=Michael age=2] [:Person name=Emma age=13] 
 [:Person name=Jacob age=16]  [:Person name=Olivia age=21]
 [:Person name=Ethan age=29]  [:Person name=Ethan age=32]
 [:Person name=Jacob age=49]  [:Person name=Olivia age=59]
 [:Person name=Jacob age=73]  [:Person name=Olivia age=78])
NIL
(repl "sort by=name persons")
([:Person name=Emma age=13]   [:Person name=Ethan age=29]
 [:Person name=Ethan age=32]  [:Person name=Jacob age=73]
 [:Person name=Jacob age=16]  [:Person name=Jacob age=49]
 [:Person name=Michael age=2] [:Person name=Olivia age=21]
 [:Person name=Olivia age=59] [:Person name=Olivia age=78])

Name: Anonymous 2010-12-30 9:40

>>16
EXPERT HASQL PROGRAMMER

Name: Anonymous 2010-12-30 13:28

>>15
His language (the one he invented) is supposedly written on top of CL, but he refuses to give it a name, and instead posts "*whatever in LISP" threads.

Name: Anonymous 2010-12-30 15:56

>>18
The language name is ``in LISP''.

Name: Anonymous 2010-12-30 19:29

>>19
on LISP

Name: Anonymous 2010-12-30 20:28

Huffman Tree in C++

function huff(str) {
    var f = {}, cs = str.split(''), h = new MinHeap(), r = [];
    cs.forEach(function (c) {f[c] |= 0; f[c]++});
    for (c in f) h.push([f[c], c]);
    while (h.length > 1)
        h.push((function (x, y) [x[0] + y[0], [x, y]])(h.pop(), h.pop()));
    (function (e, p) {var [f, c] = e; if (c instanceof Array) { let s = arguments.callee; s(c[0], p + '0'); s(c[1], p + '1') } else r.push([c, p]);})(h.pop(), '');
    return r;
}
usage example:
huff("The algorithm for generating a Huffman tree is very simple.");

[["y","00000"],  [".","000010"], ["H","000011"],
 ["f","0001"],   ["g","0010"],   ["m","0011"],
 ["n","0100"],   ["t","0101"],   ["e","011"],
 ["T","100000"], ["p","100001"], ["u","100010"],
 ["v","100011"], ["h","10010"],  ["l","10011"],
 ["o","10100"],  ["s","10101"],  ["a","1011"],
 [" ","110"],    ["i","1110"],   ["r","1111"]]

Name: Anonymous 2010-12-30 20:35

(define huff (lambda (str) '(("y" . "00000") ("." . "000010") ("H" . "000011") ("f" . "0001") ("g" . "0010") ("m" . "0011") ("n" . "0100") ("T" . "100000") (p . "100001") ("u" . "100010") ("v" . "100011") ("h" . "10010") ("l" . "10011") ("o" . "10100") ("s" . "10101") ("a" . "1011") (" " . "110") ("i" . "1110") ("r" . "1111"))))

Usage example:
(huff "The algorithm for generating a Huffman tree is very simple.")

This runs in constant time and space.

Name: Anonymous 2010-12-30 20:39

>>21
while (h.length > 1) h.push((function (x, y) [x[0] + y[0], [x, y]])(h.pop(), h.pop()));
looks like assembly code to me.

Name: Anonymous 2010-12-30 20:41

>>21
forEach(function (c) {f[c] |= 0; f[c]++});
looks like haskal code to me.

Name: Anonymous 2010-12-30 20:51

>>24
No, this code is pretty sepples, but JavaScript has operator for everything, just like Perl.  The "|="-smile probably checks if Heap element isnt NIL.

Name: Anonymous 2010-12-30 20:57

>>25
JavaScript doesn't have the sub infix:<`fibs`>{1,1,*+*...^*>=100} operator.

Name: Anonymous 2010-12-30 21:00

>>26
I feel sorry for JS, it isnt cutting-edge enough :-(

Name: Anonymous 2010-12-30 21:01

>>25
``operator for everything'' refers to Perl6, which has hundreds upon hundreds of builtin operators (plus the option to define more).  Supporting little more than the typical C ops doesn't count.

Name: Anonymous 2010-12-30 21:06

>>28
I know that because I invented and forced that meme (seriously).

Name: Anonymous 2010-12-30 21:11

>>29
It's still relatively new, I wouldn't call it a meme just yet. Please post the source to the BBCode, though, it's much less obnoxious than some of the others.

Name: Anonymous 2010-12-30 21:14

SexpCode:
{b.u.i.o.s.m.sup.sub.code everything}{i !}
BBCode:
[b][u][i][o][s][m][sup][sub][code]everything[/sub][/sup][/m][/s][/o][/i][/u][/b]![/code]

Name: Anonymous 2010-12-30 21:26

>>31
I missed an [aa]
{b.u.i.o.s.m.aa.sup.sub.code everything}{i !}
[b][u][i][o][s][m][aa][sup][sub][code]everything[/code][/sub][/sup][/aa][/m][/s][/o][/i][/u][/b][i]![/i]

Test: everything!

Name: Anonymous 2010-12-30 23:40

>>21
This is not Sepples; notice the |= operator

Name: Anonymous 2010-12-31 3:03

>>33
Sepples has a |= operator, silly.

Name: Anonymous 2010-12-31 3:25

>>34
In Sepples |= does bitwise OR-ing, but to make >>21 code work, it needs to be logical OR.

Name: Anonymous 2010-12-31 3:32

>>35
Anyway, in my Lisp-dialect, addition treats NIL as 0, so I can write

length [x@xs] -> 1+xs.length
or, to simulate >>21 style, just

ncng c ?+1 f
ncng is a primitive operation for binary-searching and modification sorted b-tree lists in log2(n).

Name: Anonymous 2010-12-31 3:45

>>36

(repl "do cs:[] (fe (ncng ? ?+1 !cs) \"The algorithm for generating a Huffman tree is very simple.\") cs")
((\Space 9) (\. 1) (\H 1) (\T 1) (\a 4) (\e 7)
 (\f 3)     (\g 3) (\h 2) (\i 4) (\l 2) (\m 3)
 (\n 3)     (\o 2) (\p 1) (\r 5) (\s 2) (\t 3)
 (\u 1)     (\v 1) (\y 1)                     )

Name: Anonymous 2010-12-31 6:48

>>36
primitive operation for binary-searching
I'm sure Perl6 doesn't have an operator for that.

Name: Anonymous 2010-12-31 6:55

>>38
Internaly lists are implemented as trees, so most operations on them (like catenation and cutting) are primitive, just like "car" and "cdr" in traditional lisps.

Name: Anonymous 2010-12-31 6:58

Another example (taken from Wikipedia SQL article)

join a b by=0 -> fold {r x=>keep ?.by==x.by b |> map [x ?] |> conc r} [[]@a]

(repl "class Employee name departmentId
class Department name departmentId

employees =: (map [n i]~>(Employee name=n departmentId=i)
                  [['Rafferty 31] ['Jones 33] ['Steinberg 33]
                   ['Robinson 34] ['Smith 34] ['John no]])

departments =: (map [n i]~>(Department name=n departmentId=i)
                    [['Sales 31] ['Engineering 33] ['Clerical 34] ['Marketing 35]])

join employees departments by=departmentId |> map [a b]~>#(`:` $a.name $b.name)")
no
no
([:Employee name=Rafferty departmentId=31]
 [:Employee name=Jones departmentId=33]
 [:Employee name=Steinberg departmentId=33]
 [:Employee name=Robinson departmentId=34]
 [:Employee name=Smith departmentId=34]
 [:Employee name=John departmentId=no])
([:Department name=Sales departmentId=31]
 [:Department name=Engineering departmentId=33]
 [:Department name=Clerical departmentId=34]
 [:Department name=Marketing departmentId=35])
(Rafferty:Sales    Jones:Engineering Steinberg:Engineering
 Robinson:Clerical Smith:Clerical                         )
Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -