CODEWITHSUNDEEP
listhaskelliterationreverse
Dewfy
Dewfy

Reputation: 23624

Process Haskell list from right to left keeping origin order

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

Upvotes: 4

Views: 701

Answers (4)

behzad.nouri
behzad.nouri

Reputation: 77951

This can be done efficiently using a left fold:

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)

Note that even thought this is a left fold, the list is built using cons (:) operator; and it will perform linearly and not quadratic (similar construct as in difference lists).

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

It can also be generalized to alternating functions other than id and (+ 1).

Upvotes: 3

is7s
is7s

Reputation: 3480

I like Thomas's solution. However, I think a simple foldr is enough here.

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

Upvotes: 0

Thomas M. DuBuisson
Thomas M. DuBuisson

Reputation: 64740

I think a cleaner specification for what you want is that you increment even indicies if the length is even and odd indicies if the length is odd. For example, when indexing from zero, the list of length 3 resulted in index 1 being incremented. One way to do this is with the obvious two pass solution:

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

This can be done in one pass (without relying on the compiler fusion rules) by "tying the knot". For example (using manual recursive style as means of communication).

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)

Upvotes: 4

raymonad
raymonad

Reputation: 949

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)

Upvotes: 4

Related Questions