LZW

lzw.hs

import Data.Maybe
import Data.Char
import Data.List

dictionary :: [String]
dictionary = [[chr x] | x <- [0..127]]

encode :: String -> [Int]
encode []     = []
encode (x:xs) = go dictionary [x] xs where  
    elemIndex' w = fromJust . elemIndex w
    
    go dict w []      = [elemIndex' w dict]
    go dict w (i:inp) =
        maybe
            (elemIndex' w dict : go (dict ++ [w']) [i] inp)
            (\_ -> go dict w' inp)
            (elemIndex w' dict)
        where w' = w ++ [i]            

decode :: [Int] -> String
decode = go dictionary where
    go dict []       = []
    go dict [i]      = dict !! i
    go dict (i:j:js) = out ++ go (dict ++ [out ++ [nxt]]) (j:js)
        where out = dict !! i
              nxt = case drop j dict of
                  (c:_):_ -> c
                  []      -> head out