Today I Learned (23.03.10)

List와 Recursive

• Elixir의 List가 타 프로그래밍 언어와 다른 점
  : 일반적인 프로그래밍 언어에서는 List를 순회대상으로 여기며 반복문으로 다루는 것이 당연한 것으로 여겨진다.

하지만 Elixir에서 List는 Linked List이다. 즉 다시 말해 Elixir에서 List는 아래와 같이 head와 tail로 나눌 수 있다.

[head | tail]

여기서 head는 값을 담고, tail은 그 이외의 값을 담고 있는 리스트이다. 그렇다면 다음과 같은 일반적인 리스트를 생각해보자.

[1,2,3]

Elixir에서는 파이프 기호를 통해 head와 tail을 구분한다. Elixir의 문법으로 다시 쓴 리스트의 모습은 다음과 같다.

[1 | [2,3] ]

하지만 tail도 역시 리스트이기 때문에 다시 다음과 같이 나눌 수 있다.

[1 | [ 2 | [ 3 ] ]

이렇게 Elixir는 리스트를 재귀적으로 풀어나갈 수 있기 때문에 반복문을 이용하여 순회하는 방법론을 가진 일반적인 프로그래밍 언어와 다른 방식으로 접근 할 수 있다.

예를 들어 엘릭서에서 리스트의 길이를 구하는 len()을 구현해본다고 가정하자. len()은 다음과 같이 구현할 수 있다.

defmodule CustomList do
	def len([]), do: 0
	def len([head | tail]), do: 1 + len(tail)
end

여기서 가장 이해하기 어려운 부분이 def len([head | tail]) ... 부분일 것이다. 하지만 조금만 생각해보면 Elixir가 얼마나 우아한 방식으로 문제를 해결 하는지 알 수 있을것이다.

def len([head | tail])... 은 비어있지 않은 모든 리스트에 패턴 매칭 된다. 여기서 head는 리스트의 첫번째 값을, tail은 나머지 리스트를 가지게 된다. 재귀적으로 호출한 len() 함수는 다음과 같이 동작한다.

len([1,2,3,4,5])
= 1 + len([2,3,4,5])
= 1 + 1 + len([3,4,5])
= 1 + 1 + 1 + len([4,5])
= 1 + 1 + 1 + 1 + len([5])
= 1 + 1 + 1 + 1 + 1 + len([])
= 1 + 1 + 1 + 1 + 1 + 0
= 5

• List를 더 자세하게 다루어 보기

위에서 살펴본 재귀적 방식으로, 리스트의 값에 일정한 값을 더하거나 제곱하는 함수를 만들 수 있다.

defmodule CustomList do
	def square([]), do: []
	def square([head | tail]), do: [head * head | square(tail)]
end

defmodule CustomList do
	def add_one([]), do: []
	def add_one([head | tail]), do: [head+1 | add_one(tail])
end

여기서 조금 더 나아가서 생각해보자. 다른 프로그래밍 언어에서처럼 함수를 받는 map 함수를 만들수도 있지 않을까?

defmodule CustomList do
	def map([],_func), do: []
	def map([head | tail], func), do: [func.(head) | map(tail)]
end

이렇게 만든 map 함수는 다음과 같이 테스트 해볼 수 있다.

iex MyList.exs

iex> CustomList.map [1,2,3,4], fn (n) -> n*n end
[1,4,9,16]

iex> CustomList.map [1,2,3,4], fn (n) -> n+1 end
[2,3,4,5]

iex> CustomeList.map [1,2,3,4], &(&1*&1) end
[1,4,9,16]

• 리스트의 값을 하나로 만들어보기
  위에서 구현한 map/2 는 리스트의 각 값에 독립적으로 함수를 적용하는 개념을 추상화한 함수이다. 그렇다면 리스트에 있는 모든 값을 더하거나, 최댓값을 구하는 작업은 어떻게 구현해야 할까?

나는 다음과 같이 대략적으로 추상화 해보았다.

#reduce(list, init_value,func)

reduce([],value,_func) -> value
reduce([head|tail], value, func) -> reduce(tail,func.(head,value),func)

실제로 구현해본 코드는 다음과 같다.

defmodule CustomList do
def reduce([],value,_) do
	value
end

def reduce([head|tail],value,func) do
	reduce(tail,func.(head,value),func)
end

위 코드는 다음과 같이 실행 시켜볼 수 있다.

iex> MyList.reduce([1,2,3,4,5],0,&(&1+&2))
15
iex> MyList.reduce([1,2,3,4,5],1,&(&1*&2))
120

• 여러가지 생각해보기: MapSum, Max, 시저함수 구현해보기

• MapSum
  내가 구현해본 코드

def mapsum(map_list, func, value \\ 0)

def mapsum([], _func, value) do
   value
end

def mapsum([head | tail], func, value) do
   mapsum(tail, func, value + func.(head))
end

MapSum 함수는 상대적으로 쉬웠다. 재귀적으로 value에 head에 함수를 적용한 값을 계속해서 더해주면 끝.

• Max
  내가 구현해본 코드

def my_max(list, value \\ 0)

def my_max([], value) do
    value
end

def my_max([head | tail], value) when value > head do
    my_max(tail, value)
end

def my_max([head | tail], value) when value < head do
    my_max(tail, head)
end

Max 함수 역시도 Guard 조건절을 이용해 재귀적으로 최댓값인 값을 갱신해준다. 그렇게 어렵지 않았다.

• 시저함수
  내가 구현해본 코드

def caesar("", _n) do
    []
  end

def caesar(list, n) do
    [head | tail] = String.split(list, "", trim: true)
    <<v::utf8>> = head
    ascii = if v + n < ?z, do: v + n, else: ?a + rem(v + n, ?z) - 1
    letter = List.to_string([ascii])
    tail = Enum.join(tail, "")
    [letter | caesar(tail, n)]
  end

시저함수는 코드가 좀 엘릭서스러운것 같진 않은것 같다… 분명 더 나은 방법이 있으리라 생각된다.

우선 받은 문자열 리터럴을 Split 해주고, 패턴 매칭을 통해 아스키 코드를 추출한다. 만약 아스키코드+n 값이 z 아스키코드 값을 넘어가면, 나머지 연산을 통해 a로 다시 돌아가게끔 만들고 아니라면 그냥 n을 더한다.

쪼갠 문자열 리터럴을 다시 하나의 문자열로 Join하고 이를 다른 문자열에서도 수행 할 수 있도록 tail에 재귀적으로 함수를 호출한다.

분명히 더 우아한 방법이 있으리라 생각된다. 하지만 일단은 내 뇌로는 여기까지가 한계이다..

• 더 복잡한 리스트 패턴에 관해

• 요소를 바꾸는 Swapper

defmodule Swapper do
  def swap([]), do: []
  def swap([a, b | tail]), do: [b, a | swap(tail)]
  def swap([_]), do: raise("Can't swap a list with an odd number of list.")
end

위 함수에서 주의깊게 봐야 할 부분은 함수의 세번째 정의이다.

def swap([_]), do: raise("Can't swap a list with an odd number of list.")

재귀 호출을 수행했을때 값이 단 하나가 남아있는 경우를 의미하며, 리스트의 길이가 홀수라는 의미이므로 에러를 호출한다.

• 리스트의 리스트에서 원하는 값을 찾기
  이번에는 실전에서도 요긴하게 써먹을듯한 예제이다. 가령 데이터베이스에 다음과 같은 날씨 레코드들이 있다고 생각해보자.

[timestamp, location_id, temp, rain]

여기서 location_id=27 인 값을 찾고 싶다고 해보자. 엘릭서 방식으로 말이다.

defmodule WeatherDatabase do
	def find_id_27([]), do: []
	def find_id_27([time, 27, temp, rain | tail]) do
		[ [time, 27, temp, rain] | find_id_27(tail)]
	end

	def find_id_27([_|tail]), do: find_id_27(tail)
end

여기서 주목해야할 부분은 함수의 두번째 정의이다.

def find_id_27([time, 27, temp, rain | tail]) do
		[ [time, 27, temp, rain] | find_id_27(tail)]
	end

우리는 지금까지 리스트의 첫번째 값을 head라는 변수에 매칭했으나, 이번에는 패턴 매칭을 통해 조건을 부여하고 있다.

패턴에 매칭되기 위해서는 기존의 head 부분이 리스트여야 하고, 그 리스트의 id값은 27이여야 매칭이 된다.

def find_id_27([_|tail]), do: find_id_27(tail)

하지만 id가 27이 아닐 경우에도 생각해야 한다. 그래서 두번째 함수 정의에서 head 가 매칭이 안될 경우에는 다른 리스트들을 계속해서 찾도록 재귀적으로 호출한다.

위 코드를 사용자가 원하는 id 값을 찾도록 개선하면 다음과 같다.

defmodule WeatherDatabase do
  def find_id([], _target_loc), do: []

  def find_id([head = [_, target_loc, _, _] | tail], target_loc) do
    [head | find_id(tail, target_loc)]
  end

  def find_id([_ | tail], target_loc), do: find_id(tail, target_loc)
end

• 위에서 배운것을 토대로 Span 함수 구현해보기
  Span 함수는 from 과 to를 파라미터로 가지며, from에서 to 까지의 숫자를 리스트로 반환한다.

내가 구현한 코드

def span(from, to, list \\ [])

  def span(from, to, list) when from == to do
    list
  end

  def span(from, to, []) do
    span(from, to, [to])
  end

  def span(from, to, list) when from < to do
    span(from, to - 1, [to - 1 | list])
  end

기존에 했던것과 조금 다르게 생각해서, 리스트를 거꾸로 돌아간다고 생각하고 코드를 짜보았다,

리스트에 head에는 계속해서 to-1 값이 들어가고, tail 부분은 지금까지 쌓여왔던 리스트를 넣어 재귀적으로 호출한다. 좀 더 쉽게 풀어보자면 아래와 같을 것이다.

iex> span(1,10)

list = [10]
list = [9 | [10]]
list = [8 | [9,10]]
list = [7 | [8,9,10]]
...

이렇게 계속해서 호출하다 보면 from 과 to가 같아지는 경우가 생길 것이고, 그때는 재귀 호출이 완료된것으로 간주하여 리스트를 출력한다. 참 쉽죠?