Using Recursion to Loop in Elm

This post is centered on the following problem:

Find the difference between the square of the sum and the sum of the squares of the first N natural numbers.

The square of the sum of the first ten natural numbers is (1 + 2 + ... + 10)² = 55² = 3025.

The sum of the squares of the first ten natural numbers is 1² + 2² + ... + 10² = 385.

Hence the difference between the square of the sum of the first ten natural numbers and the sum of the squares of the first ten natural numbers is 3025 - 385 = 2640.

Credit for the problem goes to exercism.io.

The plan is to first solve it with a for loop in Javascript, then solve it with recursion in Javascript, and finally translate the recursive solution to Elm.

With a for Loop

The for loop solution, in barely-pseudocode looks like this:

-- get the square of the sum of n by:
  -- going from 1 to n
  -- and adding each number to a total
-- return the total after the loop is done

-- get the sum of the squares of n by:
  -- going from 1 to n
  -- and adding the square of each number to a total
-- return the total after the loop is done

-- subtract the latter from the former

Translated to Javascript, we get this:

function squareOfSum(number) {
  let sum = 0;
  for (let i = 1; i <= number; i++) {
    sum += i;
  }
  return Math.pow(sum, 2);
}

function sumOfSquares(number) {
  let sum = 0;
  for (let i = 1; i <= number; i++) {
    sum += Math.pow(i, 2);
  }
  return sum;
}

function difference(number) {
  return squareOfSum(number) - sumOfSquares(number);
}

console.log(difference(10) === 2640); // true

Thanks to my extensive test suite, I can confidently refactor and use recursion instead.

In Order to Understand Recursion...

The recursive equivalent of the above solution goes like this:

-- get the square of the sum of n by:
  -- getting the triangular number for n by:
    -- returning 0 if n is 0
    -- adding n to the triangular number of n - 1

-- get the sum of the squares of n by:
  -- returning 0 if n is 0
  -- adding the square of n to the sum of the squares of n - 1

-- subtract the latter from the former

So, recursion is acting as a different way of looping by defining an action for each number n down to 1 and a final action to end the loop when n gets to 0.

I googled "factorial with adding instead of multiplying" and found "triangular numbers", so the function for calculating the sum of positive integers from 1 to N is called triangulate 🤷🏻‍♂️.

Let's write that function first:

function triangulate(n) {
  if (n === 0) {
    return 0;
  } else {
    return n + triangulate(n - 1);
  }
}

// which can be simplified to:

function triangulate(n) {
  return n === 0 ? 0 : n + triangulate(n - 1);
}

Using the triangulate function, we can get the squareOfSum function:

function squareOfSum(n) {
  const sum = triangulate(n);
  return Math.pow(sum, 2);
}

The sumOfSquares function can also use recursion:

function sumOfSquares(n) {
  if (n === 0) {
    return 0;
  } else {
    return Math.pow(n, 2) + sumOfSquares(n - 1);
  }
}

// again, can be reduced to..

function sumOfSquares(n) {
  return n === 0 ? Math.pow(n, 2) + sumOfSquares(n - 1);
}

One final thought on the Javascript solution is to make triangulate a bit more generic and add a second parameter for an exponent.

const triangulate = (n, exp = 1) => 
  n === 0
  ? 0
  : Math.pow(n, exp) + triangulate(n - 1, exp);

Then sumOfSquares can be written as the following:

function sumOfSquares(n) {
  return triangulate(n, 2);
}

How about some Elm?

Elm doesn't have for loops. Whaaaaa

Yea, for real.

Luckily, we already know this problem can be solved without a for loop. So what's the Elm equivalent of the recursive solution above? Well, let's refactor sumOfSquares just one more time in Javascript, using a switch statement with only two cases this time.

function sumOfSquares(n) {
  switch (n) {
    case 0:
      return 0;
    default:
      return Math.pow(n, 2) + sumOfSquares(n - 1);
  }
}

Elm has a case statement, so a nearly equivalent function will work:

sumOfSquares : Int -> Int
sumOfSquares n =
  case n of
    0 -> 0
    _ -> (n ^ 2) + sumOfSquares (n - 1)

We can apply a similar approach to squareOfSum:

squareOfSum : Int -> Int
squareOfSum n = 
  let
    triangulate x =
      case x of
          0 -> 0
          _ -> x + triangulate (x - 1)
  in 
    (triangulate n) ^ 2

Then the final function difference is just:

difference : Int -> Int
difference n =
  (squareOfSum n) - (sumOfSquares n)

And voila, we have solved a for-loop-friendly problem in Elm, a language with no for loop.

A Better Way?

While we can use recursion to loop through the numbers between 0 and N, we can also make use of other utilities exposed in Elm Core.

For example, List.range and List.sum make this problem much easier.

import List exposing (map, range, sum)


square : Int -> Int
square n =
    n ^ 2


squareOfSum : Int -> Int
squareOfSum n =
    range 1 n |> sum |> square


sumOfSquares : Int -> Int
sumOfSquares n =
    range 1 n |> map square |> sum


difference : Int -> Int
difference n =
    squareOfSum n - sumOfSquares n

Since for loops are one of the first things we learn as programmers, it's easy to fall back on for loops in solutions to everyday problems. Using Elm has taught me that for loops aren't necessary most of the time and seeking a different solution can lead to more declarative and readable code.

Thanks for reading :)

Comments

[1hko]

Here's another way to write diff(n) that computes in linear space and time. Another important distinction is the result is computed in a single n-sized loop instead of multiple loops

sq : Int -> Int
sq n =
    n * n


diff : Int -> Int
diff n =
    let
        loop sum squares n =
            if n == 0 then
                sq sum - squares
            else
                loop (sum + n) (squares + sq n) (n - 1)
    in
        loop 0 0 n


diff 10 == 2640

You could also implement loop generically using a union type and then implement diff with loop

type Loop state result
    = Recur state
    | Done result


loop : state -> (state -> Loop state result) -> result
loop init f =
    case (f init) of
        Recur state ->
            loop state f

        Done value ->
            value


diff : Int -> Int
diff n =
    loop ( 0, 0, n ) <|
        \( sum, squares, n ) ->
            if n == 0 then
                Done (sq sum - squares)
            else
                Recur ( sum + n, squares + sq n, n - 1 )

diff 10 == 2640

Both implementations are tail recursive and do not grow the stack