* 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:
Anonymous2010-12-30 3:03
>>7
C++ understands "Definitions of huffman tree on the Web"?
>>9
Lisp understands something, because it mutates likeitisliving!
Name:
Anonymous2010-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:
Anonymous2010-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.
>>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.
Usage example: (huff "The algorithm for generating a Huffman tree is very simple.")
This runs in constant time and space.
Name:
Anonymous2010-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:
Anonymous2010-12-30 20:41
>>21 forEach(function (c) {f[c] |= 0; f[c]++});
looks like haskal code to me.
Name:
Anonymous2010-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.
>>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.
>>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.
>>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]
>>34
In Sepples |= does bitwise OR-ing, but to make >>21 code work, it needs to be logical OR.
Name:
Anonymous2010-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).
>>36 primitive operation for binary-searching
I'm sure Perl6 doesn't have an operator for that.
Name:
Anonymous2010-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:
Anonymous2010-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
>>41
If you're dealing with large association lists, you might as well use a hashtable or something more efficient, however for tiny ones, an alist would be faster.
Name:
Anonymous2010-12-31 8:35
>>42
Hashtables are inconvenient as you cant process them like lists.
"It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures." -- Alan Perlis
Consider memory latency. You can compute a hash with only one memory request and then some arithmetic which would likely be quicker than another memory access, so two requests are to be performed to fetch a value (more if you use buckets and there are collisions) while with assoc list you can only get the first value with two requests (or with one request if it is stored linearly)
>>49
Oh no, non-alphanumeric symbols in symbol names! Next you'll be complaining about whitespace being syntactically significant in Haskell and Python.
>>40
Stop calling it repl, idiot. Write a proper repl or rename this function to rep.
Name:
Anonymous2010-12-31 11:46
>>55
Long time ago it was real REPL, now it is implemented in hosted language itself, like follow
e:m:loop expr -> {=>do $expr (rec)}
repl -> (read).eval.pp.loop
Just for fags, I've a readable version, it looks verbose as fuck
uses crt;
type
ana= record
sayi, ytree :integer;
dur, yer :byte;
end;
var
A:array[1..50] of ana; Tree:array[1..512] of integer;
binary_dizi:array[1..10] of byte; toplam_dizi:array[1..200] of byte;
i,j,k,l,m,n,t,z,top,t_d:integer; ch:char;
Procedure oku;
begin
write('Size of array:');read(n);
for i:=1 to n do
begin
read(A[i].sayi);
end;
end;
Procedure BubbleSort;
var yedek:integer;
begin
for i:=1 to n-1 do
for j:=1 to n-i do
if A[j].sayi > A[j+1].sayi then
begin
yedek:=A[j].sayi;
A[j].sayi:=A[j+1].sayi;
A[j+1].sayi:=yedek;
end;
end;
Procedure Huffman_Tree;
begin
{******************Total Array**********************}
for i:=1 to 50 do a[i].dur:=0;
i:=1; z:=0;
while z=0 do
begin
top:=A[i].sayi+A[i+1].sayi;
k:=i+1;
t:=0;
while t=0 do
if (A[k].sayi<top)and(A[k].sayi<>0) then
inc(k)
else
begin
for l:=n+1 downto k+1 do
begin
A[l].sayi:=A[l-1].sayi;
A[l].dur:=A[l-1].dur;
end;
A[k].sayi:=top;
A[k].dur:=1;
t:=1;
inc(n);
A[k].yer:=i;
end;
inc(i,2);
if A[i+1].sayi=0 then z:=1;
end;
{------------------ Total Array ----------------------}
{******************Huffman Tree**********************}
Tree[1]:=A[n].sayi;A[n].ytree:=1;
Tree[2]:=A[A[n].yer].sayi; A[A[n].yer].ytree:=2;
Tree[3]:=A[A[n].yer+1].sayi;A[A[n].yer+1].ytree:=3;
for i:=n-1 downto 1 do
if A[i].dur=1 then
begin
j:=A[i].ytree;
t:=A[i].yer;
Tree[j+j]:=A[t].sayi;
A[t].ytree:=j+j;
Tree[j+j+1]:=A[t+1].sayi;
A[t+1].ytree:=j+j+1;
end;
{------------------Huffman Tree ----------------------}
end;
Procedure binary;
var yedek:integer;
begin
{******************Binary Code**********************}
for i:=1 to n do
begin
if A[i].dur=0 then
begin
j:=A[i].ytree;
k:=0;
while j>1 do
if (j mod 2)=0 then
begin
j:=j div 2;
inc(k);
binary_dizi[k]:=0;
end
else
begin
j:=(j-1) div 2;
inc(k);
binary_dizi[k]:=1;
end;
inc(k);
binary_dizi[k]:=1;
t:=k;
for j:=1 to (k div 2) do
begin
yedek:=binary_dizi[j];
binary_dizi[j]:=binary_dizi[t];
binary_dizi[t]:=yedek;
t:=t-1;
end;
write(A[i].sayi:3,'. number´s equivalent: ');
for j:=1 to k do
begin
write(binary_dizi[j]);
inc(t_d);
toplam_dizi[t_d]:=binary_dizi[j];
end;
writeln;
end;
end;
{------------------Binary Code----------------------}
end;
Procedure TotalArray;
begin
writeln(' Total array...');
for i:=1 to t_d do write(Toplam_dizi[i]); writeln;
end;
Procedure decode;
begin
{******************Conversion from Binary to number**********************}
writeln('From above array original numbers are generated...');
i:=2; j:=1;
while i<=t_d do
begin
if Toplam_dizi[i]=0 then
j:=j+j
else
j:=j+j+1;
if (Tree[j+j]=0)and(Tree[j+j+1]=0) then
begin
writeln('Number:', Tree[j]);
inc(i);
j:=1;
end;
inc(i);
end;
{------------------ Conversion from Binary to number----------------------}
end;
BEGIN
clrscr;
oku;
BubbleSort;
Huffman_Tree;
t_d:=0;
binary;
TotalArray;
decode;
repeat ch:=readkey; until ch=#27; {Press Esc for exit}
END.
Name:
Anonymous2011-01-02 0:09
J, the one of most cryptic and succinct languages in existence, still requires a good amout of code compared to 3 lines of >>13
hcodes=: 4 : 0
assert. x -:&$ y NB. weights and words have same shape
assert. (0<:x) *. 1=#$x NB. weights are non-negative
assert. 1 >: L.y NB. words are boxed not more than once
w=. ,&.> y NB. standardized words
assert. w -: ~.w NB. words are unique
t=. 0 {:: x hc w NB. minimal weight binary tree
((< S: 0 t) i. w) { <@(1&=)@; S: 1 {:: t
)
;"1":L:0(#/.~ (],.(<' '),.hcodes) ,&.>@~.)'this is an example for huffman encoding'
t 0 1 0 1 0
h 1 1 1 1 1
i 1 0 0 1
s 0 0 1 0
1 0 1
a 1 1 0 0
n 0 0 0
e 1 1 0 1
x 0 1 0 1 1
m 0 0 1 1
p 0 1 1 0 0
l 0 1 1 0 1
f 1 1 1 0
o 0 1 0 0
r 0 1 1 1 0
u 0 1 1 1 1
c 1 0 0 0 0
d 1 0 0 0 1
g 1 1 1 1 0
>>63
And both are a pain to read, and most likely a pain to write and debug. I'd rather take something which is easy to write and easy to understand/debug than some unreadable mess.
Name:
Anonymous2011-01-02 4:39
>>65
The >>13 code was pretty easy to write and required no debugging. It uses a stream processing approach, just like Unix BASH language ("|>" stands for usual "|" from bash), so I can easily decompose it into several simplier functions at expense of making it more verbose.
Name:
Anonymous2011-01-02 4:48
BTW, as anyone, who readed SICP, knows, you can use stream-processing for everything, if your Lisp-system supports generated lists with memoization.
Name:
Anonymous2011-01-02 4:51
>>67
So, one can even replace Unix with Lisp, making Lisp a self-sufficient operating system.
>>73
On LM's they used ZetaLisp (also known as Lisp Machine Lisp). ZL, and some other Lisps (including Scheme) contributed a lot to the development of ANSI Common Lisp. Common Lisp was created to unify current popular Lisp implementations, and given the package system, it's not that hard (or at least, they tried to make it that way) to take a CL-like dialect and mold it into a standards-compliant CL, so Genera/OpenGenera (Lisp Machine's OS) supported CL after standardization, and various newer parts of it were indeed written in CL instead of ZetaLisp. I'd say that if you know CL, you can read ZetaLisp without much trouble, at least if you try to read OpenGenera's source code, it's quite readable and an interesting piece of code to study. There are some major differences between CL and ZL, especially in the object system as ZL was made before CLOS (relatively new), so they mostly use the Flavours dialect for OO.
As for Gray Streams, they're not in the CL standard, but were proposed as a means of extending the streams using CLOS (similar to how MOP extends CLOS using CLOS). Gray streams kind of fall out naturally out of the design of CL, so I had no trouble at all using them, although most of the time I'm using other people's extensions which use gray streams (for things like in-memory streams, or streams which allow one to grab the data from disk or memory and then interpret it in some way, for example parsing unicode or various foreign encodings). Gray streams are mostly good, but they miss a few generic functions which one might find very useful, but those are supported (along with Gray Streams) by most major CL implementations, so it's not a big deal.
>>75
Actually you can easily make a stream class which filters (one way or both ways, if it's read/write) elements in a stream. Some libraries provide you with such functionality (portably), but you can easily implement it yourself. I don't see why I would want to mapcar it since it's not a list, and in general, lists are not an efficient way to store a stream (memory usage can be high, not very fast, seeking only works in one direction, unless you use a doubly linked list, but even then, it costs a lot of memory accesses). I use what's more suitable for the job, and using linked lists to store binary files or strings is rarely suitable. Lazy lists are a bit better, but they do come with costs as well. If you want to implement transparent encoding/compression/encryption/whatever, there are plenty of ways to do this using standard CL + gray streams (or use a library which already does it for you).