Skip to content

A Tale of Two Functions

April 21, 2013

When covering the matter of mutually-recursive functions the first Edition of Programming F# comes up with the following sample on page 55:

let rec isOdd n = (n = 1) || isEven (n - 1)
and isEven n = (n = 0) || isOdd (n - 1)

Looks beautiful, but unfortunately does not work. The second Edition Programming F# 3.0 attempts fixing the problem with the following code on page 60:

let rec isOdd x =
    if x = 0 then false
    elif x = 1 then true
    else isEven(x - 1)
and isEven x =
    if x = 0 then true
    elif x = 1 then false
    else isOdd(x - 1)

This snippet works correctly, but it got four times longer, than the original and apparently smells. May it be refactored towards DRY? Sure, for example:

let rec isOdd = function
| 0 | 1 as n -> (n = 1)
| n -> isEven (n - 1)
and isEven n = isOdd (n - 1)

Good, but still 100% longer, than the original, so let’s keep trying:

let rec isOdd n = if n >= 2 then isEven (n - 1) else n = 1
and isEven n = if n >= 2 then isOdd (n - 1) else n = 0

Cool, this works correctly and is as succinct as the original. But wait a minute, boolean if-then-else expression can be rewritten to the equivalent expression using && and || operators:

let rec isOdd n = n >= 2 && isEven (n - 1) || n = 1
and isEven n = n >= 2 && isOdd (n - 1) || n = 0

Almost perfect, but what if we out of curiosity try something like isOdd 10000000? Oh,no! Although equivalent to previous snippet, the latest one gets not tail-recursive and blows the stack.

OK, let’s convert it back to a tail-recursive equivalent:

let rec isOdd n = n = 1 || n >= 2 && isEven (n - 1) 
and isEven n = n = 0 || n >= 2 && isOdd (n - 1)

or even to just another tail-recursive equivalent:

let rec isOdd n = n < 2 && n = 1 || isEven (n - 1) 
and isEven n = n < 2 && n = 0 || isOdd (n - 1)

The latest snippet is almost similar to the original, but works perfectly.

The bottom line: often a boolean expression may perfectly substitute one built with if-then-else. But watch for subtleties, like inadvertently losing tail-recursiveness.

Advertisements

From → F#

4 Comments
  1. This blog was… how do I say it? Relevant!! Finally I have found something which
    helped me. Appreciate it!

  2. Phil Nguyen permalink

    What is is not ok to just write:

    let rec isOdd n = not (n = 0) && isEven (n – 1)
    and isEven n = (n = 0) || isOdd (n – 1)

    , assume we ignore negative numbers?

    • Phil, nothing is “wrong” with your snippet, it is algorithmically correct. Although seeing its correctness and the way it works is, in my opinion, harder, than for one based on logical OR only, as was the original intent of Chris Smith in the book.

Trackbacks & Pingbacks

  1. F# Weekly #17, 2013 | Sergey Tihon's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: