Haskell前缀和逆运算优化：是否有更简单高效的scan实现方案

现有实现的边界问题 #

你当前的实现存在几个可优化的边界点：

• 空列表输入会直接抛出异常：last []和init []都是非法操作
• 单元素输入返回结果不符合预期：比如输入[5]，预期逆运算结果为[5]，但你的实现会返回空列表
• 无法处理无限列表：调用last需要遍历到列表末尾，遇到无限前缀和列表会直接卡住
• 时间效率偏低：需要三次遍历列表（last、foldr、init），空间上也有额外的中间列表开销

更简单高效的实现 #

前缀和的逆运算逻辑非常直观：假设前缀和数组为s，原数组的第0项等于s[0]，第k项（k≥1）等于s[k] - s[k-1]，基于这个逻辑可以写出O(n)时间、单次遍历的实现，还支持惰性计算：

undo_prefix_sum :: Num a => [a] -> [a]
undo_prefix_sum [] = []
undo_prefix_sum s@(x:xs) = x : zipWith (-) xs s

测试验证

输入前缀和列表[1,3,6,10,15,21]，执行后输出[1,2,3,4,5,6]，完全符合预期。

• 空输入返回空列表
• 单元素输入[5]返回[5]
• 支持无限前缀和列表计算

基于scan类函数的实现 #

如果你希望用扫描类函数实现，可以用mapAccumL（属于scan类的遍历工具），逻辑和上面的实现完全一致：

import Data.List (mapAccumL)

undo_prefix_sum :: Num a => [a] -> [a]
undo_prefix_sum [] = []
undo_prefix_sum (x:xs) = x : snd (mapAccumL (\prev cur -> (cur, cur - prev)) x xs)

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