List Ops

Instructions

Implement basic list operations.

In functional languages list operations like length, map, and reduce are very common. Implement a series of basic list operations, without using existing functions.

The precise number and names of the operations to be implemented will be track dependent to avoid conflicts with existing names, but the general operations you will implement include:

• append (given two lists, add all items in the second list to the end of the first list);
• concatenate (given a series of lists, combine all items in all lists into one flattened list);
• filter (given a predicate and a list, return the list of all items for which predicate(item) is True);
• length (given a list, return the total number of items within it);
• map (given a function and a list, return the list of the results of applying function(item) on all items);
• foldl (given a function, a list, and initial accumulator, fold (reduce) each item into the accumulator from the left);
• foldr (given a function, a list, and an initial accumulator, fold (reduce) each item into the accumulator from the right);
• reverse (given a list, return a list with all the original items, but in reversed order).

Note, the ordering in which arguments are passed to the fold functions (foldl, foldr) is significant.

Appendix

For this exercise in the Clojure track, assume both the input and output are vectors, as indicated by the tests. As a stretch goal, consider how to implement an approach that does not use lists for intermediate steps.

It is important not to reuse existing Clojure built-in functions with similar functionality, as doing so would diminish the intended learning value of the exercise. Key functions from the clojure.core namespace to avoid include into, concat, cat, lazy-cat, mapcat, flatten, filter, filterv, remove, count, map, mapv, reduce, transduce, reverse, and rseq.

Optional goals

The optional goal is for those who want an extra challenge and is designed with the expectation that you've already completed the main goal.

Try to pass the tests by devising an approach that assumes:

• Both the input and output are lists instead of vectors. Note that, as usual, the tests do not need to be modified.
• Vectors cannot be used for intermediate steps.

If you decide to publish this, be sure to include a comment indicating that it addresses the optional goal of using lists. Don't forget to update the docstrings!