Huffman coding: Difference between revisions

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

<lang haskell>import Data.List (group, insertBy, sort, sortBy)

import Control.Arrow

import Control.Arrow ((&&&), second)

import Data.Ord

import Data.Ord (comparing)

data HTree a

Line 2,702:

test :: String -> IO ()

test =

mapM_ (\(a, b) -> putStrLn ('\'' : a : "\' : " ++ b)) .

mapM_ (\(a, b) -> putStrLn ('\'' : a : ("' : " ++ b))) .

serialize . huffmanTree . freq

Line 2,715:

huffmanTree =

snd .

head . until (null . tail) hstep . sortBy (comparing fst) . (second Leaf ~~<$>~~)

head . until (null . tail) hstep . sortBy (comparing fst) . fmap (second Leaf)

hstep

Line 2,726:

:: Ord a

=> [a] -> [(Int, a)]

freq = ((length &&& head~~) <$>~~) . group . sort~~</lang>~~

freq = fmap (length &&& head) . group . sort

main :: IO ()

main = test "this is an example for huffman encoding"</lang>

<lang haskell>*Main> ~~test~~ ~~"this is an example for huffman encoding"~~

<lang haskell>'p' : 00000

'p' : 00000

'r' : 00001

'g' : 00010