从右到左处理 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

p.s。显然我可以反转（但更愿意理解原始任务）列表两次并应用类似的东西：

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

Answer 1

从右到左处理 Haskell 列表的典型方法是将其反转。由于你想得到结果的原始顺序，你只需再次反转：

f1 = reverse . zipWith (+) (cycle [0,1]) . reverse

但如果你真的想，你可以让每个递归调用 return 更新尾部和一个标志，指示从末尾开始计算时该位置是否偶数，这样你就知道是否增加元素是否在那个位置：

f2 = snd . g
  where
  g []     = (False, [])
  g (x:xs) = let (addOne, xs') = g xs
                 x' = if addOne then x + 1 else x
             in (not addOne, x':xs')

我们基本上是在列表上映射一个函数，但是这个函数需要一个额外的参数，该参数从列表的右端开始计算。我们可以使用一个标准函数：

import Data.List (mapAccumR)
f2' = snd . mapAccumR g False
  where
  g addOne x = (not addOne, if addOne then x + 1 else x)

Answer 2

我认为您想要的更简洁的规范是，如果长度为偶数，则增加偶数索引；如果长度为奇数，则增加奇数索引。例如，当从零开始索引时，长度为 3 的列表导致索引 1 递增。一种方法是使用明显的两遍解决方案：

f xs = zipWith (+) (cycle sol) xs
 where sol = map fromEnum [even len, odd len] 
       len = length xs

这可以由 "tying the knot" 一次性完成（不依赖编译器融合规则）。例如（使用手动递归样式作为通信方式）。

f2 xs = let (isEven, result) = go isEven xs in result
 where
  go _ []     = (True,     [])
  go e (x:xs) = let (ne,rest) = go (not e) xs
                in (not ne, x+fromEnum e : rest)

Answer 3

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

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)以外的交替函数。

Answer 4

我喜欢 Thomas 的解决方案。但是，我认为这里一个简单的 foldr 就足够了。

process = snd . foldr (\x (b,xs) -> (not b, x + fromEnum b:xs)) (False,[])

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

Process Haskell list from right to left keeping origin order

iteration

reverse

haskell

list