EECS101 전자계산입문여섯번째숙제 -리스트- (100 점 + 도전문제점수 50점 ) 오진오 (kurin@postech) 제출마감 : 5월 1일 11:59pm 이번숙제에서는수업시간에배웠던리스트에대한기본개념을프로그래밍을통해익혀보고, 리스트를통해가능한문제해결방법에대해서알아봅니다. 부정행위에관한규정은 POSTECH 전자컴퓨터공학부학부위원회의 POSTECH 전자컴퓨터공학부부정행위정의 를따릅니다. (http://http://www.postech.ac.kr/~gla/cs101/disciplinary/index.html) 숙제가어렵거나이해가안가는부분이있다면교수님과조교님들을활용하세요. 최대한친절히도와드립니다. 단, 정답은가르쳐드리지않습니다. 숙제에관한질문은과목게시판을이용하시기바랍니다. 제 1 절 골격파일과검사파일 웹브라우저에서 http://www.postech.ac.kr/~gla/cs101/hw/hw6.ml과 http://www.postech.ac.kr/~gla/cs101/hw/hw6-check.ml 또는 FTP client에서 <Hemos home folder> /cs101 handin/hw6/hw6.ml과 <Hemos home folder> /cs101 handin/hw6/hw6-check.ml을내려받는다. 제 2 절 숙제작성법 골격파일 hw6.ml을내려받고 Emacs,gvim, 메모장과같은편집프로그램을이용하여골격파일을열면다음과같다. exception NotImplemented;; let rec reverse l = raise NotImplemented;; let rec map f l = raise NotImplemented;; let rec altersum l = raise NotImplemented;; let rec collatz_seq n = raise NotImplemented;; let rec remove_duplicate l = raise NotImplemented;; let rec intersection xl yl = raise NotImplemented;; 1
let rec poly l = raise NotImplemented;; let rec powerset l = raise NotImplemented;; (* sum type for DNA *) type dna = A T C G;; let rec subsequence xl yl = raise NotImplemented;; let rec prime_seq n = raise NotImplemented;; (* Challenge *) type a inf_list = Inf_list of (unit -> ( a * a inf_list));; let inf_hd x = match x with Inf_list y -> let (a,_) = y () in a;; let inf_tl x = match x with Inf_list y -> let (_,b) = y () in b;; let rec inf_nth l n = if n = 1 then inf_hd l else inf_nth (inf_tl l) (n - 1);; let inf_prime_seq () = raise NotImplemented; 문제에서설명하는함수를작성하기위해, raise NotImplemented를삭제하고문제가요구하는올바른연산식을채워넣는다. 예를들면, 1번문제의경우함수 reverse을작성하기위해함수의몸통연산식인 raise NotImplemented를지우고, reverse의올바른몸통연산식을작성한다. 연산식 raise NotImplemented는함수의몸통연산식이작성되지않았다는예외상황을표시하며, 의미자체는본숙제의해결에중요하지않다. 만약올바르게함수를정의할수없다고판단하는경우해당함수의몸통연산식인 raise NotImplemented을삭제하지않고그대로두어야한다. 제 3 절 타입확인및제출 문제에대한답을다작성한이후, 작성한숙제파일 hw6.ml의각함수가문제에서제시한타입을만족하는지확인하기위해다음과같이검사파일을이용한다. 골격파일을편집하여숙제를작성하였으므로이후골격파일과숙제파일은동일한파일인 hw6.ml을가리킨다. 숙제파일 hw6.ml과검사파일 hw6-check.ml을동일한폴더에위치시킨다. 명령프롬프트 ([ 시작 ] [ 프로그램 ] [ 보조프로그램 ] [ 명령프롬프트 ]) 를실행한후, cd명령어를이용해숙제파일과검사파일이위치한폴더로이동한다. 아래와같이 ocamlc 명령어를이용해숙제파일과검사파일을함께컴파일한다. ocamlc -o hw6-check.exe hw6.ml hw6-check.ml 컴파일한결과명령프롬프트에아무런메시지가나타나지않으면작성한함수들이모두올바른타입을가지고있음을의미한다. 숙제작성을마친후 FTP client를이용하여숙제파일인 hw6.ml을자신의숙제제출디렉토리인 <Hemos home folder> /cs101 handin/hw6/<hemos id> 에저장한다. 2
파일이름은반드시 hw6.ml 이어야한다. hw6.ml 이아닌다른이름의파일을제출하면 0 점처리 된다. 컴파일되지않는숙제는 0 점처리된다. 제 4 절 문제 1, 2번문제에서는 Ocaml의 List 라이브러리의함수를사용하지않는다. 3 10번문제에서는 List 라이브러리를자유로이사용할수있다. List.fold left 또는 List.fold right를사용한다면골격파일에서주어진 rec 키워드를무시해도된다. Question 1. [5점] 리스트의순서를거꾸로하는함수 reverse를작성하라. ( 타입 ) a list -> a list ( 설명 ) reverse l은원소의순서가거꾸로되어있는새로운리스트를반환한다. reverse [a 1 ; a 2 ;...; a n 1 ; a n ] 은 [a n ; a n 1 ;... ; a 2 ; a 1 ] 를반환한다. 예를들면 [1; 2; 3; 4; 5] 라는리스트를입력으로받으면 [5; 4; 3; 2; 1] 이라는리스트를반환한다. ( 주의 ) Ocaml에서제공하는 List 라이브러리는사용해서는안된다. # reverse;; - : a list -> a list = <fun> # reverse [1; 2; 3; 4; 5; 6];; - : int list = [6; 5; 4; 3; 2; 1] # reverse ["Pink Floyd"; "bluedawn"; "more than paradise"];; - : string list = ["more than paradise"; "bluedawn"; "Pink Floyd"] # reverse [1.; 2.; 4.; 5.3; 6.5];; - : float list = [6.5; 5.3; 4.; 2.; 1.] # reverse [];; - : a list = [] Question 2. [5점] 함수를리스트각각의원소에적용시키는함수 map을작성하라. ( 타입 ) ( a -> b) -> a list -> b list ( 설명 ) map f l은 l의각원소에함수 f를적용한결과를반환한다. 즉 map f [a 1 ; a 2 ;... ; a n 1 ; a n ] 은 [f a 1 ; f a 2 ;... ; f a n 1 ; f a n ] 을반환한다. ( 주의 ) Ocaml에서제공하는 List 라이브러리는사용해서는안된다. # map;; - : ( a -> b) -> a list -> b list = <fun> # map (fun x -> x+2) [1; 2; 3; 4; 5; 6];; - : int list = [3; 4; 5; 6; 7; 8] # map (fun x -> not x) [true; false; true; true];; 3
- : bool list = [false; true; false; false] # map (fun x -> "my favorite band is "^x) ["Mot"; "bluedawn"];; - : string list = ["my favorite band is Mot"; "my favorite band is bluedawn"] Question 3. [10 점 ] altersum 을작성하라. ( 타입 ) int list -> int 리스트 [a 1 ; a 2 ;...; a n ] 를입력으로받아 n k=1 ( 1)k 1 a k 을구하는함수 ( 설명 ) altersum l 은리스트 l 의원소의부호를바꿔가며합을구하는함수이다. altersum [a 1 ; a 2 ;...; a n ] 은 n k=1 ( 1)k 1 a k 을계산한다. 예를들어 altersum [10; 11; 12; 13] 은결과값으로 10-11+12-13 을계 산하여 -2 를반환한다. # altersum;; - : int list -> int = <fun> # altersum [1; 2; 3; 4; 5; 6; 7; 8];; - : int = -4 # altersum [-10; 10; -10; 10];; - : int = -40 # altersum [];; - : int = 0 Question 4. [10 점 ] collatz 수열을리스트로반환하는함수를작성하라. ( 타입 ) int -> int list ( 설명 ) k 를초항으로가지는 collatz 수열 a n 은다음과같이정의된다. a 0 = k a n 1 이 1 이아닌홀수인경우 a n = 3a n 1 + 1 a n 1 이짝수인경우 a n = 1 2 a n 1 a n 1 이 1인경우수열은종결되며, a n 은정의되지않는다 collatz seq k는정수 k를초항으로하는 collatz수열을리스트형태로반환한다. 예를들어, 15를초항으로하는 collatz수열은 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 이므로 collatz seq 15는 [15; 46; 23; 70; 35; 106; 53; 160; 80; 40; 20; 10; 5; 16; 8; 4; 2; 1] 을반환한다. 결과리스트는초항부터시작하여순서대로나열되어있어야한다. 즉 [a 0 ; a 1 ;...] 순이되어야한다. ( 가정 ) k > 0 # collatz_seq;; - : int -> int list = <fun> # collatz_seq 10;; - : int list = [10; 5; 16; 8; 4; 2; 1] # collatz_seq 15;; - : int list = [15; 46; 23; 70; 35; 106; 53; 160; 80; 40; 20; 10; 5; 16; 8; 4; 2; 1] 4
Question 5. [10점] 리스트내에중복되는원소를제거해주는함수 remove duplicate를작성하라. ( 타입 ) a list -> a list ( 설명 ) remove duplicate l은리스트 l에서중복되는원소를하나만남기고제거한리스트를반환한다. 예를들어 [1; 1; 1; 1] 을입력으로받으면 [1] 을반환한다. 결과리스트에서원소의순서는중요치않다. 예를더들면 [1; 2; 3; 2] 를입력으로받으면 [1; 2; 3], [1; 3; 2], [2; 1; 3], [2; 3; 1], [3; 1; 2], [3; 2; 1] 중하나를반환해야한다. # remove_duplicate;; - : a list -> a list = <fun> # remove_duplicate [1; 2; 3; 4; 3; 2; 3; 2];; - : int list = [1; 2; 3; 4] # remove_duplicate ["a"; "b"; "hi"; "b"; "goldbar"; "hi"];; - : string list = ["a"; "b"; "hi"; "goldbar"] # remove_duplicate [true; false; true; false; false];; - : bool list = [true; false] # remove_duplicate [(1, 2); (2, 3); (1, 3); (2, 3)];; - : (int * int) list = [(1, 2); (2, 3); (1, 3)] # remove_duplicate [];; - : a list = [] Question 6. [10점] 리스트를집합으로생각하여교집합을구하는함수 intersection를작성하라. ( 타입 ) a list -> a list -> a list ( 설명 ) 리스트는집합으로해석할수있다. intersection xl yl은리스트 xl, yl을각각집합으로간주하고그교집합을구하는함수이다. 최종으로반환하는리스트에서원소의순서는중요하지않다. 예를들면 intersection [1; 2; 4] [2; 3; 4] 는두개의집합에공통적으로들어가는원소가 2, 4이므로반환값으로 [2; 4] 이나 [4; 2] 를반환한다. ( 가정 ) 입력받은리스트에는중복되는원소가존재하지않는다. 예를들면 [1; 2; 3; 1] 처럼원소가중복되는경우는입력값으로들어오지않는다고가정한다. # intersection;; - : a list -> a list -> a list = <fun> # intersection [1; 3; 5; 6] [2; 3; 4; 7];; - : int list = [3] # intersection [true; false] [false];; - : bool list = [false] # intersection ["ACT"; "TGC"; "TCA"; "GAC"; "AAC"] ["AAC"; "CGT"; "TCA"; "GAA"];; - : string list = ["TCA"; "AAC"] # intersection [] [];; - : a list = [] Question 7. [10점] 리스트로부터다항함수를만드는함수 poly를작성하라. ( 타입 ) int list -> (int -> int) 5
( 설명 ) poly l은리스트 l의원소를다항함수의계수로파악하고다항함수를생성해반환하는함수이다. 다항함수는각항의계수를원소로가지는리스트로표현할수있다. 즉다항함수 f(x) = a n x n + a n 1 x n 1 +... + a 1 x + a 0 는리스트 [a n ; a n 1 ;...; a 1 ; a 0 ] 로표현할수있다. 반대로 [a n ; a n 1 ;...; a 1 ; a 0 ] 라는계수의리스트를알면다항함수 f(x) = a n x n +a n 1 x n 1 +...+a 1 x+a 0 를생성할수있다. poly [a n ; a n 1 ;...; a 1 ; a 0 ] 는 f(x) = a n x n + a n 1 x n 1 +... + a 1 x + a 0 에해당하는함수를생성하여반환한다. 입력값이 [] 인경우 f(x) = 0에해당하는상수함수를반환한다. # poly;; - : int list -> int -> int = <fun> # poly [3; 2; 1] 0;; - : int = 1 # poly [3; 2; 1] 1;; - : int = 6 # poly [3; 2; 1] 2;; - : int = 17 # poly [-5; 3; 2; 1] 5;; - : int = -539 # poly [] 1;; - : int = 0 # poly [] 2;; - : int = 0 Question 8. [10점] 리스트를집합으로생각하였을때, 리스트를입력받아멱집합을반환하는함수 powerset을작성하라. ( 타입 ) a list -> a list list ( 설명 ) 리스트는집합으로해석할수있다. powerset l은 l의멱집합을구하여리스트의리스트타입 (( a list) list) 으로멱집합을반환한다. 부분집합간순서, 부분집합내원소의순서는중요하지않다. 예를들면 powerset [1] 의경우반환값이 [[]; [1]] 와 [[1]; []] 중무엇이되어도좋다. 하지만반환되는리스트역시집합이므로중복되는원소가있어서는안된다. powerset [1] 의경우 [[]; [1]; []] 는잘못된반환값이다. ( 가정 ) 입력받은리스트에는중복되는원소가존재하지않는다. 예를들면 [1; 2; 3; 1] 처럼원소가중복되는경우는입력값으로들어오지않는다고가정한다. # powerset;; - : a list -> a list list = <fun> # powerset [1;2;3];; - : int list list = [[1; 2; 3]; [1; 2]; [1; 3]; [1]; [2; 3]; [2]; [3]; []] # powerset ["a";"b";"c";"d"];; - : string list list = [["a"; "b"; "c"; "d"]; ["a"; "b"; "c"]; ["a"; "b"; "d"]; ["a"; "b"]; ["a"; "c"; "d"]; ["a"; "c"]; ["a"; "d"]; ["a"]; ["b"; "c"; "d"]; ["b"; "c"]; 6
["b"; "d"]; ["b"]; ["c"; "d"]; ["c"]; ["d"]; []] # powerset [];; - : a list list = [[]] Question 9. [10점] 생명공학에서 DNA분석은중요한문제이다. DNA는 A, T, C, G( 아데닌, 티민, 시토신, 구아닌 ) 4가지염기의조합으로이루어져있고, 4가지염기의조합에따라생명체의유전형질이결정된다. 그렇기때문에 DNA 염기서열에특정한염기서열이포함되어있는지를확인하는작업은 DNA연구에필수적이다. subsequence xl yl은 DNA 염기서열 xl에염기서열 yl이포함되어있는지검사한다. 4가지염기를표현하기위하여타입 dna가다음과같이정의되었다. type dna = A T C G;; ( 타입 ) dna list -> dna list -> bool ( 설명 ) 리스트 L 1 과 L 2 에대해서 L 1 = l 1 @ L 2 @ l 2 를만족하는리스트 l 1, l 2 가존재할때 L 2 는 L 1 에포함된다고말한다. 예를들면 [1; 2; 3; 4; 5; 6] 와 [3; 4; 5] 에대해 [1; 2; 3; 4; 5; 6] = [1; 2] @ [3; 4; 5] @ [6] 이므로 [3; 4; 5] 은 [1; 2; 3; 4; 5; 6] 에포함된다. 또다른예로 [1; 2; 3; 4; 5; 6] 와 [4; 5; 6] 는 [1; 2; 3; 4; 5; 6] = [1; 2; 3] @ [4; 5; 6] @ [] 을만족하므로 [4; 5; 6] 은 [1; 2; 3; 4; 5; 6] 에포함된다. 하지만 [4; 6] 는 [1; 2; 3; 4; 5; 6] = l 1 @ [4; 6] @ l 2 을만족하는 l 1, l 2 가존재하지않으므로 [1; 2; 3; 4; 5; 6] 에포함되지않는다. subsequence xl yl은염기서열 yl이 DNA 염기서열 xl에포함되어있는지검사하여포함되어있으면 true, 포함되어있지않으면 false를반환하는함수이다. # subsequence;; - : dna list -> dna list -> bool = <fun> # let seq = [A; C; T; G; C; T; G; T; G; C; G; C; T; G];; val seq : dna list = [A; C; T; G; C; T; G; T; G; C; G; C; T; G] # subsequence seq [T; C; G];; - : bool = false # subsequence seq [G; C; T];; - : bool = true # subsequence [G; C; T] [];; - : bool = true # subsequence [] [];; - : bool = true Question 10. [20점] 에라토스테네스의체를이용하여소수의리스트를계산하는함수 prime seq를작성하라.( 이문제의배점은 20점입니다 ) ( 타입 ) int -> int list ( 설명 ) prime seq n은에라토스테네스의체를이용하여입력받은정수 n이하의모든소수를리스트의형태로반환한다. 에라토스테네스의체는소수를구하기위한방법으로 [2; 3; 4;...; n] 처럼 2부터 n까지의모든자연수들의리스트가있을때, 가장먼저있는원소로나누어떨어지는원소를지워나가는방식으로소수를찾아낸다. 예를들면 [2; 3; 4; 5; 6; 7; 8; 9; 10] 이라는리스트를살펴보면가장앞에있는원소인 2로 [3; 4; 5; 6; 7; 8; 9; 10] 의원소를나누어, 나누어떨어지는 4, 6, 8, 10을삭제하고나누어떨어지지않는 3, 5, 7, 9는남긴다. 같은방법을남은리스트 [3; 5; 7; 9] 에대해서 7
도적용한다. 이러한과정을반복해나가면마지막에리스트에남는숫자들은모두소수이다. 에라토스테네스의체방법은 2부터시작하는리스트를대상으로한다. ( 가정 ) n 2 # prime_seq;; - : int -> int list = <fun> # prime_seq 2;; - : int list = [2] # prime_seq 10;; - : int list = [2; 3; 5; 7] # prime_seq 100;; - : int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97] 제 5 절도전문제 (50 점 ) [ 알림 ] 도전문제에대한질문은일체받지않습니다. OCaml은함수가정의될때몸통연산식을바로계산하지않고, 함수의적용이일어날때몸통연산식을계산한다. 함수몸통연산식의계산이지연되는예로다음함수를생각해보자. # let f () = 2 + 3;; val f : unit -> int = <fun> 함수 f는 unit 타입의값 () 을인자로받으면 2 + 3의계산결과를반환한다. ( 따라서 f의인자는계산에이용되지않고무시된다.) 위의정의에서몸통연산식 2 + 3은바로계산되어 5로대체될수도있지만, OCaml은 f가 () 에적용이될때비로소 2 + 3을계산한다. 즉함수 f는정의시점에서몸통연산식 2 + 3을계산하지않고그대로지니고있다가함수적용 f () 이계산될때몸통연산식 2 + 3을계산하는것이다. 위와같은 Ocaml의특징을이용하면무한개의원소로이루어진리스트를표현할수있다. 무한개의원소로이루어진리스트를표현하기위해서다음의타입 a inf list를이용한다. type a inf list = Inf list of (unit -> ( a * a inf list));; 생성자 Inf list의인자는 unit -> ( a * a inf list) 타입의함수로서리스트의첫번째원소 ( a 타입 ) 와나머지리스트 ( a inf list 타입 ) 로이루어진튜플을반환한다. Inf list의인자로이용하는함수는호출되기전까지몸통연산식을계산하지않음에주목하자. a inf list 타입의이용을돕기위해골격파일은아래의세함수를제공한다. let inf_hd x = match x with Inf_list y -> let (a,_) = y () in a;; let inf_tl x = match x with Inf_list y -> let (_,b) = y () in b;; let rec inf_nth l n = if n = 1 then inf_hd l else inf_nth (inf_tl l) (n - 1);; 8
inf hd는 a inf list -> a 타입을 가지고, inf hd l은 무한개의 원소로 이루어진 리스트 l의 첫 번 째 원소를 반환한다. inf tl은 a inf list -> a inf list 타입을 가지고, inf tl l은 무한개의 원소로 이루어진 리스 트 l의 첫 번째 원소를 제외한 나머지 리스트를 반환한다. inf nth는 a inf list -> int -> a 타입을 가지고, inf nth l n은 무한개의 원소로 이루어진 리 스트 l의 n번째 원소를 반환한다. Question [50점] 에라토스테네스의 체를 이용하여 소수의 리스트를 반환하는 함수 inf prime seq를 작 성하라. (타입) unit -> int inf list (설명) inf prime seq ()는 에라토스테네스의 체를 이용하여 2부터 시작하는 모든 소수를 크기 순서 대로 나열하는 int inf list타입의 리스트를 반환한다. (힌트) OCaml이 제공하는 List 라이브러리는 a inf list타입에 적용이 불가능하다. 그러나 List라 이브러리에 포함되어 있는 함수들을 a inf list 타입을 위한 함수로 바꾸어 보면 문제를 해결하는 데에 힌트를 얻을 수 있다 된다. 특히 inf hd, inf tl, inf nth 함수의 작동 원리를 이해하는 것이 a inf list 타입을 사용하는데 큰 도움이 된다. (실행 예) # inf_prime_seq;; - : unit -> int inf_list = <fun> # let prime = inf_prime_seq ();; val prime : int inf_list = inf_list <fun> # inf_hd prime;; - : int = 2 # inf_nth prime 10;; - : int = 29 # inf_nth (inf_prime_seq ()) 1000;; - : int = 7919 제6절 질문시 유의 사항 아래와 같은 질문은 삼가해주기 바랍니다. (코드의 내용을 보여주면서) "제 코드가 요구사항대로 동작하지 않는데 어느 부분이 잘못된 건가요?" 자신이 작성한 코드를 보여주면서 틀린부분을 찾아달라는 질문에 대하여 대답해 줄 수 없습니다. "제 코드의 함수 f는 타입이 int->int->int 인데요, 핸드아웃에는 int->(int->int) 라고 되어 있어요, 괜찮은가요?" 핸드아웃의 2절 타입 확인부분을 읽고 지시대로 따라하면 됩니다. "핸드아웃의 실행 예는 다 만족하는데요 그러면 제 코드가 올바르게 작성된 것인가요?" 어떤 입력 값을 넣었을때 자기가 짠 코드가 올바른지 판단하는 몫은 학생여러분 자신들에게 있습 9
니다. 단, 강의게시판에 자신이 테스트한 케이스를 올려두고 다른 학생들의 것과 비교해보는 것은 상 관없습니다. "제가 짠 코드를 복사해서 Ocaml 해석기에 붙여넣어서 테스트하면 잘 되는데 컴파일 하면 에러가 나요 ㅠㅠ." 편집기에서 복사해서 Ocaml 해석기에 붙여넣지 말고, Ocaml 해석기의 [File] [Open] 을 이용 하거나 컴파일러를 이용합니다. 제7절 숙제에 대한 의견 숙제에 대한 학생들의 모든 의견을 환영합니다. 숙제에 대한 의견이 있으면 http://pl.postech.ac.kr/~gla/feedback/ 페이지를 방문하여 의견을 익명으로 남겨주시길 바랍니다. 여러분들의 의견은 향후 숙제 설계와 강의 준비 에 중요한 자료로 이용됩니다. 의견을 남기는 사람에 대한 어떤 정보도 저장되지 않습니다. 10