Checking if all even-indexed elements in a (zero-based indexed) list are even

user_12164928 0
Viewed 474

I want to write a fstEven function that checks if the even-indexed integers in a list are all even; since in Haskell lists are have zero-based indexing, an even index corresponds to an odd position, and therefore an example of correct outputs would be

> fstEven [2,0,2,0]
True
> fstEven [1,2,3,4]
False

My attempt is this:

fstEven :: [Int] -> Bool
fstEven [] = False
fstEven (x:_:xs)
  | x `mod` 2 == 0 = True
  | otherwise = fstEven xs

But it seems to always give true as long as the last even position in the list is even, regardless of the others.

haskell
2 Answers

The problem here is that it will return True from the moment one of the other items is even. So it basically means "Any other element is even".

You should check it the other way around: an empty list means every other element is indeed even, whereas from the moment one of the other elements is odd, we return True, so:

everyOtherEven :: [Int] -> Bool
everyOtherEven [] = True
everyOtherEven [x] = even x
everyOtherEven (x:_:xs)
    | even x = everyOtherEven xs
    | otherwise = False

or we can work with:

everyOtherEven :: [Int] -> Bool
everyOtherEven [] = True
everyOtherEven [x] = even x
everyOtherEven (x:_:xs) = even x && everyOtherEven xs

For example:

Prelude> everyOtherEven [2,0,2,0]
True
Prelude> everyOtherEven [1,2,3,4]
False
Prelude> everyOtherEven [2,3,4]
True
Prelude> everyOtherEven [2,3,4,5]
True
Prelude> everyOtherEven [2,3,4,5,5]
False
user_675790

When a function has type [a] -> b it makes me think of using a fold. But folding over every other element seems a bit tricky, as folds usually act on every element. Let's take a closer look.

Notice that instead of checking if every other element is even, we could check that for all elements either its value is even or its index is odd.

myEven (idx, v) = odd idx || even v

First we zip :: [a] -> [b] -> [(a, b)] the input with a list of indices [0..], then we use all :: Foldable t => (a -> Bool) -> t a -> Bool to fold a list of pairs of indices and Ints to a Bool.

everyOtherEven :: [Int] -> Bool
everyOtherEven = all myEven . zip [0..]
  where
    myEven (idx, v) = odd idx || even v
user_40510200
Related