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) )
这是我的行程编码解决方案,任何人都可以建议我编写编码和解码函数的更好方法
您的许多代码都专用于更新累加器。您将元素添加到该累加器的尾部,这将对性能产生巨大影响。
通常这不是很有效的原因是因为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
或者我们可以使用列表单子代替:
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"
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句