Getting even and odd position of elements in list - Haskell Mutual Recursion

Question

I recently started learning Haskell.

I found this code online which returns the elements at all even/odd positions of a list.

It makes use of mutual recursion, but I cannot seem to understand how it works internally.

evens (x:xs) = x:odds xs
evens _ = []

odds (_:xs) = evens xs
odds _ = []

In particular, I don't understand how the list is moving forward and evaluating all elements. How does it check for even positions even though there is no explicit index checking

Would someone be able to provide insight?

Answer 1

First, let's agree on something: we use 0-based indices most of the time, right? So, if I were to ask you what the element in position 2 is in the list

a : b : c : d : []

you would answer c. EDIT: if you're not familiar with Haskell notation, : is the list constructor and a : b denotes the list made by prepending a in front of list b.

Moving on to elements in even position, a and c would be the obvious answer, whereas b and d would be in odd position. Let's look at the definition of even.

evens (x:xs) = x:odds xs
evens [] = []

• The base case is trivial: there is no element in even position in the empty list

• the inductive case says that the element in position 0 (x) is in even position -- which it is -- and it also says that all the other elements in even position in the list (x:xs) are in odd position in the list xs. Indeed, element in position 2 in list (x:xs) is in position 1 in list xs, the one in position 4 in position 3, and so on and so forth; does that make sense?

Using the same reasoning, it follows that elements in odd position in the list (x:xs) are elements in even position in the list xs, which is exactly the definition of odds here above.

Answer 2

Use Debug.Trace to see how the indices change with each recursive call. The trace function prints its first argument to standard error before returning its second argument.

import Debug.Trace

evens (x:xs) = x : odds (trace (show (zip [0..] xs)) xs)
evens [] = []
odds (_:xs) = evens (trace (show (zip [0..] xs)) xs)
odds [] = []

main = print (evens "abcdefg")

Standard error will show

[(0,'b'),(1,'c'),(2,'d'),(3,'e'),(4,'f'),(5,'g')]
[(0,'c'),(1,'d'),(2,'e'),(3,'f'),(4,'g')]
[(0,'d'),(1,'e'),(2,'f'),(3,'g')]
[(0,'e'),(1,'f'),(2,'g')]
[(0,'f'),(1,'g')]
[(0,'g')]
[]

Each time you make a recursive call, the positions of each original item "shifts" by one place. g, for instance, is in an even position in the original list, but alternates from even to odd positions in each recursive call.