Recursion error at my encode function from “99 questions in Haskell”

Question

The problem is:

“Run-length encoding of a list. Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.”

The expected result is:

λ> encode "aaaabccaadeeee"
[(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]

I've created this code:

encode [] = []
encode (x:xs) = (counting xs,x) : encode (dropWhile (==x) xs )
 where counting (y:ys)
        | y == head ys = 1 + counting ys
        | otherwise = 0
           

The repl is saying:

 `<interactive>:(1,1)-(5,22): Non-exhaustive patterns in function encode`

I can't figure out where is my recursion mistake.

Answer 1

I solved this way. Conta is the couting function.

encode2 [] =[]
encode2 (x:xs) = (conta x (x:xs),x) : encode2 (dropWhile (==x) xs)
 where conta y (z:zs)
        | isEmpty zs && z == y = 1
        | isEmpty zs && z /= y = 0
        | z == y = 1+ contar y (zs)
        | z /= y =0
        | otherwise = 0
       isEmpty [] = True
       isEmpty [x] = False
       isEmpty (x:xs) = False

Answer 2

Your code (the one in your answer) is essentially fine. Just replace isEmpty by library function null.

Just a thing about optimization: function encode2 scans all elements twice. This is because the information about the location in the list of the first differing element is not preserved by conta, which returns just a count.

When people program this problem in their favorite imperative language, they certainly think of preserving a pointer to the rest of the list. It is just a little bit subtler in Haskell, but it can be done too.

The situation can be improved by having a version of counta that returns both the count and (a pointer to) the rest of the list. Like this:

-- Must return also a pointer to the rest of the input list:
extract :: Eq a => a -> Int -> [a] -> (Int, [a])
extract x0 n  []     =  (n,[])
extract x0 n (x:xs)  =  if (x==x0) then  extract x0 (n+1) xs
                                   else  (n, x:xs)

Testing under ghci:

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 λ> 
 λ> :load q68434019.hs
 Ok, one module loaded.
 λ> 
 λ> extract 'a' 0 "aaaabccaadeeee"
 (4,"bccaadeeee")
 λ> 
 λ> extract 'a' 0 ""
 (0,"")
 λ> 
 λ> extract 'z' 0 "aaaabccaadeeee"
 (0,"aaaabccaadeeee")
 λ> 
 λ> extract 'z' 42 "aaaabccaadeeee"
 (42,"aaaabccaadeeee")
 λ> 

With this tool in place, it is then easy to solve the problem using a single scan of the input list:

encode3 :: Eq a => [a] -> [(Int,a)]
encode3  []     =  []
encode3 (x:xs)  =  let  (count, rest) = extract x 1 xs
                   in   (count, x) : (encode3 rest)