Mapping based on found value

user_5927758 0
Viewed 94

I want to be able to map but skip some elements based on found elements. The essence of the issue is here.

a = [1,2,3,4,5]

i = 0
while i < len(a):
    if a[i] % 2 == 0:
       a[i] *= 2
    else:
       i += 1
    i += 1

I can express this with explicit recursion in Haskell by passing along an index variable and an accumulator.

f :: Int -> [Int] -> [Int] -> [Int]
f index list acc = if index < length list then 
                   if even (list !! index) then f (index + 1) list (acc ++ [(list !! index) * 2]) else f (index + 2) list (acc ++ [list !! index, list !! (index + 1)])
                   else acc

f 0 [1,2,3,4,5] []

But this feels really ugly, is there a better way to do this?

haskell
3 Answers

How about using mapAccumL and use a boolean accumulator to represent whether the previous number was odd?

f = snd . mapAccumL go False
  where
    go False n | even n = (False, n * 2)
    go True n | even n = (False, n)
    go _ n = (True, n)
user_13788680

If I haven't got it wrong,

I think the code is going to multiply the number if it is even then move to the next one otherwise move forward twice

and I've try something like this

In [6]: walk :: [Int] -> [Int] 
      : walk [] = [] 
      : walk [x] = if even x then [x*2] else [x] 
      : walk (x:y:xs) = if even x then (2*x): walk (y:xs) else [x,y] ++ walk xs 
      :        
        
In [7]: walk [1..5] 
      :                                                                         
[1,2,3,4,5]

and it yields the same result.

user_104996850

You can do this with a fold, where you leave a value unmodified if the previous value was odd. It ought to be a left fold, since you’re proceeding from left to right, so this can use the common pattern of accumulating a list from the left and then reversing it at the end.

f = reverse . fst . foldl' go ([], False)
  where
    go (xs, skip) x
      | skip = (x : xs, False)
      | x `mod` 2 == 0 = (x * 2 : xs, False)
      | otherwise = (x : xs, True)

This is essentially using Bool as a counter for the number of elements to skip, whose value can only be 0 or 1. If you needed to skip more elements in some circumstances, you could use an integer rather than a Boolean.

I arrived at this solution by restructuring the loop from the original code:

i = 0
while i < len(a):
    if a[i] % 2 == 0:
       a[i] *= 2
    else:
       i += 1
    i += 1

Into one that decouples the state (whether to skip an element) from the list index:

i = 0
skip = False
while i < len(a):
    if a[i] % 2 == 0:
        if not skip:
            a[i] *= 2
        skip = False
    else:
        skip = True
    i += 1

You can also do this without explicit recursion or a fold, by decoupling the even/odd test from the iteration, and zipping them together:

f = zipWith3 go xs evens afterOdds
  where
    go x isEven afterOdd
      | isEven, not afterOdd = x * 2
      | otherwise            = x

    -- Whether each element is even.
    evens = map even xs

    -- Whether the previous element was odd.
    -- Note the initial ‘False’ prepended.
    afterOdds = False : map not evens

For example, given an input like [2, 4, 1, 6], evens is [True, True, False, True] and afterOdds is [False, False, False, True, False], so go is called as:

  • go 2 True False = 4
  • go 4 True False = 8
  • go 1 False False = 1
  • go 6 True True = 6

Giving [4, 8, 1, 6]. The extra False in afterOdds is ignored since the other lists run out of elements by that point in the zipping.

This can even be written using exclusively list comprehensions with {-# LANGUAGE ParallelListComp #-} enabled:

f xs =
  [ if isEven && not afterOdd then x * 2 else x
  | x <- xs
  | isEven <- [even x | x <- xs]
  | afterOdd <- False : [odd x | x <- xs]
  ]

To skip multiple elements this way, you could again use an integer instead of a Boolean, indicating the number of elements since an odd element, for example with scanl':

sinceLastOdd = scanl' go Nothing
  where
    go n x
      | odd x     = Just 0
      | otherwise = fmap succ n

> sinceLastOdd [2, 4, 1, 6, 8, 3, 10, 12]
[Nothing,Nothing,Nothing,Just 0,Just 1,Just 2,Just 0,Just 1,Just 2]
user_2468860
Related