Anonymous user
Huffman coding: Difference between revisions
added Haskell
m (Fixed lang tags.) |
(added Haskell) |
||
Line 290:
#\r 1/39 #*00000
#\Space 2/13 #*111</pre>
=={{header|Haskell}}==
Credits go to [http://www.haskell.org/haskellwiki/99_questions/46_to_50 huffman] where you'll also find a non-tree solution.
<lang haskell>import Data.List
import Control.Arrow
import Control.Monad
import Data.Maybe
import Data.Ord
data HTree a = Leaf a | Branch (HTree a) (HTree a)
deriving (Show, Eq, Ord)
freq :: (Ord a) => [a] -> [] (Int, a)
freq = map(length &&& head). takeWhile(not.null). unfoldr (Just. (partition =<< (==). head))
serialize :: HTree d -> [] (d, String)
serialize (Branch l r) = map (second('0':)) (serialize l) ++ map (second('1':)) (serialize r)
serialize (Leaf x) = [(x, "")]
htree :: (Ord t, Num t) => [] (t, HTree a) -> HTree a
htree [(_, t)] = t
htree ((w1,t1):(w2,t2):wts) =
htree $ insertBy (comparing fst) (w1 + w2, Branch t1 t2) wts
huffman :: (Ord a, Ord w, Num w) => [] (w, a) -> [] (a, String)
huffman = serialize. htree. map (second Leaf)</lang>
Example output:
<lang haskell>*Main> mapM_ (putStrLn.uncurry((.(' ':)).(:))). huffman $ freq "this is an example for huffman encoding"
s 000
t 00100
h 00101
i 0011
010
a 011
r 10000
u 10001
g 10010
c 100110
d 100111
f 1010
o 1011
p 11000
l 11001
x 11010
m 11011
n 1110
e 1111</lang>
=={{header|J}}==
| |||