4
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?

duplode
  • 33,731
  • 7
  • 79
  • 150
user3358850
  • 129
  • 9
  • 2
    There's no reason to declare all negative integers as neither even nor odd. `isOdd n | n < 0 = isOdd (-n)` (and likewise for `isEven`) is perfectly sensible. – chepner Apr 22 '17 at 21:35

3 Answers3

4

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.

Lazersmoke
  • 1,741
  • 10
  • 16
  • What do you mean by "In fact, Haskell compilers are allowed to execute any computation they want as long as it gives the correct result."? – David Young Apr 22 '17 at 19:06
  • Haskell as a language only specifies the semantics of the language, so as long as the result is correct, they can perform any sort of optimization or execution model they want. For example, GHC might specialize `even` to the machine Word or machine Int to make it very slightly faster on those types. If it knows the value of something at compile time, it can even trim out unreachable cases. `let x = True in if x then 5 else 10` will optimize to just `5` because actually checking if True is True is a waste of time. When evaluating `f x y`, it can evaluate x or y first, and the result is the same – Lazersmoke Apr 22 '17 at 20:46
  • That is different than saying "Haskell compilers are allowed to execute any computation they want as long as it gives the correct result" because there are some formal rules about what parts of an expression a Haskell compiler evaluates and when. The Haskell 98/2010 Reports require a somewhat certain (non-strict) semantics of evaluation. There is an example [here](http://stackoverflow.com/questions/40328862/is-there-any-guarantee-about-the-evaluation-order-within-a-pattern-match). – David Young Apr 22 '17 at 21:00
  • What I think you are referring to are certain optimizations, which must be guaranteed to not be "visible" as changing the evaluation order given by the Haskell Reports (except as maybe changing time and/or space usage). – David Young Apr 22 '17 at 21:01
  • Not terminating/behavior around `_|_` is denotational semantics, not operational semantics. Strictness/laziness are part of the "result" and therefore must be preserved by optimizations. Execution is operational, evaluation is denotational. Execution is up to the compiler, evaluation is defined by Haskell's semantics. – Lazersmoke Apr 22 '17 at 21:38
  • My ultimate point is, Haskell compilers cannot compile code to execute the expressions in any order they want and saying that they can as long as it gets the (in my opinion) nebulous "correct result" seems a bit misleading. Haskell specifically has non-strict semantics (function arguments are only eval'd if they are used), which means it goes outside-in. In a very practical sense, if it evaluated the other way around, this would change the behavior of programs from what the Haskell Reports specify it should be (unless you have explicit strictness annotations, which the report allows for). – David Young Apr 22 '17 at 21:57
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.

David Young
  • 10,713
  • 2
  • 33
  • 47
  • sorry I'm confused, "(0 == 0, so the second branch is taken)" makes it sound like 3 should be even – user3358850 Apr 23 '17 at 01:21
  • @user3358850 In that step, `isEven` is being called with the argument `0` (which is even, since it is evenly divisible by `2`). The second branch there is the one that says `if 0 == 0 then True ...`. `True` is the final result of evaluating `isOdd 3`. The stuff in between are the steps taken to get from `isOdd 3` to the final result of `True`. The overall chain of logic, from a higher level perspective, is something like "To know if 3 is odd, see if 2 is even. To see if 2 is even, see if 1 is odd. To see if 1 is odd, see if 0 is even. 0 is even 'by definition' (so to speak)". – David Young Apr 23 '17 at 01:25
  • And since `0` is even, all those preceding statements are true (`1` is odd, `2` is even and, finally, `3` is odd). – David Young Apr 23 '17 at 01:32
0

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.

karakfa
  • 66,216
  • 7
  • 41
  • 56