Benjamin Halsted // [bgh] todo, add something clever here.

Erlang Programming Exercise: 3-1

I'm posting the exercises starting with chapter 3. The previous chapters have you work in the shell and don't require much file work. Exercise 3-1 is:

Write a function sum/1 which, given a positive integer N, will return the sum of all the integers between 1 and N.

And the second part:

Write a function sum/2 which, given two integers N and M, where N =< M, will return the sum of the interval between N and M. If N > M, you want your process to terminate abnormally.

Here is my solution: threeone.erl

-module(threeone).
-export([sum/1, sum/2]).

sum(1) ->
	1;
sum(Number) ->
	Number + sum(Number - 1).

sum(Lower, Lower) ->
	Lower;
sum(Lower, Upper) when Lower =< Upper ->
	Upper + sum(Lower, Upper-1).

If you give sum/1 a number less than 1, you'll infinite loop.

The above solution doesn't use Erlang's tail call optimizations. If you give them a very large set of numbers to add up, they keep eating up memory. I wanted to see what would happen when it ran out of memory or stack space, so I told it to sum up a billion. After my system started swapping and started to crawl I killed the process. Maybe next time.

Here is the reworked version that takes advantage of tail call optimization and can sum up numbers from 1 to a billion without making my system swap. The beam.smp process stays around 10mb of memory.

-module(threeone_tco).
-export([sum/1, sum/2]).

sum_range(Sum, Lower, Lower) ->
	Sum + Lower;
sum_range(Sum, Lower, Upper) ->
	sum_range(Sum + Upper, Lower, Upper-1).

sum(Number) when Number > 0 ->
	sum_range(0, 1, Number).

sum(Lower, Upper) when Lower =< Upper ->
	sum_range(0, Lower, Upper).

The big change comes from passing the Sum as an argument to the next function call. To use TCO (Tail Call Optimization) you want to leave no work to be done in your function, and the last thing your function does, should be calling itself. Previously, the function would still have to add two numbers after it's recursion finished.

Cheers,
-Halzy