[Elixir] List Operations Implementation

함수형 프로그래밍 Enumerable Operations 구현 (1)

map, filter 같은 함수들은 Enum모듈, List모듈, Stream모듈 등 다양한 모듈에서 공통적으로 제공

Exercism의 List ops 문제를 푸는데, tail-call recursion을 써줘야 해서 조금 복잡하게 어찌됐든 문제를 풀었다.

대략 이런식으로 구현됨

  # map operation 구현
  @spec map(list, (any -> any)) :: list
  def map(l, f) do
    map_list(l, [], f)
  end

  defp map_list([], acc, _), do: reverse(acc)
  defp map_list([head | tail], acc, f) do
    map_list(tail, [f.(head) | acc], f)
  end

그런데 여기서, reduce 함수는 다음과 같이 구현된다.

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

이 reduce 함수의 동작을 잘 보면 map이나 다른 함수들의 구현이 reduce 함수 호출과 비슷해 보인다. 매 reduce의 호출에서, 첫번째 인자로 새로운 항목이 들어오고, 두번째 인자로 accumulate(누적값)이 들어오며, 세번째 인자로 각 항목에 적용되어 누적되어질 함수가 들어온다.

결국 모두 reduce로 구현할 수 있다는 걸 알 수 있다.

그러면 List operations들은 다음과 같이 구현된다.

defmodule ListOps do

  @spec count(list) :: non_neg_integer
  def count(l), do: reduce(l, 0, fn (_, acc) -> acc + 1 end)

  @spec reverse(list) :: list
  def reverse(l), do: reduce(l, [], &([&1 | &2]))

  @spec map(list, (any -> any)) :: list
  def map(l, f) do
    l
    |> reverse  # 뒤집어서 하나씩 떼어서 집어넣기 - 뒤에서부터 완성되는 느낌
    |> reduce([], &([f.(&1) | &2]))
  end

  @spec filter(list, (any -> as_boolean(term))) :: list
  def filter(l, f) do
    l
    |> reverse
    |> reduce([], &(if f.(&1), do: [&1 | &2], else: &2))
  end

  @type acc :: any
  @spec reduce(list, acc, ((any, acc) -> acc)) :: acc
  def reduce([], acc, _), do: acc
  def reduce([x | xs], acc, f), do:  reduce(xs, f.(x, acc), f)

  @spec append(list, list) :: list
  def append(a, b) do
    a
    |> reverse
    |> reduce(b, &([&1 | &2]))
  end

  @spec concat([[any]]) :: [any]
  def concat(l) do
    l
    |> reverse
    |> reduce([], &append/2)
  end
end