Haskell execution sequence
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 detects what is False and then switches to isEven, so how does haskell know when n is odd?
source to share
There are two different functions here: isOdd
and isEven
. They are defined in terms of each other: the number is "odd" if it is negative or zero, and "odd" if the number is less than "even". The number is "not equal" if it is negative, and "even" if it is equal to zero or one less than this number is "odd".
This is a rather unintuitive way of defining these functions, but it has nothing to do with "order of execution" or "order of evaluation". In fact, Haskell compilers can do whatever computation they want, as long as they give the correct value in the result and follow lazy / strict semantics as stated in the Haskell report.
The best implementation of these features is as follows: (from Prelude )
even, odd :: (Integral a) => a -> Bool
even n = n `rem` 2 == 0
odd = not . even
In other words, and an integer thing, even if the remainder when you divide it by 2 is 0, and odd if it isn't.
Note. The pragmas INLINEABLE
in the above link are just optimizations and can be ignored.
source to share
These functions are mutually recursive (each can call the other), with base cases. Let's see a rough estimate with isOdd
. First, I'll start by changing the guard to the equivalent if
for (hopefully) more clarity in this answer (although I 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 to execute the evaluation example [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 which these functions work is this: if a non-negative integer (natural number) is n
greater than 0
, it is odd if its predecessor ( n-1
) is even, and it is equal if its predecessor is odd. This is true because the odd and even numbers alternate.
I would recommend going through the evaluation every time you run a function (or, in this case, a pair of functions) that you don't understand using a small example like this.
[1] : Note something that doesn't really matter for this question: I've simplified a little when form expressions are x-1
reduced to the appropriate number.
source to share
this is called "mutual recursion" or "mutually recursive functions" because in recursive functions you need to define the terminal state (or exit condition). However, your definition is not the best, here is the best 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 given for 0
(symmetrically), and eventually mutual recursion will end up on one of them.
Note that this is only defined for non-negative integers, but does not apply to type Int
.
Your definition is wrong, but will at least end up for negative numbers.
source to share