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

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)