Joinc Wiki: List를 이용한 프로그래밍

Facebook Joinc 그룹 Joinc QA 사이트

현재위치 : 미니사이트>Erlang>Getting_Started_With_Erlang>Chapter_03

joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다.

List 소개

erlang는 list를 지원한다.
list 는 [와]로 표현되며, 각 원소는 ,를 이용해서 구분이 된다. 예를 들자면 [E1, E2, E3,....]식으로 list를 표현할 수 있다. 이 리스트의 원소는 E1, E2, E3, ... 가 된다.

rt(3)표준 퀵정렬함수

퀵소트와 Priority큐와의 성능비교
- 기호로 표시하자면 [E1,E2,E3,...,En|Variable], where n >= 1 이 된다.

List를 다루기 위한 내장함수들

erlang는 리스트와 다른 데이터 타입간의 변환을 위한 다양한 내장함수를 가지고 있다.

atom_to_list(A)

atom A를 ASCII 문자코드 리스트로 변환한다.
예) atom_to_list(hello) => [104,101,108,108,111]

float_to_list(F)

float point 숫자 F를 ASCII 문자코드의 리스트로 변환한다.
예) float_to_list(1.5) => [49,46,53,48,48,...,48].

integer_to_list(I)

integer형 숫자 I를 ASCII 문자코드로 변환한다.
예) integer_to_list(1245) => [49, 50, 52, 53].

list_to_atom(L)

ASCII 문자코드 리스트 L을 atom으로 변환한다.

예) list_to_atom([119,111,114,108,100]) => world.

list_to_float(L)

ASCII 문자코드 리스트 L을 floating point 숫자로 변환한다.
예) list_to_float([51,46,49,52,49,53,57])] => 3.14159

list_to_integer(L)

ASCII 문자코드 리스트 L을 integer 형으로 변환한다.
예) list_to_integer([49,50,51,52]) => 1234.

hd(L)

리스트 L의 첫번째 원소를 되돌려준다.
예) hd([a,b,c,d]) => a.

tl(L)

리스트 L에서 처음원소를 제외한 나머지 - tail -을 리턴한다.
예) tl([a,b,c,d])

length(L)

리스트 L의 원소 갯수를 리턴한다.
예) length([a,b,c,d]) => 4.

일반적인 리스트 함수

여기에서는 간단한 리스트 함수들에 대해서 알아볼 것이다. 이하 설명하는 모든 리스트함수들은 lists module에 포함된다.

재귀호출을 이용해서 문제가 이해하기 쉽게 기술되었다는 점이 인상깊다.
==== member ===
member(X, L) 만약 X가 리스트 L의 원소라면 참을 그렇지 않다면 거짓을 리턴한다. 이 함수는 다음과 같이 정의되어 있다.

member(X, X|_) -> true;
member(X, _|T) -> member(X, T);
member(X, []) -> false.

첫번째 절에서 만약 X가 리스트의 첫번째 원소와 일치한다면 true를 리턴한다. 그렇지 않다면 두번째 절이 수행이 되는데, 즉 두번째 원소와 일치하는지를 비교하게 된다. 이렇게 해서 재귀적으로 member함수를 호출을 하면서 일치하는 원소가 있는지 확인한다. 만약 모든 원소를 검사해서 빈리스트가 넘어오게 되면 3번째 절을 실행하게 되고 false를 리턴한다.

member함수가 어떻게 실행되는지를 묘사해 보았다.

> lists:member(a,[1,2,a,b,c]) 
(0)lists:member(a,[1,2,a,b,c]) 
(1).lists:member(a,[2,a,b,c]) 
(2)..lists:member(a,[a,b,c]) 
(2)..true 
(1).true 
(0)true 
true 
 
> lists:member(a,[1,2,3,4]) 
(0)lists:member(a,[1,2,3,4]) 
(1).lists:member(a,[2,3,4]) 
(2)..lists:member(a,[3,4]) 
(3)...lists:member(a,[4]) 
(4)....lists:member(a,[]) 
(4)....false 
(3)...false 
(2)..false 
(1).false 
(0)false 
false

append

apend(A,B) 두개의 리스트 A와 B를 연결한다.

append([H|L1], L2) -> [H|append(L1, L2)]; 
append([], L) -> L.

두번째 절은 간단히 이해할 수 있다. 첫번째 리스트가 비어있으면, 두번째 리스트를 그대로 리턴하라는 얘기다.

첫번째 절은 처음의 리스트가 비어있지 않다면, 다른 리스트에 추가하라는 의미다.

이러한 과정을 묘사해 보았다.

> lists:append([a,b,c],[d,e,f]). 
(0)lists:append([a,b,c],[d,e,f]) 
(1).lists:append([b,c],[d,e,f]) 
(2)..lists:append([c],[d,e,f]) 
(3)...lists:append([],[d,e,f]) 
(3)...[d,e,f] 
(2)..[c,d,e,f] 
(1).[b,c,d,e,f] 
(0)[a,b,c,d,e,f]

reverse

reverse(L)은 리스트 L의 원소의 순서를 뒤집는다.

reverse(L) -> reverse(L,[]). 
 
reverse([H|T]), Acc) -> 
    reverse(T,[H|Acc]); 
reverse([], Acc) -> 
    Acc.

reverse(L)이 실행되면 reverse/2라는 보조함수를 행성한다. 새로 만들어지는 함수는 2번째인자로 리스트를 가지는데, 여기에 결과가 저장된다.

reverse(L, Acc)가 호출되었을 때, L이 비어있는 리스트가 아니라면, L의 첫번째 원소삭제한다음 Acc의 처음으로 보낸다. 즉 reverse([x,y,z], Acc)의 결과는 reverse([y,z], x|Acc)가 된다.

reverse 는 다음과 같이 묘사할 수 있다.

> lists:reverse([a,b,c,d]). 
(0)lists:reverse([a,b,c,d]) 
(1).lists:reverse([a,b,c,d], []) 
(2)..lists:reverse([b,c,d], [a]) 
(3)...lists:reverse([c,d], [b,a]) 
(4)....lists:reverse([d], [c,b,a]) 
(5).....lists:reverse([], [d,c,b,a]) 
(5).....[d,c,b,a] 
(4)....[d,c,b,a] 
(3)...[d,c,b,a] 
(2)..[d,c,b,a] 
(1).[d,c,b,a] 
(0)[d,c,b,a] 
[d,c,b,a]

delete_all

delete_all(X, L) 는 리스트 L에서 X원소를 삭제한다.

delete_all(X, [X|T]) -> 
    delete_all(X, T); 
delete_all(X, [Y|T]) -> 
    [Y | delete_all(X, T)]; 
delete_all(_, []) -> 
    [].

예제

여기에서는 좀더 복잡한 예제들을 이용해서 리스트의 사용방법에 대해서 알아보도록 하겠다.

sort

다음은 리스트를 정렬하는 프로그램이다. 정렬을 위해서 quicksort 알고리즘을 사용했다. 퀵소트는 분할정복알고리즘을 사용한다. 퀵소트에 대한 자세한 내용은 QuickSort 알고리즘 소개문서를 참고하기 바란다.
QuickSort 알고리즘 소개는 C버전의 sort 함수가 있는데, 아래의 erlang 버전의 함수들과 비교해 보면 함수형언어의 매력을 느낄 수 있을 것이다.

-module(sort). 
-export([sort/1]). 
-export([split/2]). 
 
sort([]) -> []; 
sort([Pivot|Rest]) -> 
    {Smaller, Bigger} = split(Pivot, Rest), 
    lists:append(sort(Smaller), [Pivot|sort(Bigger)]). 
 
split(Pivot, L) -> 
    split(Pivot, L, [], []). 
 
split(Pivot, [], Smaller, Bigger) -> 
    {Smaller, Bigger}; 
split(Pivot, [H|T], Smaller, Bigger) when H < Pivot -> 
    split(Pivot, T, [H|Smaller], Bigger); 
split(Pivot, [H|T], Smaller, Bigger) when H >= Pivot -> 
    split(Pivot, T, Smaller, [H|Bigger]).

이 함수는 리스트의 첫번째 원소를 pivot로 선택하고 있다. 원본 리스트는 Smaller와 Bigger 두개의 리스트로 나뉜며, pivot보다 작은 원소는 Smaller에 pivot보다 큰 원소는 Bigger에 위치한다. 이러한 과정을 다시 Smaller과 Bigger에 대해서 반복하게 되고, 최종적으로 정렬된 리스트를 리턴하게 된다.

split(Pivot, L)함수가 Pivot를 중심으로 Smaller과 Bigger로 리스트 L의 원소를 나누는 일을 한다. 아래는 split가 어떻게 작동하는지를 보여주고 있다.

> sort:split(7,[2,1,4,23,6,8,43,9,3]). 
{[3,6,4,1,2],[9,43,8,23]}

만약 당신이 sort([7,2,1,4,23,6,8,43,9,3])을 호출 했다면, pivot으로 7이 선택되고, split/2가 pivot 7과 함께 호출이 된다. 이 결과 pivot 7을 기준으로 7보다 더작은 원소인[3,6,4,1,2]로 이루어진 리스트와 7보다크거나 같은 원소인 [9,43,8,23]로 이루어진 리스트가 만들어진다.

이제 sort([3,6,4,1,2]) => [1,2,3,4,6] 와 sort([9,43,8,23]) => [8,9,23,43]이 이루어졌다고 가정하면, 최종적으로 append를 호출해서 완전히 정렬된 결과를 만들어내게 된다.

> append([1,2,3,4,6], [7|[8,9,23,43]]). 
[1,2,3,4,6,7,8,9,23,43]

머리를 약간 더 굴려주면 append가 존재하지 않는, 좀더 간단한 함수를 만들수도 있다.

-module(qsort). 
-export([qsort/1]). 
 
qsort(X)-> 
    qsort(X,[]). 
 
qsort([Pivot|Rest], Tail)-> 
    {Smaller,Bigger} = split(Pivot,Rest), 
    qsort(Smaller,[Pivot|qsort(Bigger,Tail)]); 
qsort([],Tail)-> 
    Tail.

뇌자극 QA 뇌자극 에러 및 수정목록 총 페이지 수 : 3224 전체 함수/용어사전 구글검색방법 구글 맞춤검색	Facebook Joinc 그룹 Joinc QA 사이트 현재위치 : 미니사이트>Erlang>Getting_Started_With_Erlang>Chapter_03 Tweet joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다. List 소개 erlang는 list를 지원한다. list 는 [와]로 표현되며, 각 원소는 ,를 이용해서 구분이 된다. 예를 들자면 [E1, E2, E3,....]식으로 list를 표현할 수 있다. 이 리스트의 원소는 E1, E2, E3, ... 가 된다. rt(3)표준 퀵정렬함수 퀵소트와 Priority큐와의 성능비교 기호로 표시하자면 [E1,E2,E3,...,En\|Variable], where n >= 1 이 된다. List를 다루기 위한 내장함수들 erlang는 리스트와 다른 데이터 타입간의 변환을 위한 다양한 내장함수를 가지고 있다. atom_to_list(A) atom A를 ASCII 문자코드 리스트로 변환한다. 예) atom_to_list(hello) => [104,101,108,108,111] float_to_list(F) float point 숫자 F를 ASCII 문자코드의 리스트로 변환한다. 예) float_to_list(1.5) => [49,46,53,48,48,...,48]. integer_to_list(I) integer형 숫자 I를 ASCII 문자코드로 변환한다. 예) integer_to_list(1245) => [49, 50, 52, 53]. list_to_atom(L) ASCII 문자코드 리스트 L을 atom으로 변환한다. 예) list_to_atom([119,111,114,108,100]) => world. list_to_float(L) ASCII 문자코드 리스트 L을 floating point 숫자로 변환한다. 예) list_to_float([51,46,49,52,49,53,57])] => 3.14159 list_to_integer(L) ASCII 문자코드 리스트 L을 integer 형으로 변환한다. 예) list_to_integer([49,50,51,52]) => 1234. hd(L) 리스트 L의 첫번째 원소를 되돌려준다. 예) hd([a,b,c,d]) => a. tl(L) 리스트 L에서 처음원소를 제외한 나머지 - tail -을 리턴한다. 예) tl([a,b,c,d]) length(L) 리스트 L의 원소 갯수를 리턴한다. 예) length([a,b,c,d]) => 4. 일반적인 리스트 함수 여기에서는 간단한 리스트 함수들에 대해서 알아볼 것이다. 이하 설명하는 모든 리스트함수들은 lists module에 포함된다. 재귀호출을 이용해서 문제가 이해하기 쉽게 기술되었다는 점이 인상깊다. ==== member === member(X, L) 만약 X가 리스트 L의 원소라면 참을 그렇지 않다면 거짓을 리턴한다. 이 함수는 다음과 같이 정의되어 있다. member(X, X\|_) -> true; member(X, _\|T) -> member(X, T); member(X, []) -> false. 첫번째 절에서 만약 X가 리스트의 첫번째 원소와 일치한다면 true를 리턴한다. 그렇지 않다면 두번째 절이 수행이 되는데, 즉 두번째 원소와 일치하는지를 비교하게 된다. 이렇게 해서 재귀적으로 member함수를 호출을 하면서 일치하는 원소가 있는지 확인한다. 만약 모든 원소를 검사해서 빈리스트가 넘어오게 되면 3번째 절을 실행하게 되고 false를 리턴한다. member함수가 어떻게 실행되는지를 묘사해 보았다. > lists:member(a,[1,2,a,b,c]) (0)lists:member(a,[1,2,a,b,c]) (1).lists:member(a,[2,a,b,c]) (2)..lists:member(a,[a,b,c]) (2)..true (1).true (0)true true > lists:member(a,[1,2,3,4]) (0)lists:member(a,[1,2,3,4]) (1).lists:member(a,[2,3,4]) (2)..lists:member(a,[3,4]) (3)...lists:member(a,[4]) (4)....lists:member(a,[]) (4)....false (3)...false (2)..false (1).false (0)false false append apend(A,B) 두개의 리스트 A와 B를 연결한다. append([H\|L1], L2) -> [H\|append(L1, L2)]; append([], L) -> L. 두번째 절은 간단히 이해할 수 있다. 첫번째 리스트가 비어있으면, 두번째 리스트를 그대로 리턴하라는 얘기다. 첫번째 절은 처음의 리스트가 비어있지 않다면, 다른 리스트에 추가하라는 의미다. 이러한 과정을 묘사해 보았다. > lists:append([a,b,c],[d,e,f]). (0)lists:append([a,b,c],[d,e,f]) (1).lists:append([b,c],[d,e,f]) (2)..lists:append([c],[d,e,f]) (3)...lists:append([],[d,e,f]) (3)...[d,e,f] (2)..[c,d,e,f] (1).[b,c,d,e,f] (0)[a,b,c,d,e,f] reverse reverse(L)은 리스트 L의 원소의 순서를 뒤집는다. reverse(L) -> reverse(L,[]). reverse([H\|T]), Acc) -> reverse(T,[H\|Acc]); reverse([], Acc) -> Acc. reverse(L)이 실행되면 reverse/2라는 보조함수를 행성한다. 새로 만들어지는 함수는 2번째인자로 리스트를 가지는데, 여기에 결과가 저장된다. reverse(L, Acc)가 호출되었을 때, L이 비어있는 리스트가 아니라면, L의 첫번째 원소삭제한다음 Acc의 처음으로 보낸다. 즉 reverse([x,y,z], Acc)의 결과는 reverse([y,z], x\|Acc)가 된다. reverse 는 다음과 같이 묘사할 수 있다. > lists:reverse([a,b,c,d]). (0)lists:reverse([a,b,c,d]) (1).lists:reverse([a,b,c,d], []) (2)..lists:reverse([b,c,d], [a]) (3)...lists:reverse([c,d], [b,a]) (4)....lists:reverse([d], [c,b,a]) (5).....lists:reverse([], [d,c,b,a]) (5).....[d,c,b,a] (4)....[d,c,b,a] (3)...[d,c,b,a] (2)..[d,c,b,a] (1).[d,c,b,a] (0)[d,c,b,a] [d,c,b,a] delete_all delete_all(X, L) 는 리스트 L에서 X원소를 삭제한다. delete_all(X, [X\|T]) -> delete_all(X, T); delete_all(X, [Y\|T]) -> [Y \| delete_all(X, T)]; delete_all(_, []) -> []. 예제 여기에서는 좀더 복잡한 예제들을 이용해서 리스트의 사용방법에 대해서 알아보도록 하겠다. sort 다음은 리스트를 정렬하는 프로그램이다. 정렬을 위해서 quicksort 알고리즘을 사용했다. 퀵소트는 분할정복알고리즘을 사용한다. 퀵소트에 대한 자세한 내용은 QuickSort 알고리즘 소개문서를 참고하기 바란다. QuickSort 알고리즘 소개는 C버전의 sort 함수가 있는데, 아래의 erlang 버전의 함수들과 비교해 보면 함수형언어의 매력을 느낄 수 있을 것이다. -module(sort). -export([sort/1]). -export([split/2]). sort([]) -> []; sort([Pivot\|Rest]) -> {Smaller, Bigger} = split(Pivot, Rest), lists:append(sort(Smaller), [Pivot\|sort(Bigger)]). split(Pivot, L) -> split(Pivot, L, [], []). split(Pivot, [], Smaller, Bigger) -> {Smaller, Bigger}; split(Pivot, [H\|T], Smaller, Bigger) when H < Pivot -> split(Pivot, T, [H\|Smaller], Bigger); split(Pivot, [H\|T], Smaller, Bigger) when H >= Pivot -> split(Pivot, T, Smaller, [H\|Bigger]). 이 함수는 리스트의 첫번째 원소를 pivot로 선택하고 있다. 원본 리스트는 Smaller와 Bigger 두개의 리스트로 나뉜며, pivot보다 작은 원소는 Smaller에 pivot보다 큰 원소는 Bigger에 위치한다. 이러한 과정을 다시 Smaller과 Bigger에 대해서 반복하게 되고, 최종적으로 정렬된 리스트를 리턴하게 된다. split(Pivot, L)함수가 Pivot를 중심으로 Smaller과 Bigger로 리스트 L의 원소를 나누는 일을 한다. 아래는 split가 어떻게 작동하는지를 보여주고 있다. > sort:split(7,[2,1,4,23,6,8,43,9,3]). {[3,6,4,1,2],[9,43,8,23]} 만약 당신이 sort([7,2,1,4,23,6,8,43,9,3])을 호출 했다면, pivot으로 7이 선택되고, split/2가 pivot 7과 함께 호출이 된다. 이 결과 pivot 7을 기준으로 7보다 더작은 원소인[3,6,4,1,2]로 이루어진 리스트와 7보다크거나 같은 원소인 [9,43,8,23]로 이루어진 리스트가 만들어진다. 이제 sort([3,6,4,1,2]) => [1,2,3,4,6] 와 sort([9,43,8,23]) => [8,9,23,43]이 이루어졌다고 가정하면, 최종적으로 append를 호출해서 완전히 정렬된 결과를 만들어내게 된다. > append([1,2,3,4,6], [7\|[8,9,23,43]]). [1,2,3,4,6,7,8,9,23,43] 머리를 약간 더 굴려주면 append가 존재하지 않는, 좀더 간단한 함수를 만들수도 있다. -module(qsort). -export([qsort/1]). qsort(X)-> qsort(X,[]). qsort([Pivot\|Rest], Tail)-> {Smaller,Bigger} = split(Pivot,Rest), qsort(Smaller,[Pivot\|qsort(Bigger,Tail)]); qsort([],Tail)-> Tail.