Skip to content

Instantly share code, notes, and snippets.

@gfixler

gfixler/huff.hs

Created Jun 22, 2015
Embed
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