list - 从右到左处理 Haskell 列表，保持原始顺序

Question

需要从 Haskell 列表中的右侧开始每隔一个项目增加一次但保持原始顺序(例如 reverse 不是这种情况)。例如:

 f [1, 2, 3] --  [1, 3, 3]

 f [1, 2, 3, 4] -- [2, 2, 4, 4]

我试过类似以下的东西:

fc ([]) = []
fc (x:[]) = [x]
fc (x:[y]) = [x+1,y]
fc( x:xs ) = fc [x] : ( fc xs ) -- this line is wrong

附言显然我可以反转(但更喜欢理解原始任务)列表两次并应用以下内容:

helper (x:y:tail) = [x, y+1] ++ tail
fc x = reverse (helper (reverse x) )

Answer 1

这可以使用左折叠有效地完成:

inc :: Num a => [a] -> [a]
inc xs = foldl go (\_ _ acc -> acc) xs id (+ 1) []
    where go run x f g acc = run g f (f x: acc)

请注意，即使认为这是左折叠，列表也是使用 cons (:) 运算符构建的；它将线性执行而不是二次执行(类似于 difference lists 中的构造)。

\> inc [1, 2, 3]
[1,3,3]
\> inc [1, 2, 3, 4]
[2,2,4,4]

它也可以推广到 id 和 (+ 1) 以外的交替函数。