OCaml íﬂ—ë¡œê·¸ëžŸë°“

Size: px

Start display at page:

Download "OCaml íﬂ—ë¡œê·¸ëžŸë°“"

서오 탄
5 years ago
Views:

1 OCaml 프로그래밍 오학주 고려대학교정보대학컴퓨터학과 January 10 11, Blockchain Camp

2 소개 소속 : 고려대학교정보대학컴퓨터학과 전공 : 프로그래밍언어, 소프트웨어분석, 소프트웨어보안 웹페이지 :

3 강의내용 OCaml 프로그래밍 Part 1: 기초 OCaml 프로그래밍 (5 시간 ) 1. OCaml 기본구성 2. 리스트와재귀함수 3. 고차함수 4. 사용자정의타입 Part 2: 고급 OCaml 프로그래밍 (5 시간 )

4 Why OCaml?

5 프로그래밍언어순위 ( 인기순 )

6 프로그래밍언어랭킹 ( 연봉순 )

7 OCaml 및함수중심언어의활용사례

8 값중심, 함수중심프로그래밍언어 새롭고중요한생각의틀을제공 미래프로그래밍언어의청사진 프로그래밍언어의근본원리에대한이해 간결하고아름다운코드를작성하는즐거움... 소프트웨어전공자라면갖추어야하는기본소양

9 기본기

10 OCaml 의주요특징 값중심, 계산형, 함수중심프로그래밍 (Functional programming) 정적타입시스템 (Static type system) 자동타입추론 (Automatic type inference) 데이터타입, 패턴매칭 (Datatypes and pattern matching) 다형성 (Polymorphism) 모듈 (Modules) 메모리재활용 (Garbage Collection)

11 OCaml 프로그램의기본단위는식 프로그램을구성하는두단위 : 명령문 (statement): 기계상태를변경 x = x + 1 식 (expression): 상태변경없이값을계산 (x + y) * 2 프로그래밍언어를구분하는한가지기준 : 명령문을중심으로프로그램을작성 C, C++, Java, Python, JavaScript, etc often called imperative languages 식을중심으로프로그램을작성 ML, Haskell, Scala, Lisp, etc often called functional languages

12 OCaml 프로그램의기본구조 값정의들의나열 : let x 1 = e 1 let x 2 = e 2. let x n = e n 식 e 1, e 2,..., e n 을순차적으로계산 변수 x i 는식 e i 의값을지칭

13 예제 Hello World: let hello = "Hello" let world = "World" let helloworld = hello ^ " " ^ world let _ = print_endline helloworld 인터프리터를이용한실행 : $ ocaml helloworld.ml Hello World REPL 을이용한실행 : $ ocaml OCaml version # let hello = "Hello";; val hello : string = "Hello" # let world = "World";; val world : string = "World" # let helloworld = hello ^ " " ^ world;;

14 산술식 (Arithmetic Expressions) 숫값 ( 정수값, 실수값 ) 을계산하는식 # * 3;; - : int = 7 # *. 3.3;; - : float = 8.36 정수값을위한산술연산자 : a + b a - b a * b 덧셈뺄셈곱셈 a / b 나눗셈 ( 몫 ) a mod b 나눗셈 ( 나머지 ) 실수값을위한산술연산자 : +., -., *., /.,... 정수타입과실수타입을명확히구분 # ;; Error: This expression has type float but an expression was expected of type int # 3 + int_of_float 2.0;; - : int = 5

15 논리식 (Boolean Expressions) 논리값 ( 참, 거짓 ) 을계산하는식 # true;; - : bool = true # false;; - : bool = false 비교연산자 ( 산술식들로부터논리식을구성 ): # 1 = 2;; - : bool = false # 1 <> 2;; - : bool = true # 2 <= 2;; - : bool = true 논리연산자 ( 논리식들로부터새로운논리식을구성 ): # true && (false not false);; - : bool = true # (2 > 1) && (3 > 2);; - : bool = true

16 기본값 (Primitive Values) 프로그래밍언어에서기본적으로제공하는값 OCaml 은정수 (integer), 실수 (float), 논리 (boolean), 문자 (character), 문자열 (string), 유닛 (unit) 값을제공 # c ;; - : char = c # "Objective " ^ "Caml";; - : string = "Objective Caml" # ();; - : unit = ()

17 정적타입시스템 (Static Type System) 타입오류가있는프로그램은컴파일러를통과하지못함 : # 1 + true;; Error: This expression has type bool but an expression was expected of type int 발생가능한모든타입오류를실행전에찾아냄 OCaml 로작성된프로그램의안정성이높은이유

18 정적 / 동적타입시스템 타입시스템을기준으로한프로그래밍언어의구분 : 정적타입언어 (Statically typed languages) 타입체킹을컴파일시간에수행 타입오류를프로그램실행전에검출 C, C++, Java, ML, Scala, etc 동적타입언어 (Dynamically typed languages): 타입체킹을실행중에수행 타입오류를프로그램실행중에검출 Python, JavaScript, Ruby, Lisp, etc 정적타입언어들은다시두가지로구분 : 안전한 (Type-safe) 언어 : 타입체킹을통과한프로그램은실행중에타입오류가없음. 모든타입오류가실행전에검출됨. 프로그램이실행중에비정상적으로종료되지않음. ML, Haskell, Scala 안전하지않은 (Unsafe) 언어 : 타입체킹을통과해도실행중에여전히타입오류가발생가능 C, C++

19 장단점 정적타입언어 : (+) 타입오류가프로그램개발중에검출됨 (+) 실행중에타입체크를하지않으므로실행이효율적 ( ) 동적언어보다경직됨동적타입언어 : ( ) 타입오류가실행중에예상치못하게나타남 (+) 다양한언어특징을유연하게제공하기쉬움 (+) 쉽고빠른프로토타이핑

20 조건식 (Conditional Expression) if e 1 then e 2 else e 3 e 1 은반드시논리식이어야함. 즉 e 1 의값은참또는거짓 # if 1 then 2 else 3;; Error: This expression has type int but an expression was expected of type bool 조건식의값은 e 1 의값에따라서결정 # if 2 > 1 then 0 else 1;; - : int = 0 # if 2 < 1 then 0 else 1;; - : int = 1 e 2 와 e 3 는타입이같아야함 # if true then 1 else true;; Error: This expression has type bool but an expression was expected of type int

21 함수식 (Function Expression) fun x -> e 형식인자 (formal parameter) 가 x이고몸통 (body) 이 e인함수값 (function value) 을생성 함수의예 : fun x -> x + 1 fun y -> y * y fun x -> if x > 0 then x + 1 else x * x fun x -> fun y -> x + y fun x -> fun y -> fun z -> x + y + z 설탕구조 (syntactic sugar): fun x y -> x + y fun x y z -> x + y + z fun x 1 x n -> e

22 함수식 (Function Expression) # fun x -> x + 1;; - : int -> int = <fun> # fun y -> y * y;; - : int -> int = <fun> # fun x -> if x > 0 then x + 1 else x * x;; - : int -> int = <fun> # fun x -> fun y -> x + y;; - : int -> int -> int = <fun> # fun x -> fun y -> fun z -> x + y + z;; - : int -> int -> int -> int = <fun> # fun x y z -> x + y + z;; - : int -> int -> int -> int = <fun>

23 함수호출식 (Function Call) e 1 e 2 e 1 : 함수값을만들어내는식이어야함 e 2 : 함수전달인자 (actual parameter) # (fun x -> x * x) 3;; - : int = 9 # (fun x -> if x > 0 then x + 1 else x * x) 1;; - : int = 2 # (fun x -> if x > 0 then x + 1 else x * x) (-2);; - : int = 4 # (fun x -> fun y -> x + y) 1 2;; - : int = 3 # (fun x -> fun y -> fun z -> x + y + z) 1 2 3;; - : int = 6 e 2 는임의의식이가능 : # (fun f -> f 1) (fun x -> x * x);; - : int = 1 # (fun x -> x * x) ((fun x -> if x > 0 then 1 else 2) 3);; - : int = 1

24 Let Expression 값에이름붙이기 : let x = e 1 in e 2 e 1 의값을 x라고하고 e 2 를계산 x: 값의이름 ( 변수 ) e 1 : 정의식 (binding expression) e2 : 몸통식 (body expression) x 의유효범위 (scope) 는 e 2 # let x = 1 in x + x;; - : int = 2 # let x = 1 in x + 1;; - : int = 2 # (let x = 1 in x) + x;; Error: Unbound value x # (let x = 1 in x) + (let x = 2 in x);; - : int = 3

25 Let Expression e 1 과 e 2 는임의의식이될수있음 # let x = (let y = 1 in y + 1) in x + 1;; - : int = 3 # let x = 1 in let y = 2 in x + y;; - : int = 3 함수정의 : # let square = fun x -> x * x in square 2;; - : int = 4 # let add x y = x + y in add 1 2;; - : int = 3 재귀함수정의 : # let rec fact a = if a = 1 then 1 else a * fact (a - 1);; val fact : int -> int = <fun> # fact 5;; - : int = 120

26 연습문제 let a = 1 in let b = a + a in let c = b + b in c + c let x = 1 in let f y = x + y in let x = 2 in f x let x = 1 in ((let x = 2) + x)

27 함수값을자유롭게사용가능 프로그램에서함수도최대의자유도를가짐 (First-class values): 함수를지칭하는이름을만들수있음 : # let square = fun x -> x * x;; # square 2;; - : int = 4 함수를다른함수의인자로전달가능 : # let sum_if_true test first second = (if test first then first else 0) + (if test second then second else 0);; val sum_if_true : (int -> bool) -> int -> int -> int = <fun> # let even x = x mod 2 = 0;; val even : int -> bool = <fun> # sum_if_true even 3 4;; - : int = 4 # sum_if_true even 2 4;; - : int = 6

28 함수값을자유롭게사용가능 함수를다른함수의반환값으로전달가능 # let plus_a a = fun b -> a + b;; val plus_a : int -> int -> int = <fun> # let f = plus_a 3;; val f : int -> int = <fun> # f 1;; - : int = 4 # f 2;; - : int = 5 고차함수 (Higher-order function): 다른함수를인자로받거나반환하는함수. 언어의표현력을높이는주된특징.

29 패턴매칭 (Pattern Matching) 패턴매칭을이용한값의구조분석 팩토리얼예제 : let rec factorial a = if a = 1 then 1 else a * factorial (a - 1) let factorial a = match a with 1 -> 1 _ -> a * factorial (a - 1)

30 패턴매칭 (Pattern Matching) The nested if-then-else expression let isabc c = if c = a then true else if c = b then true else if c = c then true else false can be written using pattern matching: let isabc c = match c with a -> true b -> true c -> true _ -> false or simply, let isabc c = match c with a b c -> true _ -> false

31 자동타입추론 (Automatic Type Inference) C 나 Java 에서는타입을생략할수없음 : public static int f(int n) { int a = 2; return a * n; } OCaml 에서는타입을생략가능. 컴파일러가자동으로유추 : # let f n = let a = 2 in a * n;; val f : int -> int = <fun>

32 타입유추알고리즘 # let sum_if_true test first second = (if test first then first else 0) + (if test second then second else 0);; val sum_if_true : (int -> bool) -> int -> int -> int = <fun OCaml 컴파일러가타입을유추하는과정 : 1. The types of first and second must be int, because both branches of a conditional expression must have the same type. 2. The type of test is a function type α β, because test is used as a function. 3. α must be of int, because test is applied to first, a value of int. 4. β must be of bool, because conditions must be boolean expressions. 5. The return value of the function has type int, because the two conditional expressions are of int and their addition gives int.

33 타입을직접명시하는것도가능 # let sum_if_true (test : int -> bool) (x : int) (y : int) : int (if test x then x else 0) + (if test y then y else 0);; val sum_if_true : (int -> bool) -> int -> int -> int = <fun> 컴파일러가명시한타입이올바른지자동으로검증 : # let sum_if_true (test : int -> int) (x : int) (y : int) : int (if test x then x else 0) + (if test y then y else 0);; Error: The expression (test x) has type int but an expression was expected of type bool

34 다형타입 (Polymorphic Types) 아래프로그램의타입은? let id x = x OCaml 타입추론결과 : # let id x = x;; val id : a -> a = <fun> 임의의값에대해작동하는다형타입함수 : # id 1;; - : int = 1 # id "abc";; - : string = "abc" # id true;; - : bool = true 아래프로그램의타입은? let first_if_true test x y = if test x then x else y

35 예외처리 An exception means a run-time error: e.g., # let div a b = a / b;; val div : int -> int -> int = <fun> # div 10 5;; - : int = 2 # div 10 0;; Exception: Division_by_zero. The exception can be handled with try... with constructs. # let div a b = try a / b with Division_by_zero -> 0;; val div : int -> int -> int = <fun> # div 10 5;; - : int = 2 # div 10 0;; - : int = 0

36 예외처리 User-defined exceptions: e.g., # exception Problem;; exception Problem # let div a b = if b = 0 then raise Problem else a / b;; val div : int -> int -> int = <fun> # div 10 5;; - : int = 2 # div 10 0;; Exception: Problem. # try div 10 0 with Problem -> 0;; - : int = 0

37 리스트와재귀함수

38 튜플 (Tuples) 순서가있는값의묶음. 각구성요소는다른값을가질수있음 : # let x = (1, "one");; val x : int * string = (1, "one") # let y = (2, "two", true);; val y : int * string * bool = (2, "two", true) 패턴매칭을이용하여각구성요소를추출가능 : # let fst p = match p with (x,_) -> x;; val fst : a * b -> a = <fun> # let snd p = match p with (_,x) -> x;; val snd : a * b -> b = <fun> or equivalently, # let fst (x,_) = x;; val fst : a * b -> a = <fun> # let snd (_,x) = x;; val snd : a * b -> b = <fun>

39 튜플 (Tuples) let 에서패턴사용가능 : # let p = (1, true);; val p : int * bool = (1, true) # let (x,y) = p;; val x : int = 1 val y : bool = true

40 리스트 (Lists) 유한한원소들의나열 : # [1; 2; 3];; - : int list = [1; 2; 3] 순서가중요 : e.g., [3;4], [4;3], [3;4;3], [3;3;4] 모든원소가같은타입이어야함 [(1, "one"); (2, "two")] : (int * string) list [[]; [1]; [1;2]; [1;2;3]] : (int list) list 리스트의원소는변경이불가능 (immutable) 리스트의첫원소를 head, 나머지를 tail 이라고부름 # List.hd [5];; - : int = 5 # List.tl [5];; - : int list = []

41 리스트예제 # [1;2;3;4;5];; - : int list = [1; 2; 3; 4; 5] # ["OCaml"; "Java"; "C"];; - : string list = ["OCaml"; "Java"; "C"] # [(1,"one"); (2,"two"); (3,"three")];; - : (int * string) list = [(1, "one"); (2, "two"); (3, "thre # [[1;2;3];[2;3;4];[4;5;6]];; - : int list list = [[1; 2; 3]; [2; 3; 4]; [4; 5; 6]] # [1;"OCaml";3] ;; Error: This expression has type string but an expression was expected of type int

42 리스트를만드는방법 []: 빈리스트 (nil) :: (cons): 리스트의앞에하나의원소를추가 : # 1::[2;3];; - : int list = [1; 2; 3] # 1::2::3::[];; - : int list = [1; 2; 3] ([1; 2; 3] is a shorthand for (append): 두리스트를이어붙이기 : # [1; [3; 4; 5];; - : int list = [1; 2; 3; 4; 5]

43 리스트패턴 리스트를다룰때패턴매칭이매우유용하게쓰임 Ex1) 빈리스트인지검사하는함수 : # let isnil l = match l with [] -> true _ -> false;; val isnil : a list -> bool = <fun> # isnil [1];; - : bool = false # isnil [];; - : bool = true

44 리스트패턴 Ex2) 리스트의길이를구하는함수 : # let rec length l = match l with [] -> 0 h::t -> 1 + length t;; val length : a list -> int = <fun> # length [1;2;3];; - : int = 3 쓰이지않는구성요소는로대체가능 : let rec length l = match l with [] -> 0 _::t -> 1 + length t;; 리스트를다루는함수는주로재귀적으로정의

45 재귀적사고의강력함 Ex) 아래도형을그리는프로그램?

46 재귀적으로문제풀기 주어진문제의크기가충분히작다면직접푼다. 문제가충분히작지않다면, 1. 문제를동일한구조를가지는작은문제들로쪼갠다. 2. 쪼개진문제들을재귀적으로푼다. 3. 결과를합쳐서원래문제의답을구한다.

47 리스트길이구하기 (list length) # length [];; - : int = 0 # length [1;2;3];; - : int = 3 let rec length l = match l with [] -> 0 hd::tl -> 1 + length tl

48 예제 1: 리스트이어붙이기 (append) # append [1; 2; 3] [4; 5; 6; 7];; - : int list = [1; 2; 3; 4; 5; 6; 7] # append [2; 4; 6] [8; 10];; - : int list = [2; 4; 6; 8; 10] let rec append l1 l2 =

49 예제 2: 리스트뒤집기 (reverse) val reverse : a list -> a list = <fun> # reverse [1; 2; 3];; - : int list = [3; 2; 1] # reverse ["C"; "Java"; "OCaml"];; - : string list = ["OCaml"; "Java"; "C"] let rec reverse l =

50 예제 3: n 번째원소찾기 (nth-element) # nth [1;2;3] 0;; - : int = 1 # nth [1;2;3] 1;; - : int = 2 # nth [1;2;3] 2;; - : int = 3 # nth [1;2;3] 3;; Exception: Failure "list is too short". let rec nth l n = match l with [] -> raise (Failure "list is too short") hd::tl -> (*... *)

51 예제 4: 첫번째원소지우기 (remove-first) # remove_first 2 [1; 2; 3];; - : int list = [1; 3] # remove_first 2 [1; 2; 3; 2];; - : int list = [1; 3; 2] # remove_first 4 [1;2;3];; - : int list = [1; 2; 3] # remove_first [1; 2] [[1; 2; 3]; [1; 2]; [2; 3]];; - : int list list = [[1; 2; 3]; [2; 3]] let rec remove_first a l =

52 예제 5: 정렬된리스트에원소삽입 (insert) # insert 2 [1;3];; - : int list = [1; 2; 3] # insert 1 [2;3];; - : int list = [1; 2; 3] # insert 3 [1;2];; - : int list = [1; 2; 3] # insert 4 [];; - : int list = [4] let rec insert a l =

53 예제 6: 삽입정렬 (insertion sort) let rec sort l =

54 예제 6: 삽입정렬 (insertion sort) let rec sort l = cf) Compare with C-style non-recursive version: for (c = 1 ; c <= n - 1; c++) { d = c; while ( d > 0 && array[d] < array[d-1]) { t = array[d]; } } array[d] array[d-1] = t; d--; = array[d-1];

55 cf) 명령형 vs. 함수형프로그래밍 Imperative programming focuses on describing how to accomplish the given task: int factorial (int n) { int i; int r = 1; for (i = 0; i < n; i++) r = r * i; return r; } Imperative languages encourage to use statements and loops. Functional programming focuses on describing what the program must accomplish: let rec factorial n = if n = 0 then 1 else n * factorial (n-1) Functional languages encourage to use expressions and recursion.

56 cf) 명령형 vs. 함수형프로그래밍 함수형프로그래밍 높은추상화수준에서프로그래밍 견고한소프트웨어를작성하기쉬움 소프트웨어의실행성질을분석하기쉬움명령형프로그래밍 낮은추상화수준에서프로그래밍 견고한소프트웨어를작성하기어려움 소프트웨어의실행성질을분석하기어려움

57 cf) 오해 : 재귀함수는비싸다? In C and Java, we are encouraged to avoid recursion because function calls consume additional memory. void f() { f(); } /* stack overflow */ This is not true in functional languages. The same program in ML iterates forever: let rec f () = f () 단순히함수가재귀적으로정의되었다고계산과정이비싼것이아님.

58 Tail-Recursive Functions More precisely, tail-recursive functions are not expensive in ML. A recursive call is a tail call if there is nothing to do after the function returns. let rec last l = match l with [a] -> a _::tl -> last tl let rec factorial a = if a = 1 then 1 else a * factorial (a - 1) Languages like ML, Scheme, Scala, and Haskell do tail-call optimization, so that tail-recursive calls do not consume additional amount of memory.

59 cf) Transforming to Tail-Recursive Functions Non-tail-recursive factorial: let rec factorial a = if a = 1 then 1 else a * factorial (a - 1) Tail-recursive version: let rec fact product counter maxcounter = if counter > maxcounter then product else fact (product * counter) (counter + 1) maxcounter let factorial n = fact 1 1 n

60 연습문제 1: range 두수 n, m (n m) 을받아서 n 이상 m 이하의수로구성된리스트를반환하는함수 range 를작성하시오 : range : int -> int -> int list 예를들어, range 3 7 는 [3;4;5;6;7] 를계산한다.

61 연습문제 2: concat 리스트의리스트를받아서모든원소를포함하는하나의리스트를반환하는함수 concat 을작성하시오 : 예를들어, concat: a list list -> a list concat [[1;2];[3;4;5]] = [1;2;3;4;5]

62 연습문제 3: zipper 두리스트 a 와 b 를순차적으로결합하는함수 zipper 를작성하시오 : zipper: int list -> int list -> int list 순차적인결합이란리스트 a 의 i 번째원소가리스트 b 의 i 번째원소앞에오는것을의미한다. 짝이맞지않는원소들은뒤에순서대로붙인다. # zipper [1;3;5] [2;4;6];; - : int list = [1; 2; 3; 4; 5; 6] # zipper [1;3] [2;4;6;8];; - : int list = [1; 2; 3; 4; 6; 8] # zipper [1;3;5;7] [2;4];; - : int list = [1; 2; 3; 4; 5; 7]

63 연습문제 4: unzip 두원소를가지는튜플의리스트를두리스트로분해하는함수 unzip 을작성하시오 : 예를들어, unzip: ( a * b) list -> a list * b list unzip [(1,"one");(2,"two");(3,"three")] 은 ([1;2;3],["one";"two";"three"]) 을계산한다.

64 연습문제 5: drop 리스트 l 과정수 n 을받아서 l 의첫 n 개원소를제외한나머지리스트를구하는함수 drop 을작성하시오 : 예를들어, drop : a list -> int -> a list drop [1;2;3;4;5] 2 = [3; 4; 5] drop [1;2] 3 = [] drop ["C"; "Java"; "OCaml"] 2 = ["OCaml"]

65 고차함수

66 고차함수 (Higher-Order Functions) 다른함수를인자로받거나리턴하는함수 높은추상화 (abstraction) 수준에서프로그램을작성하게함 간결하고재활용가능한코드를작성하는데있어서필수

67 추상화 (Abstraction) 복잡한개념에이름을붙여서속내용을모른채사용할수있도록하는장치 좋은프로그래밍언어는강력한추상화기법을제공 ex) 을계산하는프로그램을작성하는방법 : 2*2*2 + 3*3*3 + 4*4*4 let cube n = n * n * n in cube 2 + cube 3 + cube 4 모든프로그래밍언어는추상화도구로변수와함수를제공 변수 : 반복적으로사용하는값에붙인이름 ( 일차 ) 함수 : 반복적으로사용하는연산에붙인이름 고차함수 : 반복되는프로그래밍패턴에붙인이름

68 List.map Three similar functions: let rec inc_all l = match l with [] -> [] hd::tl -> (hd+1)::(inc_all tl) let rec square_all l = match l with [] -> [] hd::tl -> (hd*hd)::(square_all tl) let rec cube_all l = match l with [] -> [] hd::tl -> (hd*hd*hd)::(cube_all tl)

69 List.map The code pattern can be captured by the higher-order function map: let rec map f l = match l with [] -> [] hd::tl -> (f hd)::(map f tl) With map, the functions can be defined as follows: let inc x = x + 1 let inc_all l = map inc l let square x = x * x let square_all l = map square l let cube x = x * x * x let cube_all l = map cube l Or, using nameless functions: let inc_all l = map (fun x -> x + 1) l let square_all l = map (fun x -> x * x) l let cub_all l = map (fun x -> x * x * x) l

70 퀴즈 1. map 의타입은? 2. map (fun x mod 2 = 1) [1;2;3;4] 의값은?

71 List.filter let rec even l = match l with [] -> [] hd::tl -> if hd mod 2 = 0 then hd::(even tl) else even tl let rec greater_than_five l = match l with [] -> [] hd::tl -> if hd > 5 then hd::(greater_than_five tl) else greater_than_five tl

72 List.filter filter : ( a -> bool) -> a list -> a list even = filter (fun x -> x mod 2 = 0) greater than five = filter (fun x -> x > 5)

73 List.fold right Two similar functions: let rec sum l = match l with [] -> 0 hd::tl -> hd + (sum tl) let rec prod l = match l with [] -> 1 hd::tl -> hd * (prod tl) # sum [1; 2; 3; 4];; - : int = 10 # prod [1; 2; 3; 4];; - : int = 24

74 List.fold right The code pattern can be captured by the higher-oder function fold: let rec fold_right f l a = match l with [] -> a hd::tl -> f hd (fold_right f tl a) let sum lst = fold_right (fun x y -> x + y) lst 0 let prod lst = fold_right (fun x y -> x * y) lst 1

75 fold right vs. fold left let rec fold_right f l a = match l with [] -> a hd::tl -> f hd (fold_right f tl a) let rec fold_left f a l = match l with [] -> a hd::tl -> fold_left f (f a hd) tl

76 차이점 순서 fold right 은리스트를오른쪽에서왼쪽으로 : fold right f [x;y;z] init = f x (f y (f z init)) fold left 는리스트를왼쪽에서오른쪽으로 : 타입 fold left f init [x;y;z] = f (f (f init x) y) z 결합법칙이성립하지않는 f 에대해서결과가다를수있음 fold_right : ( a -> b -> b) -> a list -> b -> b fold_left : ( a -> b -> a) -> a -> b list -> a fold left 는끝재귀호출 (tail-recursion)

77 예제 let rec length l = match l with [] -> 0 hd::tl -> 1 + length tl let rec reverse l = match l with [] -> [] hd::tl -> (reverse [hd] let rec is_all_pos l = match l with [] -> true hd::tl -> (hd > 0) && (is_all_pos tl) map f l = filter f l =

78 연습문제 1 고차함수 sigma를작성하시오 : sigma : (int -> int) -> int -> int -> int sigma f a b는다음을계산한다. b f (i). i=a 예를들어, 의값은 55 이고, sigma (fun x -> x) 1 10 는 140 을계산한다. sigma (fun x -> x*x) 1 7

79 연습문제 2 fold right 을이용하여고차함수 all 을작성하시오 : all : ( a -> bool) -> a list -> bool all p l 은리스트 l 의모든원소들이함수 p 의값을참으로만드는지여부를나타낸다. 예를들어, 는 true 를계산한다. all (fun x -> x > 5) [7;8;9]

80 연습문제 3 fold left 를이용하여정수리스트를숫자로변환하는함수를작성하시오 : lst2int : int list -> int 예를들어, lst2int [1;2;3] 는 123 을계산한다. 리스트의원소들은 0 이상 9 이하의수라고가정한다.

81 함수를반환하는함수의예 함수합성 (composition): Let f and g be two one-argument functions. The composition of f after g is defined to be the function x f (g(x)). In OCaml: let compose f g = fun x -> f(g(x)) What is the value of the expression? ((compose square inc) 6)

82 연습문제 4 함수 f 와인자 a 를받아서 f 를 a 에두번적용한결과를반환하는함수 double 을작성하시오 : 예를들어, # let inc x = x + 1;; val inc : int -> int = <fun> # let mul x = x * 2;; val mul : int -> int = <fun> # (double inc) 1;; - : int = 3 # (double mul) 1;; - : int = 4 아래식의값은? double: ( a -> a) -> a -> a ((double double) inc) 0 (double double) mul 2 ((double (double double)) inc) 5

83 연습문제 5 고차함수 iter 를작성하시오 : iter : int * (int -> int) -> (int -> int) 정의는다음과같다 : iter(n, f ) = f} {{ f}. n n = 0 이면, iter(n, f ) 은항등함수 (identify function) 으로정의한다. n > 0 이면, iter(n, f ) 은 f 를 n 번반복적용하는함수이다. 예를들어, 는 2 n 를계산한다. iter(n, fun x -> 2+x) 0

84 사용자정의타입

85 이미있는타입에새로운이름붙이기 type var = string type vector = float list type matrix = float list list let rec transpose : matrix -> matrix =fun m ->...

86 새로운타입만들기 (Variants) If data elements are finite, just enumerate them, e.g., days : # type days = Mon Tue Wed Thu Fri Sat Sun;; type days = Mon Tue Wed Thu Fri Sat Sun Construct values of the type: # Mon;; - : days = Mon # Tue;; - : days = Tue A function that manipulates the defined data: # let nextday d = match d with Mon -> Tue Tue -> Wed Wed -> Thu Thu -> Fri Fri -> Sa Sat -> Sun Sun -> Mon ;; val nextday : days -> days = <fun> # nextday Mon;; - : days = Tue

87 새로운타입만들기 (Variants) Constructors can be associated with values, e.g., # type shape = Rect of int * int Circle of int;; type shape = Rect of int * int Circle of int Construct values of the type: # Rect (2,3);; - : shape = Rect (2, 3) # Circle 5;; - : shape = Circle 5 A function that manipulates the data: # let area s = match s with Rect (w,h) -> w * h Circle r -> r * r * 3;; val area : shape -> int = <fun> # area (Rect (2,3));; - : int = 6 # area (Circle 5);; - : int = 75

88 새로운타입만들기 (Variants) Inductive data types, e.g., # type mylist = Nil List of int * mylist;; type mylist = Nil List of int * mylist Construct values of the type: # Nil;; - : mylist = Nil # List (1, Nil);; - : mylist = List (1, Nil) # List (1, List (2, Nil));; - : mylist = List (1, List (2, Nil)) A function that manipulates the data: # let rec mylength l = match l with Nil -> 0 List (_,l ) -> 1 + mylength l ;; val mylength : mylist -> int = <fun> # mylength (List (1, List (2, Nil)));; - : int = 2

89 새로운타입만들기 (Parameterized Variants) 임의의타입을담을수있는리스트를만드려면? e.g., lists of ints, lists of strings, lists of lists of ints, etc 다른타입을인자로가지는타입을정의가능 : # type a mylist = Nil Cons of a * a mylist;; type a mylist = Nil Cons of a * a mylist # let l1 = Cons (3, Nil) ;; val l1 : int mylist = Cons (3, Nil) # let l2 = Cons ("three", Nil);; val l2 : string mylist = Cons ("three", Nil) # let rec length l = match l with Nil -> 0 Cons (_,t) -> 1 + length t;; val length : a mylist -> int = <fun> mylist: 다른타입을인자로받아서다른타입을만들어내는타입생성자 (type constructor) int mylist, float mylist, (int * float) mylist, etc

90 연습문제 1: 이진나무 (ver. 1) 이진나무 (binary tree) 는다음과같이정의할수있다 : type btree = Empty Node of int * btree * btree 예를들어, let t1 = Node (1, Empty, Empty) let t2 = Node (1, Node (2, Empty, Empty), Node (3, Empty,Empty)) 이진나무에서주어진원소가존재하는지여부를반환하는함수 mem 을작성하시오 : mem: int -> btree -> bool 예를들어, 는 true 이고, 는 false 이다. mem 1 t1 mem 4 t2

91 연습문제 2: 이진나무 (ver. 2) 이진나무를다음과같이정의하자. type btree = Leaf of int Left of btree Right of btree LeftRight of btree * btree 예를들어, Left (LeftRight (Leaf 1, Leaf 2)) 이진나무의왼쪽, 오른쪽자식을재귀적으로모두교환하는함수 mirror 를작성하시오 : 예를들어, mirror : btree -> btree mirror (Left (LeftRight (Leaf 1, Leaf 2))) 는 Right (LeftRight (Leaf 2, Leaf 1)) 를계산한다.

92 연습문제 3: 계산기 (ver. 1) type exp = Const of int Minus of exp Plus of exp * exp Mult of exp * exp 위산술식의값을계산하는함수 를작성하시오. 예를들어, 는 3 을계산한다. calc: exp -> int calc (Plus (Const 1, Const 2))

93 연습문제 4: 계산기 (ver. 2) type exp = X INT of int ADD of exp * exp SUB of exp * exp MUL of exp * exp DIV of exp * exp SIGMA of exp * exp * exp 위식에대한계산기를작성하시오 : calculator : exp -> int 예를들어, 는다음과같이표현되며 10 x=1 (x x 1) SIGMA(INT 1, INT 10, SUB(MUL(X, X), INT 1)) 그계산결과는 375 이다.

94 리뷰 OCaml 기본구성 : 식, 변수, 함수, 유효범위 리스트와재귀함수 고차함수 사용자정의타입 감사합니다!

OCaml

OCaml OCaml 2009.. (khheo@ropas.snu.ac.kr) 1 ML 2 ML OCaml INRIA, France SML Bell lab. & Princeton, USA nml SNU/KAIST, KOREA 3 4 (let) (* ex1.ml *) let a = 10 let add x y = x + y (* ex2.ml *) let sumofsquare