Haskell实现列表从右起隔位翻倍的doubleDigits函数问题

需求说明 #

需实现类型签名如下的函数：

doubleDigits :: [Integer] -> [Integer]

函数执行规则：

• 从列表最右端开始，每隔一位对数字执行翻倍操作
• 首个处理位为倒数第二位，之后依次处理倒数第四位、倒数第六位……直到遍历完全部元素

对应测试用例：

输入：doubleDigits [1,2,3,4,5,6,7]
输出：[1,4,3,8,5,12,7]

实现思路 #

由于需要从列表尾部开始计数定位待翻倍的位置，直接正向遍历很难快速匹配位置，因此采用「两次反转」的处理逻辑：

1. 先将原列表反转，此时原列表的倒数第一位变为反转列表的第一位，原列表倒数第二位变为反转列表的第二位
2. 遍历反转列表，从第二位开始隔位做翻倍操作
3. 处理完成后再次反转列表，即可得到符合规则的结果
   遍历过程中用一个二进制标记位记录当前位是否需要翻倍，每处理完一位就翻转标记状态。

完整实现代码 #

-- 配套工具函数：将正整数转换为逆序排列的数字列表
toDigitsReverse :: Integer -> [Integer]
toDigitsReverse n = reverse (toDigits n)

-- 遍历辅助函数：传入待处理列表、当前位是否翻倍的标记位，返回处理后的逆序列表
doubleDigitsHelper :: [Integer] -> Integer -> [Integer]
doubleDigitsHelper l t
    | l == [] = []
    | t == 0 = head l : doubleDigitsHelper (tail l) 1
    | t == 1 = 2 * head l : doubleDigitsHelper (tail l) 0

-- 主函数入口
doubleDigits :: [Integer] -> [Integer]
doubleDigits l = reverse (doubleDigitsHelper (reverse l) 0)

逻辑验证 #

以测试用例输入[1,2,3,4,5,6,7]为例：

1. 原列表反转后得到[7,6,5,4,3,2,1]
2. 辅助函数初始标记位为0（第一位不翻倍），逐位处理后得到中间结果[7,12,5,8,3,4,1]
3. 中间结果反转后得到[1,4,3,8,5,12,7]，和预期输出完全一致。

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