/prog/ - 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-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                         )

Huffman Tree in LISP

1 Name: Anonymous 2010-12-30 1:10

40 Name: Anonymous 2010-12-31 6:58

Name: Anonymous 2010-12-30 1:10

Name: Anonymous 2010-12-31 6:58