Homework 1 SNU 4190.310, Fall 2012 Kwangkeun Yi Due: 9/14, 24:00 Exercise 1 리스트합 큰순서대로 (descending order) 나열된정수리스트두개를받아서하나의 순서리스트로만드는함수 merge: int list * int list -> int list 를정의하세요. 리스트에는같은정수가반복해서들어있지않습니다. Exercise 2 씨그마 우리가중고등수학시간에숱하게썼던다음의 씨그마 를 OCaml 로정의 하세요 : 씨그마의타입은 Σ b n=af(n) sigma : int * int * (int -> int) -> int. 즉, sigma(a,b,f) 로표현하면 Σ b n=af(n) 과같도록. Exercise 3 반복기 다음함수 iter 를정의하세요 : iter(n,f) = f f }{{} n 이때, n = 0 이면아무일을하지않는 (identity) 함수를내놓고, 양수이면그만 큼 f 를반복해서적용하는함수를내놓습니다. 그래서, iter(n, function x -> 2+x) 0 1
은 2 n을내놓게됩니다. Exercise 4 합곱 아래의성질을만족하는함수 sumprod를정의하세요 : sumprod(matrix, n, k) = Σ n i=1π k j=1matrix(i, j). 즉, sumprod의타입은 sumprod : (int * int -> real) * int * int -> real Exercise 5 대진표스트링 일반적으로게임대진표는완전한이진나무구조 (complete binary tree) 입니다. 2014 얼드컵팀들과그대진표를다음과같이정의했습니다 : type team = Korea France Usa Brazil Japan Nigeria Cameroon Poland Portugal Italy Germany Norway Sweden England Argentina type tourna = LEAF of team NODE of tourna * tourna tourna를받아서괄호를이용한 1차원스트링으로변환해주는함수 parenize를작성하세요 : parenize: tourna -> string 예를들어, parenize(node(node(leaf Korea, LEAF Portugal), LEAF Brazil)) = "((Korea Portugal) Brazil)" Exercise 6 참거짓 Propositional Logic 식들 (formula) 을다음과같이정의했습니다 : type formula = TRUE FALSE NOT of formula ANDALSO of formula * formula 2
and ORELSE of formula * formula IMPLY of formula * formula LESS of expr * expr expr = NUM of int PLUS of expr * expr MINUS of expr * expr 주어진 formula를받아서참값을만들어내는함수 eval eval : formula bool 를정의하세요. Exercise 7 자연수 자연수 nat 는다음과같이정의될수있다 : type nat = ZERO SUCC of nat 두자연수를받아서그합 / 곱에해당하는자연수를만드는두함수 natadd : nat * nat -> nat natmul : nat * nat -> nat 를정의하세요. Exercise 8 CheckMetroMap 아래 metro 타입을생각하자 : type metro = STATION of name AREA of name * metro CONNECT of metro * metro and name = string 아래 checkmetro 함수를정의하라 : checkmetro: metro -> bool checkmetro는주어진 metro 가제대로생겼는지를확인해준다. metro가제대로생겼다 는것은 (iff) 메트로역이름 (id in STATION(id)) 들이항상자기이름의지역 (m in AREA(id, m)) 에서만나타나는경우를뜻한다. 예를들어, 제대로생긴 metro 들은 : 3
AREA("a", STATION "a") AREA("a", AREA("a", STATION "a")) AREA("a", AREA("b", CONNECT(STATION "a", STATION "b"))) AREA("a", CONNECT(STATION "a", AREA("b", STATION "a"))) 그렇지못한것들의예들은 : AREA("a", STATION "b") AREA("a", CONNECT(STATION "a", AREA("b", STATION "c"))) AREA("a", AREA("b", CONNECT(STATION "a", STATION "c"))) Exercise 9 짚-짚-나무 임의의나무를여러분바지의 지퍼 로구현할수있답니다. 나무구조타입은아래와같이정의되겠지요 : type item = string type tree = LEAF of item NODE of tree list 아래의 zipper가나무의줄기를타고자유자재로찢어놓기도하고붙여놓기도합니다. type zipper = TOP HAND of tree list * zipper * tree list 현재나무줄기의어느지점에멈춰있는지퍼손잡이 HAND(l,z,r) 에서, l은왼편형제나무들 (elder siblings) 이고 r은오른편형제나무들 (younger siblings) 이다. 나뭇가지에서의현재위치 location는현재위치를뿌리로하는나무자체와지퍼 (zipper) 로표현되는주변나무들로구성된다. type location = LOC of tree * zipper 예를들어, a b + c d 가다음과같은나무구조로표현될것이다. 모든심볼은항상잎새에매달리게된다. NODE [ NODE [LEAF a; LEAF *; LEAF b]; 4
LEAF +; NODE [LEAF c; LEAF *; LEAF d] ] 두번째곱셈표에의위치는다음과같다 : LOC (LEAF *, HAND([LEAF c], HAND([LEAF +; NODE [LEAF a; LEAF *; LEAF b]], TOP, []), [LEAF d])) 자, 주어진위치에서이제자유자재로나무를탈수있습니다. 왼편으로옮겨가는것은다음과같지요 : let goleft loc = match loc with LOC(t, TOP) -> raise (NOMOVE "left of top") LOC(t, HAND(l::left, up, right)) -> LOC(l, HAND(left, up, t::right)) LOC(t, HAND([],up,right)) -> raise NOMOVE "left of first" 다음의나머지함수들을정의하세요 : goright: location -> location goup: location -> location godown: location -> location 5