From: Darius Bacon <darius@ac...> - 2003-09-13 09:30:37
Kicking this off with something simple -- I translated the run-length
coder from Kernighan & Plauger's _Software Tools_ to Haskell (a
language I have little experience in), and I have mixed feelings about
encode :: [Char] -> [Char]
encode cs = coding  cs
coding buf  = flush buf 
coding buf (c:cs) = findRun buf c cs 1
findRun buf c (d:cs) nrep | d == c && nrep < 255 = findRun buf c cs (nrep + 1)
findRun buf c cs nrep | nrep < 5 = append buf nrep c cs
| otherwise = flush buf ('\0' : c : chr nrep : encode cs)
append buf 0 _ cs = coding buf cs
append buf n c cs = more (n - 1) (buf ++ [c])
where more n' buf' | length buf' < 255 = append buf' n' c cs
| otherwise = flush buf' (append  n' c cs)
flush  rest = rest
flush buf rest = chr (length buf) : buf ++ rest
decode :: [Char] -> [Char]
-- Decode a run-length-encoded string.
decode  = 
decode ('\0':c:n:cs) = replicate (ord n) c ++ decode cs
decode (n:cs) = x ++ decode y where (x, y) = splitAt (ord n) cs
It's shorter than K&P's, but has some ugly inefficiencies (like buf++[c]).
Maybe this ought to use a state monad and imitate K&P's imperative code?