Intermediate Exercism • haskell

Leap

Challenge Overview

Determine whether a given year is a leap year.

Visit the leap exercise on Exercism to read the full instructions and download the exercise files.

Dig Deeper

Logical expression

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:

```haskell
ghci> :info &&
...
infixr 3 &&
ghci> :info +
...
infixl 6 +
ghci> :info not
...  -- no precedence information
```

Here, `infixr 3 &&` indicates that `&&` has precedence 3 and [associates][wikipedia-associativity] 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.

[wikipedia-associativity]:
    https://en.wikipedia.org/wiki/Operator_associativity
    "Wikipedia: Operator associativity"

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][wikipedia-truth-table] 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.

[wikipedia-truth-table]:
    https://en.wikipedia.org/wiki/Truth_table
    "Wikipedia: Truth table"

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.

Guards

isLeapYear :: Integer -> Bool
isLeapYear year
  | indivisibleBy 4   = False
  | indivisibleBy 100 = True
  | indivisibleBy 400 = False
  | otherwise         = True
  where
    indivisibleBy d = year `mod` d /= 0

Guards

Guards can optionally be added to patterns to constrain when they should match. For example, in

ageCategory = case age of
  Just n | n >= 24 -> "Adult"
  Just n           -> "Nonadult"
  Nothing          -> "Eternal"

the pattern Just n will match both values Just 5 and Just 39, but the pattern Just n | n >= 24 will only match the latter. Because patterns are checked in order, here

Just 39 will match the first pattern and so result in "Adult", but
Just 5 will fall through to be matched to the second pattern, which will match, resulting in "Nonadult".

Patterns may contain multiple guards in sequence. These will then be checked in order just like patterns. The following variant on the above example produces exactly the same result.

ageCategory = case age of
  Just n | n >= 24   -> "Adult"
         | otherwise -> "Nonadult"
  Nothing            -> "Eternal"

Here there is one fewer pattern, but the first one contains one more guard. otherwise is a synonym of True: it is the guard that always succeeds.

Sequences of guards are analogous to if–else if chains in other languages.

In this approach

When there are not many cases to match against, it is common to use function definition syntactic sugar instead of case because sometimes that is a bit nicer to read.

categorize (Just n)
  | n >= 24        = "Adult"
  | otherwise      = "Nonadult"
categorize Nothing = "Eternal"
-- is equivalent to / an abbreviation of
categorize age = case age of
  Just n | n >= 24   -> "Adult"
         | otherwise -> "Nonadult"
  Nothing            -> "Eternal"

In the case of Leap, there aren’t any interesting patterns to match against, so we only match against a name.

-- A "binding pattern", just like `n` above.
--          👇
isLeapYear year
  | ...

It turns out that, if we are careful to ask questions in the right order, we can always potentially attain certainty about the answer by asking one more question.

If the year is not divisible by 4, then it is certainly not a leap year.
If it is, then it might be a leap year.
- If divisible by 4 but not by 100, then it certainly is a leap year.
- If also divisible by 100, then it might be a leap year.
  - If divisible by 4 and 100 but not by 400, then it is certainly not a leap year.
  - Otherwise, i.e. if also divisible by 400, then it certainly is a leap year.

We can encode this sequence of checks using guards as follows.

isLeapYear year
  | indivisibleBy 4   = False
  | indivisibleBy 100 = True
  | indivisibleBy 400 = False
  | otherwise         = True
  where
    indivisibleBy d = year `mod` d /= 0

We need not start checking for divisibility by 4 specifically. Starting with 400 is also possible, but our checks and outcomes will be flipped:

isLeapYear :: Integer -> Bool
isLeapYear year
  | divisibleBy 400 = True
  | divisibleBy 100 = False
  | divisibleBy   4 = True
  | otherwise       = False
  where
    divisibleBy d = year `mod` d == 0

Starting with 100 is more complicated: both years divisible by 100 and years not divisible by 100 sometimes are and sometimes aren’t leap years. Using guards is still possible, but it necessarily looks different:

isLeapYear year
  | divisibleBy 100 = divisibleBy 400
  | otherwise       = divisibleBy   4
  where
    divisibleBy d = year `mod` d == 0

This is very similar to the conditional expression approach.

When to use guards?

Many beginning Haskellers write code like

fromMaybe :: a -> Maybe a -> a
fromMaybe x m
  | isJust m  = fromJust m
  | otherwise = x

fromMaybe :: a -> Maybe a -> a
fromMaybe x m
  | m == Nothing = x
  | otherwise    = fromJust m

Don’t do this. Use case instead, whenever possible. The compiler will be much more able to help you if you do, such as by checking that you have covered all possible cases. It is also nicer to read.

Use guards

to narrow down when patterns should match, or
in lieu of other languages’ if–else if chains.

Because guards are not themselves expressions, the latter use is not always possible. In such cases, the MultiWayIf language extension has your back:

{- LANGUAGE MultiWayIf -}  -- at the top of the file

_ = if | condition   -> expression
       | proposition -> branch
       | otherwise   -> alternative
-- which is syntactic sugar for
_ = case () of
  _ | condition   -> expression
  _ | proposition -> branch
  _ | otherwise   -> alternative

For more on this question, see Guards vs. if-then-else vs. cases in Haskell on StackOverflow.

Conditional expression

isLeapYear :: Integer -> Bool
isLeapYear year =
  if divisibleBy 100
    then divisibleBy 400
    else divisibleBy 4
  where
    divisibleBy d = year `mod` d == 0

Conditional expressions

A conditional expression (if … then … else …) is a compound expression that uses a test to determine which of two alternatives to evaluate to. Many other languages feature a similar construct, often termed ‘ternary operator’. They are also known as if expressions.

When p is some expression of type Bool and t and f are any two expressions of the same type, then if p then t else f will

evaluate to t if p evaluates to True, and
evaluate to f if p evaluates to False.

Conditional expressions are [syntactic sugar][wikipedia-syntactic-sugar] for certain `case` expressions:

```haskell
_ = if p then t else f
-- is an abbreviation of
_ = case p of
  True  -> t
  False -> f
```

[wikipedia-syntactic-sugar]:
    https://en.wikipedia.org/wiki/Syntactic_sugar
    "Wikipedia: Syntactic sugar"

In this approach

This approach uses exactly two tests to determine whether a year is a leap year.

The first test is for divisibility by 100. Once we know if the year is a multiple of 100, we know which further test to perform.

If the year is evenly divisible by 100, then divisibleBy 100 will evaluate to True and the entire if expression will evaluate to whatever divisibleBy 400 evaluates to.
If the year is not evenly divisible by 100, then divisibleBy 100 is False and so the if expression evaluates to divisibleBy 4.

When to use `if`?

if expressions might be a good fit when you

need an expression that
chooses between exactly two options
depending on a single Bool.

When you have something other than a Bool, use case instead.

When you do not strictly need an expression, an alternative is to use guards.

When you need to choose between more than two options, guards might be the solution. However, guards are not expressions and so are not always applicable. In such cases you might want to break out a multi-way if, available through the MultiWayIf language extension:

{- LANGUAGE MultiWayIf -}  -- at the top of the file

_ = if | condition   -> expression
       | proposition -> branch
       | otherwise   -> alternative
-- which is syntactic sugar for
_ = case () of
  _ | condition   -> expression
  _ | proposition -> branch
  _ | otherwise   -> alternative

For more on this question, see Guards vs. if-then-else vs. cases in Haskell on StackOverflow.

An example of lazy evaluation

Just like ‘ternary operators’ in other languages, conditional expressions evaluate lazily. Specifically, only the relevant branch is evaluated:

ghci> error "Crash!"  -- for demonstration
*** Exception: Crash!
ghci> if even 42 then "Success!" else error "Crash!"
"Success!"

Notice how evaluating the entire if expression does not result in a crash, even though one of its branches would if it were evaluated.

In our solution above we have

year	`divisibleBy 100`	`divisibleBy 400`	`divisibleBy 4`	is leap year
2020	`False`	not evaluated	`True`	`True`
2019	`False`	not evaluated	`False`	`False`
2000	`True`	`True`	not evaluated	`True`
1900	`True`	`False`	not evaluated	`False`

Source: Exercism haskell/leap