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.

The way that i'm thinking has flaws. Thanks, i realized my mistake and now i'm better in haskell. — João Paulo Andrade, Jul 19 '21 at 01:41
Always keep warnings turned on. The missing `[]` case in that way is reported by the compiler before the code is run. — chi, Jul 19 '21 at 07:55
i'm running haskell on jupyter notebook, it's easy to learn. — João Paulo Andrade, Jul 19 '21 at 08:05
They might just want to to re-use the function from previous Problem 9, and solve Problem 10 using 1) that function and 2) library function [`map`](https://hackage.haskell.org/package/base-4.15.0.0/docs/Prelude.html#v:map). — jpmarinier, Jul 19 '21 at 11:30

score 1 · Answer 1 · answered Jul 19 '21 at 11:18

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)

score 0 · Answer 2 · answered Jul 19 '21 at 03:19

0

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

answered Jul 19 '21 at 03:19

João Paulo Andrade

97
6

1

Your `isEmpty` function can be replaced by the [`null`](https://hackage.haskell.org/package/base-4.15.0.0/docs/GHC-List.html#v:null) library function. – jpmarinier Jul 19 '21 at 09:46
1

If optimization is of interest, you might note that there is a “low-hanging fruit” possible improvement: library function `dropWhile` counts the elements equal to x **for the second time**. – jpmarinier Jul 19 '21 at 10:36
1

if you're already using `dropWhile` why not also use `takeWhile` and process its output with `length`. – Will Ness Jul 19 '21 at 14:18
Or the OP can just use library function [span](https://hoogle.haskell.org/?hoogle=%28a+-%3E+Bool%29+-%3E+%5Ba%5D+-%3E+%28%5Ba%5D%2C%5Ba%5D%29&scope=set%3Astackage) instead of `dropWhile` and `takeWhile`. – jpmarinier Jul 19 '21 at 19:19

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

2 Answers2