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.

Implementing these list operations without using any built-in function is virtually impossible in Roc, because you need a way to append or prepend elements to a list. In other languages you might use operators such as : in Haskell or += in Python, but in Roc you have to use the List functions.

So for this exercise you're allowed to use List.append (but avoid using any other built-in function).

Many functional programming languages use linked lists as the primary collection type. It is efficient to prepend an element or pop the first element from a linked list, so in those languages, you would implement list operations using List.prepend. In Roc however, a List is an array (a contiguous chunk of bytes). Arrays have different properties than linked lists like the ability to efficiently access elements by index and append new elements. Because of this, in Roc we use List.append often and rarely use List.prepend.

Hint: try using:

when list is
    [] -> ????
    [first, .. as rest] -> ???

or

when list is
    [] -> ???
    [.. as rest, last] -> ???