Edit every Nth item in a list

Question

I want to perform an arithmetic operation (e.g. doubling the value) on a list of integers, every n places.

For example, given the list [1,2,3,4,5,6,7], I want to double values every three places. In that case, we would have [1,2,6,4,5,12,7].

How can I do it?

Answer 1

applyEvery :: Int -> (a -> a) -> [a] -> [a]
applyEvery n f = zipWith ($) (cycle (replicate (n-1) id ++ [f]))

The cycle subexpression builds a list of functions [id,id,...,id,f] with the correct number of elements and repeats it ad nauseam, while the zipWith ($) applies that list of functions to the argument list.

---

Since you asked for it, more detail! Feel free to ask for more explanation.

The main idea is maybe best explained with an ASCII picture (which won't stop me from writing a thousand a lot of ASCII words!):

functions : [ id, id, f  , id, id, f  , id, id, f, ... 
input list: [  1,  2,   3,  4,  5,   6,  7 ]
-----------------------------------------------------
result    : [  1,  2, f 3,  4,  5, f 6,  7 ]

Just like there's no reason to hardcode the fact that you want to double every third element in the list, there's nothing special about f (which in your example is doubling), except that it should have the same result type as doing nothing. So I made these the parameters of my function. It's even not important that you operate on a list of numbers, so the function works on lists of a, as long as it's given an 'interval' and an operation. That gives us the type signature applyEvery :: Int -> (a -> a) -> [a] -> [a]. I put the input list last, because then a partial application like doubleEveryThird = applyEvery 3 (*2) is something that returns a new list, a so-called combinator. I picked the order of the other two arguments basically at random :-)

To build the list of functions, we first assemble the basic building block, consisting of n-1 ids, followed by an f as follows: replicate (n-1) id ++ [f]. replicate m x makes a list containing m repetitions of the xargument, e.g. replicate 5 'a' = "aaaaa", but it also works for functions. We have to append the f wrapped in a list of its own, instead of using : because you can only prepend single elements at the front - Haskell's lists are singly-linked.

Next, we keep on repeating the basic building block with cycle (not repeat as I first had mistakenly). cycle has type [a] -> [a] so the result is a list of "the same level of nested-ness". Example cycle [1,2,3] evaluates to [1,2,3,1,2,3,1,2,3,...]

[ Side note: the only repeat-y function we haven't used is repeat itself: that forms an infinite list consisting of its argument ]

With that out of the way, the slightly tricky zipWith ($) part. You might already know the plain zip function, which takes two lists and puts elements in the same place in a tuple in the result, terminating when either list runs out of elements. Pictorially:

    xs   : [ a  , b    , c   , d, e] 
       ys: [   x,    y ,   z ]
------------------------------
zip xs ys: [(a,x),(b,y),(c,z)]

This already looks an awful lot like the first picture, right? The only thing is that we don't want to put the individual elements together in a tuple, but apply the first element (which is a function) to the second instead. Zipping with a custom combining function is done with zipWith. Another picture (the last one, I promise!):

          xs   : [   a  ,   b  ,   c   , d, e] 
             ys: [     x,     y,     z ]
----------------------------------------
zipWith f xs ys: [ f a x, f b y, f c z ]

Now, what should we choose to zipWith with? Well, we want to apply the first argument to the second, so (\f x -> f x) should do the trick. If lambdas make you uncomfortable, you can also define a top-level function apply f x = f x and use that instead. However, this already a standard operator in the Prelude, namely $! Since you can't use a infix operator as a standalone function, we have to use the syntactic sugar ($) (which really just means (\f x -> f $ x))

Putting all of the above together, we get:

applyEvery :: Int -> (a -> a) -> [a] -> [a]
applyEvery n f xs = zipWith ($) (cycle (replicate (n-1) id ++ [f])) xs

But we can get rid of the xs at the end, leading to the definition I gave.

Answer 2

A common way to get indexes for values in a list is to zip the list into tuples of (value, index).

ghci > let zipped = zip [1,2,3,4,5,6,7] [1..]
ghci > zipped
[(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)]

Then you just need to map over that list and return a new one. If index is divisible by 3 (index `rem` 3 == 0), we'll double the value, otherwise we'll return the same value:

ghci > map (\(value, index) -> if index `rem` 3 == 0 then value*2 else value) zipped
[1,2,6,4,5,12,7]

Tell me if that all makes sense—I can add more detail if you aren't familiar with zip and map and such.

Zip

You can find documentation on zip by looking at its Haddocks, which say: "zip takes two lists and returns a list of corresponding pairs." (Docs are hosted in several places, but I went to https://www.stackage.org and searched for zip).

Map

The map function applies a function to each item in a list, generating a new value for each element.

Lambdas

Lambdas are just functions without a specific name. We used one in the first argument to map to say what we should do to each element in the list. You may have seen these in other languages like Python, Ruby, or Swift.

This is the syntax for lambdas:

(\arg1, arg2 -> functionBodyHere)

We could have also written it without a lambda:

ghci > let myCalculation (value, index) = if index `rem` 3 == 0 then value*2 else value
ghci > map myCalculation zipped
[1,2,6,4,5,12,7]