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.
Execute the tests with:
$ elixir list_ops_test.exs
In the test suites, all but the first test have been skipped.
Once you get a test passing, you can unskip the next one by
commenting out the relevant @tag :pending
with a #
symbol.
For example:
# @tag :pending
test "shouting" do
assert Bob.hey("WATCH OUT!") == "Whoa, chill out!"
end
Or, you can enable all the tests by commenting out the
ExUnit.configure
line in the test suite.
# ExUnit.configure exclude: :pending, trace: true
For more detailed information about the Elixir track, please see the help page.
It's possible to submit an incomplete solution so you can see how others have completed the exercise.
if !System.get_env("EXERCISM_TEST_EXAMPLES") do
Code.load_file("list_ops.exs", __DIR__)
end
ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)
defmodule ListOpsTest do
alias ListOps, as: L
use ExUnit.Case
defp odd?(n), do: rem(n, 2) == 1
# @tag :pending
test "count of empty list" do
assert L.count([]) == 0
end
@tag :pending
test "count of normal list" do
assert L.count([1, 3, 5, 7]) == 4
end
@tag :pending
test "count of huge list" do
assert L.count(Enum.to_list(1..1_000_000)) == 1_000_000
end
@tag :pending
test "reverse of empty list" do
assert L.reverse([]) == []
end
@tag :pending
test "reverse of normal list" do
assert L.reverse([1, 3, 5, 7]) == [7, 5, 3, 1]
end
@tag :pending
test "reverse of huge list" do
assert L.reverse(Enum.to_list(1..1_000_000)) == Enum.to_list(1_000_000..1)
end
@tag :pending
test "map of empty list" do
assert L.map([], &(&1 + 1)) == []
end
@tag :pending
test "map of normal list" do
assert L.map([1, 3, 5, 7], &(&1 + 1)) == [2, 4, 6, 8]
end
@tag :pending
test "map of huge list" do
assert L.map(Enum.to_list(1..1_000_000), &(&1 + 1)) == Enum.to_list(2..1_000_001)
end
@tag :pending
test "filter of empty list" do
assert L.filter([], &odd?/1) == []
end
@tag :pending
test "filter of normal list" do
assert L.filter([1, 2, 3, 4], &odd?/1) == [1, 3]
end
@tag :pending
test "filter of huge list" do
assert L.filter(Enum.to_list(1..1_000_000), &odd?/1) == Enum.map(1..500_000, &(&1 * 2 - 1))
end
@tag :pending
test "reduce of empty list" do
assert L.reduce([], 0, &(&1 + &2)) == 0
end
@tag :pending
test "reduce of normal list" do
assert L.reduce([1, 2, 3, 4], -3, &(&1 + &2)) == 7
end
@tag :pending
test "reduce of huge list" do
assert L.reduce(Enum.to_list(1..1_000_000), 0, &(&1 + &2)) ==
Enum.reduce(1..1_000_000, 0, &(&1 + &2))
end
@tag :pending
test "reduce with non-commutative function" do
assert L.reduce([1, 2, 3, 4], 10, fn x, acc -> acc - x end) == 0
end
@tag :pending
test "append of empty lists" do
assert L.append([], []) == []
end
@tag :pending
test "append of empty and non-empty list" do
assert L.append([], [1, 2, 3, 4]) == [1, 2, 3, 4]
end
@tag :pending
test "append of non-empty and empty list" do
assert L.append([1, 2, 3, 4], []) == [1, 2, 3, 4]
end
@tag :pending
test "append of non-empty lists" do
assert L.append([1, 2, 3], [4, 5]) == [1, 2, 3, 4, 5]
end
@tag :pending
test "append of huge lists" do
assert L.append(Enum.to_list(1..1_000_000), Enum.to_list(1_000_001..2_000_000)) ==
Enum.to_list(1..2_000_000)
end
@tag :pending
test "concat of empty list of lists" do
assert L.concat([]) == []
end
@tag :pending
test "concat of normal list of lists" do
assert L.concat([[1, 2], [3], [], [4, 5, 6]]) == [1, 2, 3, 4, 5, 6]
end
@tag :pending
test "concat of huge list of small lists" do
assert L.concat(Enum.map(1..1_000_000, &[&1])) == Enum.to_list(1..1_000_000)
end
@tag :pending
test "concat of small list of huge lists" do
assert L.concat(Enum.map(0..9, &Enum.to_list((&1 * 100_000 + 1)..((&1 + 1) * 100_000)))) ==
Enum.to_list(1..1_000_000)
end
end
defmodule ListOps do
# Please don't use any external modules (especially List) in your
# implementation. The point of this exercise is to create these basic functions
# yourself.
#
# Note that `++` is a function from an external module (Kernel, which is
# automatically imported) and so shouldn't be used either.
@spec count(list) :: non_neg_integer
def count([]), do: 0
def count([_ | tail]), do: 1 + count(tail)
@spec reverse(list) :: list
def reverse(list), do: reverse(list, [])
defp reverse([], acc), do: acc
defp reverse([head | tail], acc), do: reverse(tail, [head | acc])
@spec map(list, (any -> any)) :: list
def map([], _), do: []
def map([head | tail], function), do: [function.(head) | map(tail, function)]
@spec filter(list, (any -> as_boolean(term))) :: list
def filter([], _), do: []
def filter([head | tail], function) do
if function.(head) do
[head | filter(tail, function)]
else
filter(tail, function)
end
end
@type acc :: any
@spec reduce(list, acc, (any, acc -> acc)) :: acc
def reduce([], acc, _), do: acc
def reduce([head | tail], acc, function), do: reduce(tail, function.(head, acc), function)
@spec append(list, list) :: list
def append(list_a, []), do: list_a
def append([], list_b), do: list_b
def append([head | tail], list_b), do: [head | append(tail, list_b)]
@spec concat([[any]]) :: [any]
def concat([]), do: []
def concat([head | tail]), do: append(head, concat(tail))
end
A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.
Here are some questions to help you reflect on this solution and learn the most from it.
Level up your programming skills with 3,450 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors. Exercism is 100% free forever.
Sign up Learn More
Community comments
See here for discussion about some advantages of tail call optimisation...