Skip to content

Instantly share code, notes, and snippets.

Created Jun 22, 2015
What would you like to do?
Dabblings with Huffman encoding in Haskell
import Data.List (sortBy)
import Data.Ord (comparing)
import qualified Data.Map as M (Map, fromList)
data Freq a = V Int a | B Int (Freq a) (Freq a) deriving (Show)
size :: Freq a -> Int
size (V n _) = n
size (B n _ _) = n
freq :: (a,Int) -> Freq a
freq (x, n) = V n x
freqs :: [(a,Int)] -> Freq a
freqs = merge . map freq
where merge [x] = x
merge xs = merge $ sortBy (comparing size) $ merged xs
merged (x:y:ys) = B (size x + size y) x y : ys
huffs :: Freq a -> M.Map String a
huffs = M.fromList . huffs' ""
where huffs' s (V _ x) = [(reverse s, x)]
huffs' s (B _ x y) = huffs' ('0':s) x ++ huffs' ('1':s) y
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment