Can mapEvery be implemented with foldr

Question

For a function that maps a function to every nth element in a list:

mapEvery :: Int -> (a -> a) -> [a] -> [a]
mapEvery n f = zipWith ($) (drop 1 . cycle . take n $ f : repeat id)

Is it possible to implement this with foldr like ordinary map?

EDIT: In the title, changed 'folder' to 'foldr'. Autocorrect...

Hm? That's really interesting. How would you implement it with multiple `foldr`'s? — Ramith Jayatilleka, Oct 08 '14 at 16:42
...Never mind, don't think that'd work either. With `foldr` you're only going to be able to count how many elements from the _end_ of the list you are, not how many from the beginning you are. — Louis Wasserman, Oct 08 '14 at 16:45
Yeah, I realized that. I was thinking that could work, if the base case includes `mod (length xs) n` but that only works for finite lists. — Ramith Jayatilleka, Oct 08 '14 at 16:56
@LouisWasserman You can implement `foldl` in terms of `foldr`, so it really doesn't matter which fold you use. — bheklilr, Oct 08 '14 at 16:59

score 6 · Accepted Answer · answered Oct 08 '14 at 17:23

Here's one solution

mapEvery :: Int -> (a -> a) -> [a] -> [a]
mapEvery n f as = foldr go (const []) as 1 where
  go a as m 
    | m == n    = f a : as 1
    | otherwise =   a : as (m+1)

This uses the "foldl as foldr" trick to pass state from the left to the right along the list as you fold. Essentially, if we read the type of foldr as (a -> r -> r) -> r -> [a] -> r then we instantiate r as Int -> [a] where the passed integer is the current number of elements we've passed without calling the function.

score 1 · Answer 2 · edited May 23 '17 at 11:49

Yes, it can:

mapEvery :: Int -> (a -> a) -> [a] -> [a]
mapEvery n f xs
    = foldr (\y ys -> g y : ys) []
    $ zip [1..] xs
    where
        g (i, y) = if i `mod` n == 0 then f y else y

And since it's possible to implement zip in terms of foldr, you could get even more fold-y if you really wanted. This even works on infinite lists:

> take 20 $ mapEvery 5 (+1) $ repeat 1
[1,1,1,1,2,1,1,1,1,2,1,1,1,1,2,1,1,1,1,2]

This is what it looks like with even more foldr and inlining g:

mapEvery :: Int -> (a -> a) -> [a] -> [a]
mapEvery _ _ [] = []
mapEvery n f xs
    = foldr (\(i, y) ys -> (if i `mod` n == 0 then f y else y) : ys) []
    $ foldr step (const []) [1..] xs
    where
        step _ _ [] = []
        step x zipsfn (y:ys) = (x, y) : zipsfn ys

Now, would I recommend writing it this way? Absolutely not. This is about as obfuscated as you can get while still writing "readable" code. But it does demonstrate that this is possible to use the very powerful foldr to implement relatively complex functions.

Can mapEvery be implemented with foldr

2 Answers2