Double every other element of list from right in Haskell

Question

I have a list and I want to double every other element in this list from the right.

There is another related question that solves this problem but it doubles from the left, not the right: Haskell: Double every 2nd element in list

For example, in my scenario, [1,2,3,4] would become [2,2,6,4], and in that question, [1,2,3,4] would become [1,4,3,8].

How would I implement this?

Answer 1

I think that the top answer misinterpreted the question. The title clearly states that the OP wants to double the second, fourth, etc. elements from the right of the list. Ørjan Johansen's answer is correct, but slow. Here is my more efficient solution:

doubleFromRight :: [Integer] -> [Integer]
doubleFromRight xs = fst $ foldr (\x (acc, bool) ->
                                  ((if bool then 2 * x else x) : acc,
                                   not bool)) ([], False) xs

It folds over the list from the right. The initial value is a tuple containing the empty list and a boolean. The boolean starts as false and flips every time. The value is multiplied by 2 only if the boolean is true.

Answer 2

How about this for simplicity?

doubleEveryOtherRev :: [Integer] -> [Integer]

doubleEveryOtherRev l = doubleRev (reverse l) []
  where
    doubleRev [] a = a
    doubleRev (x:[]) a = (x:a)
    doubleRev (x:y:zs) a = doubleRev zs (2*y:x:a)

---

You would have to feed a reversed list of digits, in case you followed that course's recommendation, because it will double every other element as it reverses again. I think that this is different than using twice the reverse function, with another to double every other digit in between, because you won't need to know the full extent of their list by the second time. In other words, it solves that course's problem, but someone correct me if I'm wrong.

Answer 3

OK, as @TomEllis mentions, everyone else seems to have interpreted your question as about odd-numbered elements from the left, instead of as even-numbered from the right, as your title implies.

Since you start checking positions from the right, there is no way to know what to double until the end of the list has been found. So the solution cannot be lazy, and will need to temporarily store the entire list somewhere (even if just on the execution stack) before returning anything.

Given this, the simplest solution might be to just apply reverse before and after the from-left solution:

doubleFromRight = reverse . doubleFromLeft . reverse

Answer 4

Think about it.

double = zipWith ($) (cycle [(*2),id])

EDIT I should note, this isn't really my solution it is the solution of the linked post with the (*2) and id flipped. That's why I said think about it because it was such a trivial fix.

Answer 5

A direct implementation would be:

doubleOddElements :: [Int] -> [Int]
doubleOddElements [] = []
doubleOddElements [x] = [2 * x]
doubleOddElements (x:y:xs) = (2*x):y:(doubleOddElements xs)

Answer 6

Okay, so not elegant or efficient like the other answers, but I wrote this from a beginners standpoint (I am one) in terms of readability and basic functionality.

This doubles every second number, beginning from the right.

Using this script: doubleEveryOther [1,3,6,9,12,15,18] produces [1,6,6,18,12,30,18] and doubleEveryOther [1,3,6,9,12,15] produces [2,3,12,9,24,15]

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther (x:[]) = [x]
doubleEveryOther (x:y:zs)
  |  (length (x:y:zs)) `mod` 2    /= 0    =    x : y*2 : doubleEveryOther zs
  |  otherwise                            =    x*2 : y : doubleEveryOther zs

Answer 7

Trying to generalize the problem a bit: Since we want to double every 2nd element from the end, we can't know in advance if it'll be every odd or even from the start. So the easiest way is to construct both, count if the overall size is even or odd, and then decide.

Let's define an Applicative data structure that captures:

• Having two variants of values,
• keeping the parity of the length (odd/even), and
• alternating the two when two such values are combined,

as follows:

import Control.Applicative
import Data.Monoid
import qualified Data.Traversable as T

data Switching m = Switching !Bool m m
  deriving (Eq, Ord, Show)

instance Functor Switching where
    fmap f (Switching b x y) = Switching b (f x) (f y)

instance Applicative Switching where
    pure x = Switching False x x
    (Switching False f g) <*> (Switching b2 x y) = Switching b2 (f x) (g y)
    (Switching True  f g) <*> (Switching b2 x y) = Switching (not b2) (f y) (g x)

So traversing a list will yield two lists looking like this:

x1 y2 x3 y4 ...
y1 x2 y3 x4 ...

two zig-zag-ing copies. Now we can compute

double2 :: (Num m) => m -> Switching m
double2 x = Switching True (2 * x) x

double2ndRight :: (Num m, T.Traversable f) => f m -> f m
double2ndRight k = case T.traverse double2 k of
                    Switching True _ y -> y
                    Switching False x _ -> x

Answer 8

Here are mine two solutions, note that I'm complete beginner in Haskell.

First one uses list functions, head, tail and lenght:

doubleSecondFromEnd :: [Integer] -> [Integer]
doubleSecondFromEnd [] = []  -- Do nothing on empty list
doubleSecondFromEnd n
  | length n `mod` 2 == 0 = head n * 2 : doubleSecondFromEnd (tail n)
  | otherwise      = head n : doubleSecondFromEnd (tail n)

Second one, similar but with a different approach only uses length function:

doubleSecondFromEnd2 :: [Integer] -> [Integer]
doubleSecondFromEnd2 [] = []  -- Do nothing on empty list
doubleSecondFromEnd2 (x:y)
  | length y `mod` 2 /= 0 = x * 2 : doubleSecondFromEnd2 y
  | otherwise      = x : doubleSecondFromEnd2 y

Answer 9

I am just learning Haskell so please find the following beginner solution. I try to use limited cool functions like zipWith , cycle, or reverse

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther s@(x:xs)
  | (length s) `mod` 2 == 0 = (x * 2) : (doubleEveryOther xs)
  | otherwise =  x : (doubleEveryOther xs)

The key thing to note that when doubling every element from the right you can put the doubling into two cases:

1. If the list is even length, you will ultimately end up doubling the first element of the list.
2. If the list is odd length, you will not be doubling the first element of the list.

I answered this as part of the homework assignment from CS194

Answer 10

My first thought was:

doubleOdd (x:xs) = (2*x):(doubleEven xs)
doubleOdd [] = []
doubleEven (x:xs) = x:(doubleOdd xs)
doubleEven [] = []

DiegoNolan's solution is more elegant, in that the function and sequence length are more easily altered, but it took me a moment to grok.

Adding the requirement to operate from the right makes it a little more complex. foldr is a neat starting point for doing something from the right, so let me try:

doubleOddFromRight = third . foldr builder (id,double,[])
    where third (_,_,x) = x
          builder x (fx,fy,xs) = (fy, fx, fx x : xs)
          double x = 2 * x

This swaps the two functions fx and fy for each entry. To find the value of any entry will require a traversal to the end of the list, finding whether the length was odd or even.

Answer 11

This is my answer to this CIS 194 homework assignment. It's implemented using just the stuff that was introduced in lecture 1 + reverse.

doubleEveryOtherLeftToRight :: [Integer] -> [Integer]
doubleEveryOtherLeftToRight []       = []
doubleEveryOtherLeftToRight (x:[])   = [x]
doubleEveryOtherLeftToRight (x:y:zs) = x:y*2:(doubleEveryOtherLeftToRight zs)

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = reverse (doubleEveryOtherLeftToRight (reverse xs))

Answer 12

We can also do it like this:

doubleEveryOther = reverse . zipWith (*) value . reverse
    where
    value = 1 : 2 : value