Haskell execution sequence

Question

isOdd, isEven :: Int -> Bool
isOdd n
    | n<=0 = False
    | otherwise = isEven (n-1)
isEven n
    | n<0 = False
    | n==0 = True
    | otherwise = isOdd (n-1)

I'm having trouble understanding this code,in isOdd,it only defines what is False,and then switch to isEven,so how does haskell know when is n odd?

Answer 1

There are two different functions here: isOdd and isEven. They are defined in terms of each other: A number is "not odd" if it is negative or zero, and "odd" if one less than that number is "even". A number is "not even" if it is negative, and "even" if it is zero or one less than that number is "odd".

It's a fairly unintuitive way to define these functions, but it has nothing to do with "execution sequence" or "evaluation order". In fact, Haskell compilers are allowed to execute any computation they want as long as it gives the correct value as a result and follows the lazy/strict semantics as specified in the Haskell Report.

A better implementation of these functions is as follows: (from the Prelude)

even, odd       :: (Integral a) => a -> Bool
even n          =  n `rem` 2 == 0
odd             =  not . even

In other words, and integer-like thing is even if the remainder when you divide it by 2 is 0, and odd if it is not even.

Note: The INLINEABLE pragams in the link above are just an optimization, and can be ignored.

Answer 2

These functions are mutually recursive (each one can call the other one), with base cases. Lets follow an example evaluation using isOdd. First, I will start by changing the guards into the equivalent ifs for (hopefully) more clarity in this answer (though I would usually suggest using guards).

isOdd, isEven :: Int -> Bool
isOdd n =
  if n <= 0
    then False
    else isEven (n-1)

isEven n =
  if n < 0
    then False
    else if n == 0
           then True
           else isOdd (n-1)

Now, we can try stepping through an example evaluation^[1]:

    isOdd 3

==> if 3 <= 0                  (Applying isOdd to 5 and expanding the body)
      then False
      else isEven (3-1)

==> isEven (3-1)               (3 > 0)

==> if 2 < 0
      then False
      else if 2 == 0
             then True
             else isOdd (2-1)

==> isOdd (2-1)                (4 > 0, so the first two branches aren't taken)

==> if 1 <= 0                  (Applying isOdd to 1 and expanding the body)
      then False
      else isEven (1-1)

==> isEven 0

==> if 0 < 0
      then False
      else if 0 == 0
             then True
             else isOdd (0-1)

==> True                      (0 == 0, so the second branch is taken)

The intuition behind why these functions work is this: if a non-negative integer (natural number) n is greater than 0, it is odd if its predecessor (n-1) is even and it is even if its predecessor is odd. This is true since even and odd numbers alternate.

I would recommend stepping through an evaluation whenever you run into a function (or, in this case, pair of functions) that you don't understand using a small example like this.

_{^[1]: Note for something that doesn't really matter for this question: I've slightly simplified when the expressions of the shape x-1 get reduced to the corresponding number.}

Answer 3

this is called "mutual recursion" or "mutually recursive functions", as in the recursive functions you need to define the terminal state (or exit condition). However, your definition is not the best, here is a better alternative

isEven,isOdd :: Int -> Bool
isEven 0 = True
isEven n = isOdd  (n - 1)
isOdd  0 = False
isOdd  n = isEven (n - 1)

here the terminal condition is set for 0 (symmetrically) and mutual recursion will end up on one of them eventually.

Note that this is only defined for non-negative integers but not enforced with the type Int.

Your definition is not correct either but at least will terminate for negative numbers.