Haskell用FOLDR单遍实现字符串游程编码，禁止使用(++)操作符

问题分析 #

你现有代码的核心问题是对foldr的累加值结构认知错误：你在lambda中将累加值仅匹配为单元素列表[(symbol, count)]，既丢弃了累加列表中已生成的多组连续字符统计结果，也没有在字符不匹配时将当前字符作为新的统计项加入列表，自然无法得到完整结果。

实现思路 #

要求用foldr单遍遍历、不使用(++)操作符，刚好可以利用foldr从右向左遍历的特性：

• 累加值存储已经处理完成的右侧字符串的连续字符统计元组列表
• 每次处理当前字符时，仅需要和累加列表的第一个元素的字符做比对：
  • 字符相同则累加第一个元素的计数，其余列表内容保持不变
  • 字符不同则将当前字符对应的新元组(c, 1)直接追加到累加列表头部，用(:)操作符即可完成，完全不需要(++)

正确实现代码 #

task2 :: String -> [(Char, Int)]
-- 处理空字符串边界
task2 [] = []
task2 str = foldr step [] str
  where
    -- 累加列表为空时，直接插入当前字符的统计元组
    step c [] = [(c, 1)]
    -- 匹配累加列表的首个元素，其余部分保留
    step c allAcc@((sym, cnt):restAcc)
      | c == sym  = (sym, cnt + 1) : restAcc
      | otherwise = (c, 1) : allAcc

测试验证 #

输入task2 "aaaabbaab"即可得到预期结果[('a',4),('b',2),('a',2),('b',1)]。

内容的提问来源于stack exchange，提问作者Bohdan Chornopolskyi