Huffman coding: Difference between revisions
m
→{{header|Haskell}}: ( Generalising map to fmap (<$>) for marginally more readability )
m (→{{header|zkl}}: update) |
m (→{{header|Haskell}}: ( Generalising map to fmap (<$>) for marginally more readability )) |
||
Line 2,690:
=={{header|Haskell}}==
Credits go to [http://www.haskell.org/haskellwiki/99_questions/46_to_50#Problem_50 huffman] where you'll also find a non-tree solution. Uses sorted list as a priority queue.
<lang haskell>import Data.List
import Control.Arrow
import Data.Ord
data HTree a
= Leaf a
deriving (Show, Eq, Ord)▼
| Branch (HTree a)
(HTree a)
test :: String -> IO ()
test =
mapM_ (\(a, b) -> putStrLn ('\'' :
serialize . huffmanTree . freq
serialize :: HTree a -> [(a, String)]
serialize (Branch l r) =
(second ('0' :) <$> serialize l) ++ (second ('1' :) <$> serialize r)
serialize (Leaf x)
huffmanTree
:: (Ord w, Num w)
=> [(w, a)] -> HTree a
. sortBy (comparing fst) . map (second Leaf)▼
huffmanTree =
snd .
hstep
hstep :: (Ord a, Num a) => [(a, HTree b)] -> [(a, HTree b)]▼
:: (Ord a, Num a)
hstep ((w1,t1):(w2,t2):wts) = insertBy (comparing fst) (w1 + w2, Branch t1 t2) wts▼
hstep ((w1, t1):(w2, t2):wts) =
freq
freq :: Ord a => [a] -> [(Int, a)]▼
:: Ord a
freq = map (length &&& head) . group . sort</lang>▼
{{out}}
<lang haskell>*Main> test "this is an example for huffman encoding"
| |||