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?

Machinate

Have you tried evaluating simple expressions, like evens ('a':'b':'c':[]), by hand? At what point does your understanding fail? – Alfaro

@Alfaro It's more that 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 – Machinate

In evens, x is the element at the zero-th position, and xs are the elements from the first position onwards. In the call to odds xs, we moved one element forward through that. Instead of two functions, you could also write a single function with a "boolean index" - a toggle whether you currently are at an odd or an even position in the original array. – Alfaro

Have you seen other examples of recursion over lists (like length or sum or take)? – Alfaro

@Alfaro I haven't no, I have only recently started looking into Haskell but I found this example very intriguing – Machinate

I see, maybe you should start with something simpler than (I'd recommend length, take, and functions that return the 0th, 1st or 2nd element: head, first, second). You probably need to learn more about pattern matching. – Alfaro

In Haskell, it is very idiomatic to avoid indexing, when possible. In many cases, you do not need it, when you have pattern matching and recursion. (Mutual recursion like this is quite rare, though.) Even in real life, if I had to take the even-indexed cards in a deck, I'd use a "take,discard,take,discard,..." method, I surely would not count the cards to know their index. The Haskell code above roughly does the same thing. – Altonaltona

@chi, I've not noticed mutual recursion being particularly rare, although it's not exactly ubiquitous either. Certainly it shows up a lot in Data.Tree, and several key places in Streaming, and in the default definitions of some and many. I wouldn't be at all surprised to see it elsewhere in parsing-land either, since automaton states can be represented as functions pretty naturally. – Psychological

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.

Voorhis

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.

Marrano

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

Solvable

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]

Etiquette