Haskell的游程长度编码功能

该编码函数需要下面的输出， code "aaccbbaa" = [('a',2),('c',2),('b',2),('a',2)Haskell的游程长度编码功能

然而，这是我的输出。 code "aaccbbaa" = [('a',4),('c',2),('b',2)]

这里是我的功能，

code :: Eq a => [a] -> [(a,Int)] 
code [] = [] 
code (x:xs) = [(x, length(filter(==x)(x:xs)))] ++ code(filter (/=x)(xs))

我如何让它讲述下一个字母字母出现了吗？

来源

2017-05-04 BCKN

我相信托马斯M DuBuisson评论一些伟大的事情较早，但得到的答复已被删除？ – BCKN

他删除了它，因为他意识到他正在回答的问题与您提出的问题不同。 – amalloy

有一个group功能Data.List

code :: Eq a => [a] -> [(a,Int)] 
code = map (\x -> (head x, length x)) . group

λ> code "aaccbbaa" 
[('a',2),('c',2),('b',2),('a',2)]

来源

2017-05-04 12:19:51 Kamel

这是非常简洁的编码。我刚刚查了一下group function，'group'aaccbbaa''outputs'[“aa”，“cc”，“bb”，“aa”]' – BCKN

带有辅助函数的foldr应该足以处理这项工作如下;

code :: Char -> [(Char,Int)] -> [(Char,Int)] 
code c [(_,0)] = [(c,1)] 
code c ((x,n):ts) | c == x = (x,n+1):ts 
        | otherwise = (c,1):(x,n):ts 

rle :: String -> [(Char,Int)] 
rle = foldr code [(' ',0)]

那么按你的意见，接受任何类型的Eq类的情况下，我们可以简化rle功能。另一方面，接受的答案涉及3次执行操作，如group,map和length。对于一次性使用它并不重要，但是如果你将某些单词或句子使用这个函数数百万次，那么我会建议下面这个只在列表中运行一次的单元。

rle :: Eq a => [a] -> [(a,Int)] 
rle = foldr code [] 
     where code c []   = [(c,1)] 
      code c ((x,n):ts) | c == x = (x,n+1):ts 
           | otherwise = (c,1):(x,n):ts

来源

2017-05-04 08:19:45 Redu

这也适用，并且更容易。但它改变了原始数据结构'code :: Eq a => [a] - > [（a，Int）]''。 – BCKN

@BCKN您是对的...我已根据您的需求更正了代码。它仅在O（n）时间内在列表中单次传递作业。 – Redu

Haskell的游程长度编码功能

回答

相关问题