Process Haskell list from right to left keeping origin order

Question

Need increment every second item starting from the right in Haskell list but keeping origin order (e.g. reverse is not a case). For example:

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

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

I've tried something like a following:

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

p.s. Obviously I could reverse (but prefer to understand original task) the list twice and apply something like:

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

Answer 1

The typical way to process a Haskell list from right to left would be to reverse it. Since you want to have the original order for the result, you would simply reverse again:

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

But if you really want to, you can have each recursive call return both the updated tail and a flag that indicates whether that position is even when counted from the end so you know whether to increase the element at that position or not:

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')

We're basically mapping a function over the list, but this function requires an extra parameter that gets computed starting from the right end of the list. There's a standard function we can use:

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