Avatar of davearonson

davearonson's solution

to List Ops in the Elixir Track

Published at Jul 13 2018 · 1 comment
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

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.

Running tests

Execute the tests with:

$ elixir list_ops_test.exs

Pending tests

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.

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

list_ops_test.exs

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(l) do
    do_count(l, 0)
  end
  defp do_count([], acc), do: acc
  defp do_count([_|tail], acc), do: do_count(tail, acc + 1)

  @spec reverse(list) :: list
  def reverse(l) do
    do_reverse(l, [])
  end
  defp do_reverse([], acc), do: acc
  defp do_reverse([head|tail], acc), do: do_reverse(tail, [head | acc])

  @spec map(list, (any -> any)) :: list
  def map(l, f) do
    do_map(l, f, [])
  end
  defp do_map([], _, acc), do: acc
  defp do_map([head|tail], f, acc), do: [f.(head) | do_map(tail, f, acc)]

  @spec filter(list, (any -> as_boolean(term))) :: list
  def filter(l, f) do
    do_filter(l, f, [])
  end
  defp do_filter([], _, acc), do: acc
  defp do_filter([head|tail], f, acc) do
    prepend_if_true(head, do_filter(tail, f, acc), f.(head))
  end
  defp prepend_if_true(item, list, decider) do
    if decider, do: [item | list], else: list
  end

  @type acc :: any
  @spec reduce(list, acc, ((any, acc) -> acc)) :: acc
  def reduce(l, acc, f) do
    do_reduce(l, acc, f)
  end
  defp do_reduce([], acc, _), do: acc
  defp do_reduce([head|tail], acc, f), do: do_reduce(tail, f.(head, acc), f)

  @spec append(list, list) :: list
  def append(a, b) do
    do_append(a, b)
  end
  defp do_append([], acc), do: acc
  defp do_append([head|tail], acc), do: [head | do_append(tail, acc)]

  @spec concat([[any]]) :: [any]
  def concat(ll) do
    do_concat(ll, [])
  end
  defp do_concat([], acc), do: acc
  defp do_concat([head|tail], acc), do: append(head, do_concat(tail, acc))
end

Community comments

Find this solution interesting? Ask the author a question to learn more.
Avatar of davearonson

Had some difficulty with this one, trying to figure out how to append an item to a list. I still don't quite grok the | operator. Also, the initial version of concat had lousy performance due to passing the accumulator to append as the one it would move, making that horribly inefficient -- the current version passes the accumulator to append as the piece to be added to, so it doesn't cycle through that. That took it from "took so long I wondered if it was stuck so I killed it", to "a bit long for a test". :-)

What can you learn from this solution?

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.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?