isLeapYear :: Integer -> Bool
isLeapYear year = divisibleBy 4 && (not (divisibleBy 100) || divisibleBy 400)
where
divisibleBy d = year `mod` d == 0
We can combine smaller logical statements into larger ones using the logical operators &&
(and), ||
(or), and not
(negation).
Precedence
In school they teach you that 2 + 3 * 4
is to be read as meaning 2 + (3 * 4)
.
This is a convention, chosen for its convenience.
We say that the *
operator has higher precedence than +
.
In logic similar ambiguities exist, and these are similarly resolved. By convention â€“ and so in Haskell â€“
- and has higher precedence than or, and
- not has higher precedence than both and and or.
For example, p || q && r
means the same as p || (q && r)
.
If you want to know the precedence of an operator, you can ask GHCi:
ghci> :info &&
...
infixr 3 &&
ghci> :info +
...
infixl 6 +
ghci> :info not
... -- no precedence information
Here, infixr 3 &&
indicates that &&
has precedence 3 and associates to the right.
Similarly, infixl 6 +
means that +
has precedence 6 and associates to the left.
No precedence is shown for not
, because none has been explicitly defined.
However, not
is just a regular function, and function application always has precedence 10.
The solution highlighted above uses parentheses to group two tests together that would otherwise be grouped apart.
That is, this solution has the shape P && (Q || R)
.
However, if the parentheses were removed the solution would still be correct!
Do you see why? Hint: fill out the truth tables for both versions.
This is not possible in general: sometimes (P && Q) || R
and P && (Q || R)
disagree.
The motivation for the parentheses in the highlighted solution is efficiency; see below.
An example of laziness
Just like in many other languages, Haskell's logical operators display short-circuiting behavior:
ghci> import Debug.Trace
ghci> -- `trace s x` prints the given string `s`
ghci> -- and immediately returns `x`.
ghci> cheap x = trace "Cheap computation" x
ghci> expensive x = trace "Expensive computation" x
ghci> cheap False && expensive True
Cheap computation
False
ghci> cheap True && expensive False
Cheap computation
Expensive computation
False
ghci> cheap True || expensive False
Cheap computation
True
ghci> cheap False || expensive False
Cheap computation
Expensive computation
False
Sometimes, the result is already completely determined by the left operand.
In such cases both &&
and ||
avoid unnecessary work by skipping evaluation of the right operand.
So far, so usual.
However, in contrast to many other languages, Haskell does not have this behavior built in specifically for the logical operators. In fact, these operators aren't built-in at all! Instead they are defined in the standard library, as follows.
(&&) :: Bool -> Bool -> Bool
True && x = x
False && _ = False
(||) :: Bool -> Bool -> Bool
True || _ = True
False || x = x
Both first pattern-match on their left operand to check whether it is True
or False
.
Next, depending on the match, they directly return the right operand or disregard it.
Because sometimes &&
and ||
do not evaluate their second operand, we say that they are lazy in their second argument.
In the Leap solution highlighted above, laziness results in the following checks being evaluated.
year | divisibleBy 4 |
divisibleBy 100 |
divisibleBy 400 |
is leap year |
---|---|---|---|---|
2020 | True |
False |
not evaluated | True |
2019 | False |
not evaluated | not evaluated | False |
2000 | True |
True |
True |
True |
1900 | True |
True |
False |
False |
Laziness of &&
and ||
and clever grouping ensure that only minimal effort is spent:
- 75% of all years are not multiples of 4. For these years only 1 test is done.
- 24% of all years are multiples of 4 but not of 100. For these, only 2 tests are done.
- For the remaining 1% of years, all 3 tests are done.
If we leave out the parentheses, i.e. check for divisibility by 4 and 100 together, the end result is the same but it takes more work to get there:
year | divisibleBy 4 |
divisibleBy 100 |
divisibleBy 400 |
is leap year |
---|---|---|---|---|
2020 | True |
False |
not evaluated | True |
2019 | False |
not evaluated | False |
False |
2000 | True |
True |
True |
True |
1900 | True |
True |
False |
False |
As you can see, this version always does at least 2 tests.