CS 245 - Programming Languages

Homework 4

Elixir Programs

In this lab you will write four small programs in Elixir. Each of your programs should be it its own module and that module in its own file. (Yes, you could put them all in the same module, or all of the modules into a single file.)

Each module and public function should be documented using @moduledoc and @doc. (See code posted on the class website for examples.) Documentation does not need to be extensive, but should be sufficient to help the grader read and understand your code.

Each program should be accompanied by a set of tests sufficient to demonstrate that your program works. You may assume that someone else is checking for valid input. So the tests need only demonstrate that your program works on "good" input. For instance, in the first program, you may assume that the input is actually a list rather than a string or a tuple, ... However, you should have several list structures.

Part 1

Write a program which flattens lists of unlimited depth. Specifically, consider a list. The elements in the list are items which may be either something or lists. The contained lists abide by the same rule as the top level list. For example, the following is a legal list:

        [12, 6, [1, [2]],[3,4]]

Your program should "flatten" the provided list and return the flattened list. Items in the flattened list my be in any order. For instance, for the first example above, the following is an acceptable result:

        [6,12,3,4,1,2]

I have no idea why you program would produce such a result, but it would be OK. (One version of my implementation preserves order.)

Some thoughts:

there exists a function Enum.flat_map/2 that could do similar work. DO NOT use that.
Consider writing two versions of this program, one tail-recursive and one not. I strongly suggest actually writing the one that is NOT tail recursive.

Part 2

Write a module named Student that contains a struct with two properties: name and id_number. Within that module, add a function named register_students that takes a list of names and, optionally, a starting number. If no starting number is supplied, use 0. The function should return a list of Student structs. You function(s) should NOT contain any if (or case or cond). Do everything using matching.

For example:

IO.inspect Student.register_students(["mary", "jane", "grace"])
[
  %Student{id_number: 0, name: "mary"},
  %Student{id_number: 1, name: "jane"},
  %Student{id_number: 2, name: "grace"}
]


IO.inspect Student.register_students(["lily", "alana", "quinn"], 5501)
[
  %Student{id_number: 5501, name: "lily"},
  %Student{id_number: 5502, name: "alana"},
  %Student{id_number: 5503, name: "quinn"}
]

~~Implement two versions of register_students. In the first, write you own recursive function. In the second, use Enum.map rather than recursion.~~ Only one version is required. Implement both a recursive and Enum.map version for a 5 point bonus. (Do everything else before doing both.)

Finally, suppose you are given two lists of registered students. Write a function to return a single list, without duplications (where a duplication is defined as two students having the same ID number). Note that there may be duplications within each list and well as between the two lists. Hint: one fairly efficient approach is to first sort the combined lists and then remove duplicate neighbors (you can use Enum.sort and Enum.dedup to do so).

Part 3 -- Using Enum

Write a program using function(s) in Enum to do the following. Given a list of strings, return only those strings that are

in odd numbered positions in the list. That is if the list is [a,b,c,d,e] then you should only get [b, d] as they are in positions 1 and 3 (when you start counting from 0).
are longer than 5 characters

In your program:

do not use recursion (just use functions in Enum, in particular, the filter function).
use String.length to know the length of a string
Write this as a series of filters ... first filter for position, then filter for string length.
If you cannot figure out how to do this with just things from the Enum package, you may write a recursive function to do the filter by position portion of the task
Suggestion: use the elixir pipe command |> to take the output of 1 thing into the input of another.
Write this without using the map_index and filter_index functions described next.

Part 4 -- Indices

Almost totally missing from the Enum package are functions that are dependent on position in the list. So write two.

Start by creating a module named EnumIndex. Within this module you will create two functions, as described below:

map_index

The map_index function is very similar to Enum.map. It takes two arguments: a list and a function. Unlike map, the input function should take two parameters: a value from the list and the index of the index of the item in the list. Here is an example of the usage of map_index

    iex(1)> EnumIndex.map_index(["a", "s", "d", "f", "g"], fn (val, idx) -> {val, idx} end)

    [{"a", 0}, {"s", 1}, {"d", 2}, {"f", 3}, {"g", 4}]

filter_index

The filter_index function is very similar to Enum.filter. It takes two arguments: a list and a function. Unlike filter, the input function should take two parameters: a value from the list and the index of the index of the item in the list. Here is an example of the usage of filter_index

    iex(1)> EnumIndex.filter_index(["a", "s", "d", "f", "g"], fn (val, idx) -> idx>1 and val>"e" end)
    ["f", "g"]

Questions:

In part 1, I commented that the tail recursive version of the program was painful (to write). What about this problem makes tail recursion painful? (Hint, using tail recursion to search a binary tree is painful for the same reason.) Explain.
Why do you think that the Enum package not have functions to do things on the basis of indices? (Speculate, I do not think there is a "correct" answer.)
From the deduplication of Students. The approach I suggested involving sorting. So it is, at best, O(n lg n). A different approach would be heave everything into a map (i.e., ideally this would be a hashtable rather than a true basic map) with keys being ID numbers. Then since maps do not allow duplicate keys, all you need to do is read the map at the end to get the de-duplicated list. This procedure works well in imperative programming (it is O(n)). Does it work as well in Elixir? Explain.

What to hand in

A readme file with the usual contents. The readme should definitely include instructions on how to run the tests for each part. Ideally this would be as simple as Elixir part1.ex but it could be slightly more involved.
Answers to the three questions above. (They may be in the readme
Well written, adequately documented code for each part. In addition, tests for each part that adequately demonstrate that the code works. Testing output is not needed, I will run your rests

How to Submit

Put everything you want to submit in a directory containing nothing else. For instance you might name the directory a4

Go to the directory containing a4
Enter /home/gtowell/bin/submit -c 245 -p 4 -d a4

If this worked you will get a message with the word "success" and a listing of all the files you submitted.