"Haskell中的99个问题"中我的编码函数出现递归错误

Question

问题是：

">列表的行程编码。使用问题P09的结果来实现所谓的行程编码数据压缩方法。元素的连续重复被编码为列表(NE(，其中N是元素E的重复数。">

预期结果是：

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

我创建了这个代码：

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

回复说：

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

我不知道我的递归错误在哪里。

Answer 1

您的代码(答案中的代码(基本上是好的。只需将isEmpty替换为库函数null即可。

关于优化：函数encode2扫描所有元素两次。这是因为conta不保留第一个不同元素列表中位置的信息，它只返回一个计数。

当人们用他们最喜欢的命令式语言编程这个问题时，他们肯定会考虑保留一个指向列表其余部分的指针。这在Haskell中只是稍微微妙一点，但它也可以做到。

可以通过使用counta的版本来改善这种情况，该版本同时返回计数和(指向(列表其余部分的指针。像这样：

-- 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)

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")
λ> 

有了这个工具，只需对输入列表进行一次扫描就可以很容易地解决问题：

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

Answer 2

我用这种方法解决了问题。Conta是定制功能。

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