9

I'd like to apply a function to every second element in a list:

> mapToEverySecond (*2) [1..10]
[1,4,3,8,5,12,7,16,9,20]

I've written the following function:

mapToEverySecond :: (a -> a) -> [a] -> [a]
mapToEverySecond f l = map (\(i,x) -> if odd i then f x else x) $ zip [0..] l

This works, but I wonder if there is a more idiomatic way to do things like that.

dfeuer
  • 48,079
  • 5
  • 63
  • 167
Nausika
  • 495
  • 7
  • 13
  • 2
    There are certainly *other* ways. But I'm voting to close on the grounds that what qualifies as "better" in this case seems very subjective. If you can describe a concrete problem you have with your implementation, then we can make a go of dealing with that problem. – Daniel Wagner Jan 31 '15 at 21:44
  • 10
    I'm with @DanielWagner on this, but here's a standard fun answer: `map2nd f = zipWith ($) (cycle [id, f])`. – J. Abrahamson Jan 31 '15 at 21:56
  • 2
    @J.Abrahamson, as of base 4.8, that will sometimes be slower than it is in previous versions (previous ones were shady). You can instead use `map2nd f xs = zipWith (flip ($)) xs (cycle [id, f])`. – dfeuer Jan 31 '15 at 22:09
  • 2
    You are right, "better" is subjective. But as I'm just starting to learn Haskell I'm interesseted to see solutions of experienced Haskellers. When I found this solution I just wondered if "this is it"... coming from for-loop-languages this feels very different. Thank you for the answer @J.Abrahamson. – Nausika Jan 31 '15 at 22:14
  • 1
    @dfeuer Why would the partially-applied version be slower in new versions of GHC? And why is it not considered a compiler bug? – Benjamin Hodgson Feb 01 '15 at 00:20
  • 2
    @BenjaminHodgson, it's not about the compiler, and it's not about the partial application either. `zipWith` has long attempted to fuse with either of its list arguments. Unfortunately, fusing with the *right* list argument is actually semantically wrong, and can produce bottoms where none should be when compiled with optimization and not otherwise. So I pushed to have that removed, and so `zipWith` will only fuse with its *left* list argument. – dfeuer Feb 01 '15 at 00:25
  • The trouble with fusing with the *right* argument is that if the right argument goes to bottom just where the left argument ends, you'll get bottom instead of `[]`. Although this was known when the code was written, it was really *always* a bug. – dfeuer Feb 01 '15 at 00:26

6 Answers6

8

I haven't written very much Haskell, but here's the first thing that came into mind:

func :: (a -> a) -> [a] -> [a]
func f [] = []
func f [x] = [x]
func f (x:s:xs) = x:(f s):(func f xs)

It is a little ulgy, since you have to not only take care of the empty list, but also the list with one element. This doesn't really scale well either (what if you want every third, or

One could do as @Landei points out, and write

func :: (a -> a) -> [a] -> [a]
func f (x:s:xs) = x:(f s):(func f xs)
func f xs = xs

In order to get rid of the ugly checks for both [] and [x], though, IMHO, this makes it a little harder to read (at least the first time).

MartinHaTh
  • 1,417
  • 1
  • 13
  • 25
  • Very reasonable. However, you should probably remove the redundant parentheses in the last line: `func f (x:s:xs)=x : f s : func f xs`. – dfeuer Feb 01 '15 at 00:21
  • Accepted, this is the most straight forward solution (for me). Thank you. I guess for other index based criterias (every third, fourth, only prime, etc) I'll stick with my solution. – Nausika Feb 01 '15 at 20:21
  • 1
    You could remove the first two cases, and append `func f xs = xs` as **last** one instead. – Landei Feb 02 '15 at 14:02
7

Here is how I would do it:

mapOnlyOddNumbered f []      = []
mapOnlyOddNumbered f (x:xs)  = f x : mapOnlyEvenNumbered f xs

mapOnlyEvenNumbered f []     = []
mapOnlyEvenNumbered f (x:xs) = x : mapOnlyOddNumbered f xs

Whether this is "idiomatic" is a matter of opinion (and I would have given it as a comment if it would fit there) , but it may be useful to see a number of different approaches. Your solution is just as valid as mine, or the ones in the comments, and easier to change into say mapOnlyEvery13nd or mapOnlyPrimeNumbered

Hans Lub
  • 5,513
  • 1
  • 23
  • 43
7
mapToEverySecond = zipWith ($) (cycle [id, (*2)])

Is the smallest I can think of, also looks pretty clear in my opinion. It also kinda scales with every nth.

Edit: Oh, people already suggested it in comments. I don't want to steal it, but I really think this is the answer.

utdemir
  • 26,532
  • 10
  • 62
  • 81
  • For uniformity with the other answers, I think it should better be `mapToEverySecond f = zipWith ($) (cycle [id, f])` – Stef Jan 01 '22 at 16:45
3

Here's how I would probably do it:

mapToEverySecond f xs = foldr go (`seq` []) xs False
  where
    go x cont !mapThisTime =
      (if mapThisTime then f x else x) : cont (not mapThisTime)

But if I were writing library code, I'd probably wrap that up in a build form.

Edit

Yes, this can also be done using mapAccumL or traverse.

import Control.Applicative
import Control.Monad.Trans.State.Strict
import Data.Traversable (Traversable (traverse), mapAccumL)

mapToEverySecond :: Traversable t => (a -> a) -> t a -> t a
-- Either
mapToEverySecond f = snd . flip mapAccumL False
 (\mapThisTime x ->
     if mapThisTime
     then (False, f x)
     else (True, x))

-- or
mapToEverySecond f xs = evalState (traverse step xs) False
  where
    step x = do
      mapThisTime <- get
      put (not mapThisTime)
      if mapThisTime then return (f x) else return x

Or you can do it with scanl, which I'll leave for you to figure out.

Community
  • 1
  • 1
dfeuer
  • 48,079
  • 5
  • 63
  • 167
  • Thank you, this looks interessting (I wanted to use a fold/scan initially). I need to look up seq and ! though, this is the first time I see them. – Nausika Feb 01 '15 at 20:15
  • @Nausika, unfortunately, scans are a little bit broken in Haskell (grr...), but you can use them anyway if you like. Another, differently-broken, option is `mapAccumL`. Cleaner than either would be `traverse`. – dfeuer Feb 01 '15 at 20:45
  • @Nausika, I've added some details. – dfeuer Feb 01 '15 at 21:29
  • 1
    Thanks for the details. The function `mapAccumL` is excatly what I was looking for! Why do you say that scans and mapAccum are broken? – Nausika Feb 04 '15 at 14:08
  • @Nausika, `mapAccumL` is not really broken, per se, but the fact that it returns the final value of the accumulator along with the list keeps it from working as well as it otherwise could with the list fusion optimizations. `scanl` is broken because it starts the list off with the initial accumulator value. The biggest problem with this, probably, is that it can't be defined for general `Traversable` types. It also makes some other thing a bit awkward, as I recall. – dfeuer Feb 04 '15 at 16:56
1

This is more a comment to @MartinHaTh's answer. I'd slightly optimize his solution to

func :: (a -> a) -> [a] -> [a]
func f = loop
  where
    loop []  = []
    loop [x] = [x]
    loop (x:s:xs) = x : f s : loop xs
Petr
  • 62,528
  • 13
  • 153
  • 317
  • 3
    Is this actually an optimization, or just saving characters? You don't explicitly pass the `f` to recursive calls anymore, but I think it's still implicitly passed around just as much by the closure-creating machinery. – amalloy Feb 01 '15 at 08:45
  • 1
    @amalloy It is an optimization. MartinHaTh's function is recursive, which means it won't be inlined by GHC. But this `func` isn't (only `loop` is), so `func f` will be inlined, which also enables further potential optimizations. See also [Can GHC really never inline map, scanl, foldr, etc.?](http://stackoverflow.com/q/9658438/1333025). – Petr Feb 02 '15 at 10:13
0

Not very elegant, but this is my take:

mapToEverySecond f = reverse . fst . foldl' cmb ([], False) where
    cmb (xs, b) x = ((if b then f else id) x : xs, not b)

Or improving on MartinHaTh's answer:

mapToEverySecond f (x : x' : xs) = x : f x' : mapToEverySecond f xs
mapToEverySecond _ xs = xs
Landei
  • 54,104
  • 13
  • 100
  • 195