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.

Answer 3

Let’s look at a sample evaluation of evens on an input list. I’ll use "abcde"—recall that String is an alias for a list of characters [Char], so this is equivalent to ['a', 'b', 'c', 'd', 'e'] or 'a' : 'b' : 'c' : 'd' : 'e' : [].

We start with the initial input:

evens "abcde"

Match the first pattern of evens, adding 'a' to the beginning of the result and proceeding on the remainder of the list:

evens "abcde"
-------------

-- evens (x : xs) = x : odds xs
-- x = 'a'
-- xs = "bcde"
-- evens "abcde" = 'a' : odds "bcde"

'a' : odds "bcde"
-----------------

Match the first pattern of odds, ignoring 'b' and proceeding:

'a' : odds "bcde"
      -----------

-- odds (_ : xs) = evens xs
-- xs = "cde"
-- odds "bcde" = evens "cde"

'a' : evens "cde"
      -----------

First pattern of evens, adding 'c':

'a' : evens "cde"
      -----------

-- evens (x : xs) = x : odds xs
-- x = 'c'
-- xs = "de"
-- evens "cde" = 'c' : odds "de"

'a' : 'c' : odds "de"
      ---------------

First pattern of odds, ignoring 'd':

'a' : 'c' : odds "de"
            ---------

-- odds (_ : xs) = evens xs
-- xs = "e"
-- odds "de" = evens "e"

'a' : 'c' : evens "e"
            ---------

First pattern of evens, adding 'e':

'a' : 'c' : evens "e"
            ---------

-- evens (x : xs) = x : odds xs
-- x = 'e'
-- xs = "" = []
-- evens "e" = 'e' : odds ""

'a' : 'c' : 'e' : odds ""
            -------------

Now, finally, the first pattern of odds doesn’t match, because an empty list [] doesn’t match the list constructor _ : _, so we fall through to the second (default) pattern:

'a' : 'c' : 'e' : odds ""
                  -------

-- odds _ = []
-- odds "" = []

'a' : 'c' : 'e' : []
                  --

Giving the final result:

"ace"

Basically these functions are treating the input as a “stream” of values and producing a stream as a result: evens consumes one element and outputs it to the result, proceeding to take the odds of the remainder; while odds consumes one element and discards it, taking the evens of the remainder.

This doesn’t do any calculation on the indices because it doesn’t have to—it’s just following the structure of the list. By definition, the first value in a list is at an even index (when counting from 0), so evens keeps it and takes the odd indices of the remainder, while odds discards it and takes the even indices of the remainder. Removing each element shifts all the indices down by one—that is, the element that was at index 1 in the input list is at index 0 in the tail of the input:

zip [0..] "abcde" == [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e')]

'a' 'b' 'c' 'd' 'e'
 0   1   2   3   4
 |   |   |   |   |
 x   /   /   /   /
    /   /   /   /
   /   /   /   /
  /   /   /   /
 |   |   |   |
'b' 'c' 'd' 'e'
 0   1   2   3

zip [0..] "bcde" == [(0, 'b'), (1, 'c'), (2, 'd'), (3, 'e')]

You could also implement these functions explicitly using indices instead of mutual recursion. With list comprehensions:

evens xs = [x | (i, x) <- zip [0..] xs, even i]

odds xs = [x | (i, x) <- zip [0..] xs, odd i]

Or with explicit map and filter:

evens = map snd . filter (even . fst) . zip [0..]

odds = map snd . filter (odd . fst) . zip [0..]

Then you could even turn the predicate on the indices into a parameter:

indices f = map snd . filter (f . fst) . zip [0..]

evens = indices even

odds = indices odd

Answer 4

Our own language is quite powerful. I was having difficulty with limits when teaching myself calculus until I read one sentence in one paragraph of Newton. It was, of course, in English.

First off, you are correct about the indexing not being used or needed.

Secondly, the code does not know the difference between even or odd and you are again right to question it.

Finally, I modified these slightly to work properly on my implementation.

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

How they work is evens does the work. It builds the output list. It takes the first item of a list fed it and makes it the first or next item of the output list. It calls odds with the remainder of the list. odds simply returns the tail of what it received back to evens.

Like tail, it discards the first item of what it receives.

evens produces a list with about half of the items discarded. odds produces nothing but does the critical discarding.

If you give evens the list [0,1,2,3,4] it returns every other item starting with 0, that is, [0,2,4]. If you give evens the list [1,2,3,4] it returns [1,3] because the list started with and odd number. Wherever evens starts, that's what it produces.

Try either with [1,1,1,1,1] or "bcdefg"

The modifications made to the functions reflect what each does respectively with the remaining element. odds discards it, evens attaches it to the end of the output list.

Both functions only work properly if given a list starting with an even number. If given a list with an odd number they work in reverse.

Here is a function that will produce an even or odd list depending on a specified starting number and ending in the specified ending number.

eo s e = [s,s+2..e]