Mutual recursion in odd/even functions in haskell

Question

In chapter 6 of "Programming in Haskell" by Graham Hutton there is a section called "6.5 Mutual recursion", that contains the following example:

even :: Int -> Bool
even 0       = True
even (n + 1) = odd n

odd :: Int -> Bool
odd 0       = False
odd (n + 1) = even n

I wanted to try it out. I put the code in Hof.hs file, ran ghci(version 7.8.3), typed

:l Hof.hs

and got the following error message

Hof.hs:3:7: Parse error in pattern: n + 1
Failed, modules loaded: none.

Why am I getting this message? Is the code syntactically out of date or something?

Answer 1

n + k patterns have been removed from Haskell and are no longer available. Write it like this instead:

even :: Int -> Bool
even 0 = True
even n = odd (n - 1)

odd :: Int -> Bool
odd 0 = False
odd n = even (n - 1)

Note that this function fails horribly for negative inputs, so you probably want to augment it with abs.

Answer 2

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]