CIs 554 Erlang Exercises
Fall 2014, David Matuszek

Purposes of this assignment


Write and test the following functions. Please be sure to get the spelling and capitalization right, and the right number and types of parameters, so that we can also test them when we do the grading.

These are mostly unrelated exercises, to give you some experience with Erlang syntax. The earlier ones depend on recursion, while the latter are best done using some of Erlang's second-order functions.

In some cases, for example reversing a list, you may find Erlang functions that already do exactly what you want. Please don't use them, but rather write the functions yourself, as if the Erlang equivalent didn't exist, prefixing the name with my_ (for example, reverse would become my_reverse).

First group

You don't need higher-order functions to program these, but if you see an opportunity to use them, go ahead. Generallly, the purpose is to get you used to writing recursive functions the Erlang way.

Defined for positive integers n. Returns a list starting with N. Each subsequent value is computed from the previous value according to this rule: Example: collatz(7) is [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1].

Reverses the elements of list Lst. For example, the list [1, 2, [3, 4]] becomes the list [[3, 4], 2, 1].

Removes duplicate elements of Lst. For example, given [1, 2, 3, 1, 4, 1, 2], remove-duplicates returns a list containing the elements [1, 2, 3, 4], in some order.

Returns as value the list Lst with all inner brackets removed, returning a "flat" list of values. For example, if Lst is [1, [2, 3], [ ], [[ ]], a], the result should be [1 2 3 a].

Removes all the non-list elements of list Lst, but retains all the list structure (the brackets). For example, if Lst is [1, [2, [3, 4]], 5, 6, [7], [ ]], the result is [[[ ]], [ ], [ ]].

Reverses the elements of L at all levels. For example, if Lst is [a, [b, c, [d]], e], deep-reverse should return [e, [[d], c, b], a].

eliminate(Value, Lst)
Returns the list Lst with all occurrences of the Value removed, at all levels, retaining the list (bracket) structure. For example, if Lst is [a, b, [b, c, d [a [b]]], e], eliminate(b, Lst) should return [a, [c, d, [a, []]], e]. Note that the value may be any value, for example, a list.

Return a quicksorted version of the given list. Use the lists:partition function.

Second group

These are all probably best done with higher-order functions, so please use them wherever they seem to work.

Remove from the given text all invalid ASCII characters. (Valid characters are decimal 10 (linefeed), 13 (carriage return) and 32 through 126, inclusive. Remember that Erlang has no "character" type; a "string" is just a list of ASCII values. Hint: filter.

Apply the rot-13 transformation to text. This is a simple encoding in which each letter is replaced by the letter 13 further along, end-around. Both uppercase and lowercase letters should be rotated; other characters should be unaffected. Hint: map.

Compute the square root of the positive number N, using Newton's method. That is, choose some arbitrary number, say 2, as the initial approximation R to the square root; then to get the next approximation, compute the average of R and N/R. Continue until you have five significant digits to the right of the decimal point. Do this by taking an infinite series of approximations, and taking approximations until they differ by less than 0.00001.

longest_collatz(Lo, Hi)
The Collatz sequence eventually converges to 1. Find which starting value, in the range Lo to Hi (including both end points) takes the longest to converge. If two values take equally long to converge, return either value.

Unit testing

Write unit tests for all your methods. Since we haven't talked about testing yet, here's a model for you to follow. The tests may be in the same file or in a separate file. If in a separate file, only exported functions may be tested directly.


fib(0) -> 1;
fib(1) -> 1;
fib(N) when N > 1 -> fib(N-1) + fib(N-2).

square(N) -> N * N.

fib_test_() ->
    [?_assert(fib(0) =:= 1),
     ?_assert(fib(1) =:= 1),
     ?_assert(fib(2) =:= 2),
     ?_assert(fib(3) =:= 3),
     ?_assert(fib(4) =:= 5),
     ?_assert(fib(5) =:= 8),
     ?_assertException(error, function_clause, fib(-1)),
     ?_assert(fib(31) =:= 2178309)

square_test_() ->
    [?_assert(square(0) =:= 0),
     ?_assert(square(1) =:= -1), % deliberate error
     ?_assert(square(5) =:= 25),
     ?_assert(square(-5) =:= 25)

Run this as:

1> cd("C:/Users/matuszek/Box Sync/Programming/Erlang_programs"). % substitute your path
C:/Users/matuszek/Box Sync/Programming/Erlang_programs
2> c(fib).
3> fib:test().

Due date:

Turn in your assignment by 6am Wednesday, September 24. You can turn in a single .erl file, or, if your tests are in a separate file, turn in a single .zip file containing both. As always, only files submitted to Canvas will be accepted.