Haskell中的运行长度编码

Question

import Data.List

data Encoding = Multiple Int Char | Single Char deriving (Eq,Show,Ord)

运行长度的编码

encode :: String -> [Encoding]
encode inputString =encoding (group inputString) []


encoding :: [String] -> [Encoding] -> [Encoding]
encoding groupString xs=
if (length groupString == 0)
    then xs
else
    case (head groupString) of
            ([c]) ->encoding (tail groupString)  (xs ++ [Single c])
            (x) -> encoding (tail groupString)  (xs ++ [Multiple (length x) (head x)])

运行长度的解码

decode :: [Encoding] -> String
decode listString = decoding listString []              

decoding :: [Encoding] -> String -> String
decoding inputString xs=
if (length inputString == 0)
    then xs
else
    case (head inputString) of
        (Single x) ->decoding (tail inputString) (xs++ [x])
        (Multiple num x) ->decoding (tail inputString) (xs ++ (replicate num x) )

这是我的运行长度编码解决方案,任何人都可以建议我更好的方式来编写编码和解码功能

Answer 1

您的许多代码专门用于更新累加器.您将元素添加到该累加器的尾部,这将对性能产生巨大影响.

这通常不是很有效的原因是因为Haskell中的列表[a]实现 - 至少在概念上 - 作为链表.结果连接两个列表l1并l2与之一起l1 ++ l2,将取O(| l1 |)时间(即元素的数量l1).这意味着如果列表已经包含100个元素,那么在最后添加一个额外元素将需要大量工作.

另一种反模式是使用head和tail.是的,这些功能可以使用,但不幸的是因为你不使用模式匹配,是可能发生的空列表被传递,然后head和tail会报错.

这里的另一个问题是你length在列表上使用.因为有时Haskell中的列表可以具有无限长度,所以length如果我们需要它,则调用将永远不会结束.

如果你必须在累加器的末尾附加,通常我们可以在我们正在构建的列表"cons"的尾部写入递归.所以我们可以改写我们的程序:

encode :: String -> [Encoding]
encode [] = []
encode (h:t)  = ...

现在的问题是我们如何计算这些价值观.我们可以使用span :: (a -> Bool) -> [a] -> ([a],[a])一个函数 - 对于给定的谓词和列表 - 构造一个2元组,其中第一个项目包含列表的前缀,其中所有元素都满足谓词,第二个项目包含列表的其余部分,所以我们可以这样使用:

encode :: String -> [Encoding]
encode [] = []
encode (h:t)  | nh > 1 = Multiple nh h : tl
              | otherwise = Single h : tl
    where (s1, s2) = span (h ==) t
          nh = 1 + length s1
          tl = encode s2

例如:

Prelude Data.List> encode "Foobaaar   qqquuux"
[Single 'F',Multiple 2 'o',Single 'b',Multiple 3 'a',Single 'r',Multiple 3 ' ',Multiple 3 'q',Multiple 3 'u',Single 'x']

对于解码,我们再次不需要累加器,并且可以使用replicate :: Int -> a -> [a]:

decode :: [Encoding] -> String
decode [] = []
decode (Single h:t) = h : decode t
decode (Multiple nh h) = replicate nh h ++ decode t

或者我们可以使用列表monad:

decode :: [Encoding] -> String
decode = (>>= f)
    where f (Single h) = [h]
          f (Multiple nh h) = replicate nh h

例如:

Prelude Data.List> decode [Single 'F',Multiple 2 'o',Single 'b',Multiple 3 'a',Single 'r',Multiple 3 ' ',Multiple 3 'q',Multiple 3 'u',Single 'x']
"Foobaaar   qqquuux"