Huffman Tree in LISP


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

>>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.