0

问题是：

“<em>列表的行程编码。利用问题P09的结果来实现所谓的游程编码数据压缩方法。元素的连续重复被编码为列表 (NE)，其中 N 是元素 E 的重复数。”</p>

预期结果是：

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

repl 说：

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

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

4

2 回答 2

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)
于 2021-07-19T11:18:49.897 回答
0

我是这样解决的。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
于 2021-07-19T03:19:14.003 回答