Haskell LZW compression

lzw.hs

-- Could use a few rounds of cleanup...

import Data.Char
import Data.List

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

prefixes :: [String] -> String -> [(Int, String)]
prefixes xs y = [(i, xs !! i) | i <- [0 .. (length xs) -1], xs !! i `isPrefixOf` y]

longest :: [(Int, String)] -> (Int, String)
longest xs = helper xs (0,"")
  where
    helper [] acc = acc
    helper (x:xs) acc
      | (length $ snd acc) < (length $ snd x) = helper xs x
      | otherwise = helper xs acc

step :: [String] -> String -> (Int, String, String)
step dict s = helper $ longest $ prefixes dict s
  where
    helper (idx, item) = (idx, item, drop (length item) s)

extend :: [String] -> String -> String -> [String]
extend dict _ [] = dict
extend dict matched s =
  let new_elem = matched ++ [head s] in
  if new_elem `elem` dict then dict else dict ++ [new_elem]

first (a, b, c) = a
second (a, b, c) = b
third (a, b, c) = c

reduce :: [String] -> String -> [Int]
reduce dict s = helper dict "" s []
  where
    helper dict _ "" acc = acc
    helper dict matched remaining acc = let
      step_result = step dict remaining
      extended_dict = (extend dict (second step_result) (third step_result))
      in
       helper extended_dict (second step_result) (third step_result) (acc ++ [first step_result])

compress :: String -> String
compress = map chr . reduce dictionary