Folds implementation in Haskell

Question

I am having LOTS of problem trying to understand folds implementation on Haskell. I need to have two functions using fold that have this output

> runLengthEncode "aaaaaaabbb"
[(7,'a'),(3,'b')]
> runLengthDecode [(1,'h'), (5,'i')]
"hiiiii"

So what I did is to write the function first as I would do with pattern matching (they work), but now I do not know how to "translate" that using either fold left or fold right.

runLengthEncode :: String -> [(Int,Char)]
runLengthEncode [] = []
runLengthEncode (x:xs) = runLengthEncode 1 x xs
    where
        runLengthEncode n x [] = [(n,x)]
        runLengthEncode n x (y:ys) | x == y = runLengthEncode (n + 1) y ys
                                   | otherwise = (n,x) : runLengthEncode 1 y ys

runLengthDecode :: [(Int,Char)] -> String
runLengthDecode [] = []
runLengthDecode ((a,b):xs) = replicate a b ++ (runLengthDecode xs)

Answer 1

Think of a fold as taking a list of terms:

[a,b,c,d]

and adding an initial value zz and binary operator <+> between the terms:

foldl (<+>) zz [a,b,c,d] = (((zz <+> a) <+> b) <+> c) <+> d
foldr (<+>) zz [a,b,c,d] = a <+> (b <+> (c <+> (d <+> zz)))

Note that the initial value is also the value the fold will have when applied to an empty list, so that's usually easy to figure out. The hard part is defining the appropriate binary operator.

So, to express runLengthEncode as right fold, you need:

'a' <+> ('a' <+> ('a' <+> ('b' <+> zz))) = [(3,'a'),(1,'b')]

for an operator <+> and some initial value zz.

We can easily "solve" for zz because we know that runLengthEncode [] = [], so zz = []. We need to define <+> so that it satifies equations derived from the example above (working right to left) like:

'b' <+> [] = [(1, 'b')]
'a' <+> [(1, 'b')] = [(1, 'a'), (1, 'b')]
'a' <+> [(1, 'a'), (1, 'b')] = [(2, 'a'), (1, 'b')]
'a' <+> [(2, 'a'), (1, 'b')] = [(3, 'a'), (1, 'b')]

Defining such an operator is actually pretty easy:

(<+>) :: Char -> [(Int, Char)] -> [(Int, Char)]
x <+> ((n, y) : rest) | x == y = ((n+1), y) : rest
x <+> rest                     = (1, x) : rest

so we get:

runLengthEncode' :: String -> [(Int,Char)]
runLengthEncode' = foldr (<+>) []

Try doing this with a left fold, too:

(((zz + 'a') <+> 'a') <+> 'a') <+> 'b' =>  [(3,'a'),(1,'b')]

You'll find that when it comes time to define <+>, you have to inspect the last element of the current RLE instead of the first. It can be done, of course, but it's slightly less natural, which is why I used a right fold above.

For runLengthDecode, it's the same business:

(1, 'h') <+> ((5, 'i') <+> zz) = "hiiiii"

Again, determine what zz should be. Then, figure out how you write a binary operator to solve:

(5, 'i') <+> zz = "iiiii"
(1, 'h') <+> "iiiii" = "hiiiii"

Spoilers follow...

Of course, you don't actually need to use an operator syntax, so a full solution would look like:

runLengthEncode'' :: String -> [(Int,Char)]
runLengthEncode'' = foldr step []
  where step x ((n, y) : rest) | x == y = ((n+1), y) : rest
        step x rest                     = (1, x) : rest

runLengthDecode'' :: [(Int,Char)] -> String
runLengthDecode'' = foldr step ""
  where step (n, x) str = replicate n x ++ str