Huffman coding: Difference between revisions
Content added Content deleted
m (→{{header|zkl}}: update) |
m (→{{header|Haskell}}: ( Generalising map to fmap (<$>) for marginally more readability )) |
||
Line 2,690: | Line 2,690: | ||
=={{header|Haskell}}== |
=={{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. |
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 |
<lang haskell>import Data.List |
||
import Control.Arrow |
import Control.Arrow |
||
import Data.Ord |
import Data.Ord |
||
data HTree a |
data HTree a |
||
= Leaf a |
|||
⚫ | |||
| Branch (HTree a) |
|||
(HTree a) |
|||
⚫ | |||
test :: String -> IO () |
test :: String -> IO () |
||
test = |
|||
test s = mapM_ (\(a,b)-> putStrLn ('\'' : a : "\' : " ++ b)) |
|||
mapM_ (\(a, b) -> putStrLn ('\'' : a : "\' : " ++ b)) . |
|||
serialize . huffmanTree . freq |
|||
serialize :: HTree a -> [(a, String)] |
serialize :: HTree a -> [(a, String)] |
||
serialize (Branch l r) = |
serialize (Branch l r) = |
||
(second ('0' :) <$> serialize l) ++ (second ('1' :) <$> serialize r) |
|||
serialize (Leaf x) |
serialize (Leaf x) = [(x, "")] |
||
huffmanTree |
huffmanTree |
||
:: (Ord w, Num w) |
|||
huffmanTree = snd . head . until (null.tail) hstep |
|||
=> [(w, a)] -> HTree a |
|||
⚫ | |||
huffmanTree = |
|||
snd . |
|||
⚫ | |||
hstep |
|||
⚫ | |||
:: (Ord a, Num a) |
|||
⚫ | |||
⚫ | |||
hstep ((w1, t1):(w2, t2):wts) = |
|||
⚫ | |||
freq |
|||
⚫ | |||
:: Ord a |
|||
⚫ | |||
⚫ | |||
⚫ | |||
{{out}} |
{{out}} |
||
<lang haskell>*Main> test "this is an example for huffman encoding" |
<lang haskell>*Main> test "this is an example for huffman encoding" |