Lec-OCaml. Functional Programming in OCaml (4주차 2강, 5주차 1/2강)

9월 25일 4주차 2강 + 9월 30일 5주차 1강 + 10월 2일 5주차 2강

 

* 본 글은 개인 공부용으로 정리한 것 입니다. 정확한 내용은 본인이 공부하는 자료를 참고하시길 바랍니다!!

 

OCaml이 진짜 문대...그게문데문대...나는 high level만 먹는다고...

 

1. Introduction

1.1. Functional Programming?

• 함수: first-class
  • 변수에 저장된다
  • 다른 함수의 인자로 전달될 수 있다
  • 다른 함수의 반환값으로 사용할 수 있다
• expression-oriented: 계산 과정이 값을 변형하지 않고 표현식으로 기술된다...(아래 참고)
  • imperative version: 명령형 방식, int factorial(int n)에서 r을 계속 갱신하면서 계산
  • functional version: 함수형 방식: let rec fact n, 상태를 변경하지 않고 재귀적 호출로 표현식만 계산

1.2. Why Functional Programming?

• 함수형 언어를 사용하면 코드를 더 간결하게짤 수 있음 (재귀, 패턴 매칭 등)
• 함수형 프로그래밍은 명령형 프로그래밍과 달리 새로운 사고 방식을 습득할 수 있다
• 함수형 언어는 실무와 학계에서 많이 쓰이고 있다

• C, Java: 함수 호출이 memory를 소모함. 무한 재귀 호출 = stack overflow 유발
  • void f() { f(); } - 무한히 재귀 호출이 이뤄져 stack이 가득차면서 segmentation fault 발생
• function lang: 무한히 반복되어도 문제 없음
  • lec rec f() =f() - 재귀 호출이 무한히 발생해도 문제 없음
  • tall-call optimization: ML, Scheme, Scala, Haskell 같은 함수형 언어의 interpreter와 compiler가 수행함

• tail-call optimization: 재귀 함수의 마지막 호출이 또 다른 함수로 이어지는 경우, 새로운 stack frame 생성하지 않음
  • non-tail-recursive factorial: let rec fact a = if a = 1 then 1 else a * fact (a - 1)
    • fact(a-1) 호출 후, 반환된 값에 a를 곱하는 연산이 이루어짐
    • a를 곱하는 연산이 마지막에 이뤄지므로, 재귀 호출 후에도 연산을 수행해야 해서 최적화가 불가능
  • tail-recursive version: let rec fact n acc = if n = 0 then acc else fact (n - 1) (n * acc)
    • acc 누적 변수에 재귀 호출 결과값을 누적함. 처음에는 1로 초기화 됨
      • f(n-1): 팩토리얼을 구하는 재귀 호출, 다음 재귀 단계로 넘어가는 부분
      • (n*acc): 다음 재귀 단계로 넘길 중간 결과. 현재값 n * 기존 acc 값을 곱함
    • fact(5,1)을 예시로 호출해보자
      • fact(5, 1) → fact(4, 5 * 1) → fact(4, 5)
      • fact(4, 5) → fact(3, 4 * 5) → fact(3, 20)
      • fact(3, 20) → fact(2, 3 * 20) → fact(2, 60)
      • fact(2, 60) → fact(1, 2 * 60) → fact(1, 120)
      • fact(1, 120) → fact(0, 1 * 120) → acc = 120
      • n=1이 되면, acc에 120이 return됨
    • 재귀 호출 후 연산이 발생하지 않음. fact(n-1)이 마지막 작업임. 최적화 가능

1.3. Why Function Programming in OCaml

• OCaml은 ML(Meta Lang) 계열의 프랑스 방?언이라고 함(네? 방언이요?) 아무트 함수형 프로그래밍에 좋음
• Functional Programming: Scala, Java8, Haskell, Python, JavaScript 등과 함께 함수형 프로그래밍을 지원
• Static하고 Sound한 Type System:
  • static: 컴파일 단계에서 type을 확인함
  • sound: 프로그램에서 타입 오류가 발생하지 않도록 보장(안전하다)
• 자동 타입 추론: OCaml은 타입을 명시하지 않아도 자동으로 타입 추천해줌(Scala, Haskell도 ㄱㄴ)
• 패턴 매칭: 간결하게 case analysis 가능(Scala도 ㄱㄴ)
• Algebraic data types, module system 등...
• OCaml로 구현된 프로젝트 예시
  • Infer(Facebook): Java, C++, Objective-C, C 언어에서 메모리 누수를 감지
  • VeriSmart: 스마트 계약 안전성 검증
• 어쩄든 타입 체킹에 좋대요

 

 

2. OCaml Basic Topics

• Expressions
• Names
• Functions
• Pattern matching
• Type inference
• Tuples and lists
• Variants (union data types)
• Exceptions
• Modules

 

3. OCaml

대 카 믈

3.1. Basic Structure

• 여러 let 문으로 구성됨. 변수 x_i에 표현식 e_i 값을 할당하는 구조
• e1, e2, ..., en 순차적으로 평가 됨
• 변수 x_i는 표현식 e_i 값을 참조함. 변수를 통해 표현식의 결과를 사용할 수 있음

• 국룰 예졔: Hello World
  • let hello = "Hello": 변수 hello에 문자열 "Hello"를 할당.
  • let world = "World": 변수 world에 문자열 "World"를 할당.
  • let helloworld = hello ^ " " ^ world: 결합 연산자 ^로 두 변수 사이에 " " 공백을 넣어 결합
  • let _ = print_endline helloworld: helloworld 문자열을 출력, let _는 결과값을 사용하지 않겠다는 뜻
• Interpreter: Ocaml 파일에 위 내용을 넣고 ocaml helloworld.ml 로 실행할 수 있음
• Real-Eval-Print-Loop
  • OCaml 인터프리터에서 직접 코드를 입력하고 실행할 수 있음
  • ocaml 명령어로 대화형 모드에 진입
  • 각 명령어 뒤에는 ;;를 붙여서 해당 변수의 끝을 알림 (세미콜론 두 개인 거 줫나 헷갈림)

3.2. Expressions

3.2.1. Arithmetic Expressions: 산술 표현식

 

• a + b: 덧셈
• a - b: 뺄셈
• a * b: 곱셈
• a / b: 나눗셈 (정수 나눗셈, 나눈 값의 몫을 반환)
• a mod b: 나눗셈의 나머지
• REPL에서 1+2*3;;을 입력하면 결과인 7와 함께 type인 int도 반환

3.2.2. Boolean Expressions

• (true, false) 같은 값으로 evaluate 됨
• comparison(비교) 연산자로 boolean value를 생산함
  • a = b: a와 b가 같으면 true
  • a <> b: a와 b가 다르면 true
  • a < b: a가 b보다 작으면 true
  • a <= b: a가 b보다 작거나 같으면 true
  • a > b: a가 b보다 크면 true
  • a >= b: a가 b보다 크거나 같으면 true
• REPL 예시
  • # true;; - : bool = true
  • # false;; - : bool = false
  • # 1 > 2;; - : bool = false

• Boolean expresison은 boolean operator로 결합할 수 있음

3.2.3 기본적인 Type에 대한 설명

 

• 올바르지 않은 expression을 평가하려고 하면 에러 반환함
• 예를 들면 정수와 boolean을 더하려고 할 때 error

• Statically Typed Languages: 정적 타입 언어
  • 타입 검사: 컴파일 시점에 이뤄짐. 프로그램 실행 전에 타입 오류 감지
  • C, C++, Java, ML, Scala
• Dynamically Typed Language:
  • 타입 검사: 런타임 시점에 이뤄짐. 프로그램 실행 중에 타입 오류 감지
  • Python, JavaScript, Ruby, Lisp

• Static Type Lang은 두 가지로 세분화 가능
• Type-safe Language
  
  • 런타임에 타입 오류가 발생하지 않음을 보장. 컴파일 시점에 타입 오류 모두 검출
  • 타입 오류가 완전히 방지되기 때문에 안전한 실행 보장
  • ML Haskell, Scala
• Unsafe Lang
  • 런타임 중 일부 타입 오류 발생 가능. 컴파일 시점에 모든 타입 오류를 못잡음
  • C, C++

 

• 장단점을 비교해보자
• 정적 타입 언어
  • 장점: 타입 오류를 개발 초기에 잡을 수 있다. 런타임에서 타입 검사 없이 빠른 실행 가능
  • 단점: 컴파일 시 타입이 미리 정의되어야 해서 덜 flexible
• 동적 타입 언어
  • 장점: 빠르게 프로토타이핑. 타입 선언 없이 빠르게 코드 작성. 더 flexible한 코딩 가능.
  • 단점: 런타임에 타입 오류 발생

• 다른 type 사이에서 비교
• OCaml에서는 서로 다른 타입의 값을 구분함. int(정수)와 float(실수)는 명확히 구분 됨
• 명시적인 타입 변환: int_of_float으로 실수 2.0을 정수로 변환해야 연산이 가능함. 결과는 int로 반환
• 실수에 대한 연산자: 실수 연산을 위해 +. *. 연산자가 별도로 존재함. float_of_int는 정수 1을 실수로 변환함.

• Ocaml은 6개의 primitive value를 제공함
  • integer, boolean, floating point number, character, string, unit
  • () : unit type의 유일한 값. 의미있는 값을 반환할 필요가 없는 경우에 사용. 결과값이 중요하지 않은 함수
  • # print_endline "HI" : "HI"를 출력하고 - : unit = ()를 반환. 의미있는 값을 반환하지 않음

3.2.4. Conditional Expression

• if be then e₁ else e₂: be가 참이면, 조건식의 값은 e_1, be가 거짓이면 e_2
• be는 반드시 boolean expression이어야 함. e_1과 e_2의 타입이 같아야 함.
• 예시
  • # if 2 > 1 then 0 else 1;; 2>1이 참이므로 0 반환
  • # if 2 < 1 then 0 else 1;; 2<1이 거짓이므로 1 반환
  • # if true then true else false;; true이므로 true 반환
  • 오류  # if 1 then 1 else 2;; 1은 boolean expresison이 아니므로 오류 발생
  • 오류  # if true then 1 else true;; e_1과 e_2의 타입이 다름. 오류 발생

3.2.5. Functions

• # let x = 3 + 4;;  -> val x : int = 7, 변수 x에 값 7이 바인딩 됨.
• 아까 정의한 x값을 사용해서 연산할 수 있음 # let y = x + x;; -> 결과 val y : int = 14
• let ... in ... 구문을 사용하여 지역 변수를 생성할 수 있음
  • let x = e₁ in e₂, x는 e1에 바인딩되고, e2 범위 내에서만 유효함
    • e2의 값이 전체 expression의 최종 값이 됨

 

• # let a = 1 in a;; a가 값 1에 바인딩되고, 이를 그대로 반환함
• # let a = 1 in a * 2;; a가 1로 정의되었고, 이것에 2를 곱한 값을 반환함
• let a = 1 in
  let b = a + a in
  let c = b + b in
  c + c;;
  • a에 1 할당, b에 a+a=2 할당, c에 b+b=4 할당, 그리고 c+c=8 반환

• # let square x = x * x;; -> val square : int -> int = <fun> 입력받은 인자의 제곱 값을 반환
• # square 2;; 2를 square 함수에 전달해서 제곱 값인 4을 반환
• # square (2 + 5);; 에 2+5를 전달해서 제곱값인 49 반환
• # square (square 2);;에 square 2 반환값인 4을 square에 다시 집어넣어서 16 반환
• # let neg x = if x < 0 then true else false;;
  • neg 함수는 입력된 x의 값이 음수이면 true, 아니면 false를 반환한다
  • x의 값은 int이고, 반환되는 값은 bool임. 그래서 int->bool=<fun>
  • neg 1;; -> bool=false, neg (-1);; -> bool=true

• # let sum_of_squares x y = (square x) + (square y);;
  • sum_of_squares 함수는 입력받은 x와 y를 square 함수에 각각 적용시킨 후 합을 return함
  • x: int, y: int, square x+square y: int
• # let rec factorial a = if a = 1 then 1 else a * factorial (a - 1);;
  • rec -> 재귀함수를 정의할 때 사용하는 키워드
  • 기본적으로 함수를 정의할 때 함수 내에 그 함수의 이름을 참조할 수 없음.
  • 하지만 rec 키워드를 사용하면 함수 정의 내부에서 자기 자신을 참조할 수 있음
  • 따라서 factorial 함수를 재귀로 정의한다는 뜻이 되는 것임
  • input 값인 a는 int
    • return 값은 1 또는 a*factorial(a-1)인데, if문에서 e_1과 e_2의 type은 같아야 하기도 하고
    • factorial(1)일 때 종료되는데, 이 때 값은 1, 그리고 누적돼서 곱해지는 a의 값도 int 그래서 return값은 int
    • 그래서 int -> int = <fun>이 됨

• OCaml에서 함수 이름 없이 함수를 정의할수 있음
  • # fun x -> x * x;; - : int -> int = <fun>
• 일반 함수처럼 호출할 수 있음. # (fun x -> x * x) 2;; - : int = 4
• nameless function을 변수에 바인딩해서 쓸 수 있음. # let square = fun x -> x * x;;
• nameless 함수와 일반 함수는 동일한 기능을 수행함
  • let square = fun x -> x * x
  • let square x = x * x

• value가 first class라는 의미는 다음과 같다
  • 변수에 저장될 수 있다
  • 함수의 인자로 전달될 수 있다
  • 다른 함수로부터 반환될 수 있다
• function이 first class value에 해당되면, 그 언어를 functional이라고 부른다

• function이 variable에 저장될 수 있다
  • let square = fun x -> x * x;;
  • square 2는 4를 return
• 다른 함수의 인자로 전달될 수 있다
  • let sum_if_true test first second = (if test first then first else 0) + (if test second then second else 0);;
    • test는 조건을 평가하는 함수
    • sum_if_true는 frist와 second 값을 입력받고, test로 조건을 평가함
    • first 값을 test했을 때 결과에 따라 first를 더하거나, 더하지 않음. second도 마찬가지임
    • (int->bool): test 자리에 "정수를 입력값으로 받는 함수"를 인자로 받아서, boolean을 반환함. 
    • first: int 입력, second: int 입력 -> test 자리에 입력받은 함수의 판결 결과에 따라 두 값을 더해서 int 반환
  • let even x = x mod 2 = 0;;
    • even함수는 int x를 입력 받아서, 2로 나눈 나머지가 0인 (even)인 값인지 판별해서 boolean 반환함
  • sum_if_true even 3 4;;
    • even함수를 조건 판별 함수로 쓰고, 3과 4를 인자로 입력함 -> 4만 살아남아서 4 return

• 함수를 반환하는 함수
  • let plus_a a = fun b -> a + b;;
    • 정수 a를 입력받고, 정수 b를 입력받아 두 값을 더한 결과 int를 반환
  • let f = plus_a 3;; 함수 f는 plus_a에 3을 입력한 함수를 반환함 (함수를 반환하는 함수)
  • f 1
    • let f = plus_a 3;
    • lef f = fun b -> 3+b;
    • f 1 = fun 1 -> 3 + 1 = 4를 반환함
  • f2
    • let f = fun b -> 3+b;
    • f 2 = fun 2 -> 3 +2 = 5를 반환함
  • 고차 함수의 동작 -> f는 plus_a 함수 자체를 반환하고, 반환된 함수는 다시 호출되어 원하는 계산을 수행
  • higher-order functions

3.2.6. Pattern Matching

• 패턴 매칭 - 조건을 분석하는 편리한 방법, case analysis
• 팩토리얼 함수
  • 기존: let rec factorial a = if a = 1 then 1 else a * factorial (a - 1)
  • 패턴 매칭:
    let rec factorial a = match a with
    | 1 -> 1 // 1인 경우에는 1을 반환한다
    | _ -> a * factorial (a - 1) // 그 외는 _로 처리되며, a*factorial(a-1)을 반환한다.
  • _는 wild card. 어떤 값이 오더라도 해당 구문에서 처리함.
• list나 variant type을 처리할 때 장점이 있다.

 

• 중첩된 if-then-else를 표현하는 경우
• c가 'a', 'b' 또는 'c'일 경우 true를 반환함.
• 패턴매칭을 사용할 경우 else if를 반복하지 않고, 이 경우엔 이걸 반환해줘!라는 식으로 작성할 수 있음
• 간단하게 'a'|'b'|'c' -> true로 반환할 수 있음.

3.2.7. Type Inference

• C나 Java에서는 타입을 명시적으로 선언해야 함. OCaml은 딱히 안그래도 됨

• 위에서 했던 예제긴 한데 sum_if_true 함수의 type에 대해 물어봄
  • test 함수는 int 값을 입력받아서 boolean을 반환함 int->boolean
  • first, second는 int 값임
  • (int -> boolean) -> int -> int -> int = <fun>
• OCaml 컴파일러는 아래와 같은 스탭을 따름
  • first, second는 int여야 한다. 왜냐면 if문에서 e1이랑 e2의 타입이 같아야 되는데, 둘다 e2값이 0이라 int임
  • test는 함수로 사용되고 있기 때문에 알파->베타 형태의 함수여야 함
  • 알파는 int여야 함. 왜냐면 test는 first를 인자로 받고 있는데, 그가 int이기 때문
  • 베타는 bool이어야 함. 왜냐면 test의 결과는 if문 내에서 쓰이고 있는데, if 조건 판별 부분은 boolean이어야 함
  • 반환 값은 int여야 함. 왜냐면 두 condition expression 결과가 int이고 두 값의 합은 int이기 때문
  • (bool->int) -> int -> int -> int = <fun>

 

• 명시적으로 타입을 지정할 수 있음
• 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);;
• let sum_if_true : (int -> bool) -> int -> int -> int = fun test x y -> (if test x then x else 0) + (if test y then y else 0);;
• 만약 잘못 명시하면 오류를 뱉을거임
  • 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);;
  • int -> int << test함수는 if문에서 조건 함수로 사용되니까 return값이 bool이어야 됨. 틀렸슈

• let id x = x
  • OCaml은 val id : 'a -> 'a = <fun> 라고 타입을 정의함
  • 'a는 어떤 타입이든 될 수 있음. 어떤 타입의 값이든 받아서 동일한 타입의 값으로 반환할 수 있음
• 예제에서 입력한 인자들의 type을 판단해서 그대로 타입 = 값 형태로 return하고 있음
• polymorphic이라고 부름. 다형성

• 공식 답이 아님. 걍 내가 생각해봄
  
  • let first_if_true test x y =  if test x then x else y
  • x랑 y는 if문의 e_1 e_2이니까 타입이 같아야됨
  • test는 bool을 return해야 됨
  • test는 x를 인자로 받아서 bool을 return함
  • 근데 x가 딱히 무슨 타입이든 상관 없음. 그래서 x랑 y는 'a임
  • ('a -> bool) -> `a -> `a -> `a

3.2.8. Tuples

• 서로 다른 타입의 값을 포함할 수 있는 순서화된 값의 집합
• let x = (1, "one");; val x : int * string = (1, "one") x는 int랑 string 타입의 값을 포함하는 튜플
• let y = (2, "two", true);; val y : int * string * bool = (2, "two", true) y는 int, string, bool 포함하는 튜플
• 패턴 매칭을 사용해서 튜플의 값을 추출할 수 있음
  • let fst p = match p with (x, _) -> x;; val fst : 'a * 'b -> 'a = <fun>
  • x는 튜플의 첫 번째 요소, _는 두 번째 요소, 두 번째 값이 뭐든 신경 안쓰고 x 반환
  • let snd p = match p with (_, x) -> x;; val snd : 'a * 'b -> 'b = <fun>
  • x는 튜플의 두 번째 요소, _는 첫 번째 요소, 첫 번째 값이 뭐든 두번째 값 return
  • let fst (x, _) = x;; let snd (_, x) = x;; 이렇게도 표현할 수 있음

• 튜플 매칭은 let에서도 쓸 수 있음
• (x,y)에 P를 할당하면 각각 순서대로 int인 1과 bool인 true가 x,y에 할당됨

3.2.9. Lists

• 동일한 타입의 값들로 구성된 유한한 시퀀스
• 리스트로 묶어서 정의되고, 각 요소는 ;로 구분됨
• 다른 타입이 섞여있으면 유효하지 않은 리스트
• 요소는 order되어 있음.
• 첫 번째 요소는 head, 나머지는 tail
• [1;2;3]에서 1은 head, [2;3]은 tail
• special case
  • []는 빈 리스트, head와 tail이 따로 없어서 구분안됨
  • [5]는 1 요소짜리 list, 5가 head, tail은 []

• int만 들어간 int list
• string만 들어간 string list
• (int *string)이 들어간 list
• [1; "Ocaml"; 3]은 int랑 string이 섞여있음. 에러

• ::는 list의 front에 single element를 추가할 수 있음
• 1::2::3::[] -> 3부터 순서대로 차곡차곡 넣어서 [1;2;3]
• @는 두 list를 합칠 수 있음

• 어떤 type의 list든 상관 없음, 무조건 비어있으면 true 그 외엔 다 false
  • 'a list -> bool = <func>
  • isnil[1] -> bool = false
  • isnill [] -> bool = true

 

• h::t -> head를 제외하고 tail을 length 함수에 다시 반환함
• 그럼 tail에 []이 들어가기 전까지 계속 첫 번쨰 함수를 잘라낸 상태로 tail을 계속 집어넣고 그때마다 1씩 길어짐
• 단계적으로 보면
  • [1;2;3]인 경우
  • 1::[2;3] 에서 [2;3]을 다시 함수 인자로 넣음
  • 2::[3]에서 [3]을 다시 함수 인자로 넣음
  • 3::[]에서 []를 다시 함수 인자로 넣음 []->0으로 종결 조건
  • 그럼 그동안 더해진걸 보면 1+1+1이니까 3 return

• Variant: 여러 constructor(생성자)를 사용해서 다양한 형태의 값을 정의할 수 잇음
• type shape = Rect of int * int | Circle of int;;
  • shape이라는 새로운 타입을 정의했고, 두 가지 형태를 가질 수 있음
  • Rect of int * int : Rect는 두 개의 int를 가짐
  • Circle of int: Circle은 한 개의 int를 가짐
  • Rect (2,3);; shape = Rect(2,3)
  • Circle 5;; shape = Circle 5
• area 구하는 함수 만들깅
  • let area s = match s with  | Rect (w,h)->w*h | Circle r -> r*r*3;; shape -> val area int = <func>
  • area (Rect(2,3));; -> Rect(2,3) -> 2*3 결과 6 return

• variant type으로 재귀 데이터 타입 정의하기
  • type mylist = Nil | List of int * mylist;;
  • Nil: 리스트가 비어있음
  • List of int * mylist: 리스트는 정수와 다른 mylist를 포함할 수 있음. 
• Nill;;  mylist = Nil
• List (1,Nill);; mylist = List(1,Nil)
• List(1,List(2,Nil));; mylist = List(1,List(2,Nil))
• 길이 반환 함수
• let rec mylength l = match l with | Nil->0 | List(_,l') -> 1+ mylength l';; mylist -> int = <func>
• mylength (List (1, List(2,Nil)));;
  • (List(1, List(2,Nill)))에서 1, List(2,Nil)로 나뉘고, List(2,Nil)이 다시 mylength 함수로 들어감
  • List(2,Nill)에서 2, Nil이 되고, Nil이 mylength함수로 들어감
  • Nil이 들어와서 정지함
  • 그럼 1+1은 2가 return됨

3.2.9. Exceptions

• exception은 run time error를 의미함
• # let div a b = a / b;; int -> int -> int
• div 10 5;; int=2
• div 10 0;; 어 0으로 못나누는데? Exception 발생
• exception은 try ... with으로 다룰 수 있음
  • let div a b = try a/b with Division_by_zero -> 0;
  • 0으로 나누는 오류가 나오면 0을 대신 return하라는거임 그럼 핸들리 ㅇ가능

• 무려 사용자 정의 exception도 있음
  • exception Problem;;이라는 예외를 정의
  • let div a b = if b=0 then raise Problem else a/b;;
    • 만약 b가 0이 들어오면 Problem이라는 Exception을 발생함
  • try div 10 0 with Problem->0
    • Problem이라는 error가 발생하면 0을 return하도록 try with으로 한 번 더 감쌀 수 있음

3.2.10. Modules

• 모듈 시스템의 핵심 구조
  • Structure: 타입, 예외, value, 함수 등을 포함, 구현 세부사항을 의미
  • Signature: 구조의 인터페이스, 구조에 존재하는 세부사항이 외부에 어떻게 노출될지 정의
  • 추상화와 캡슐화의 일종.

• 큐 자료구조의 인터페이스
  • empty: 빈 큐
  • isempty: q가 비어있는지 확인하고 boolean을 반환(비어있으면 참)
  • enq(q,x): 큐의 끝에 요소 x를 추가함. 새로운 큐를 반환함
  • deq(q): 큐의 앞쪽에 요소를 제거함. 제거된 앞쪽 요소 반환. 비어있으면 예외 반환
  • print(q): q의 내용을 출력
  • E: deq 수행 시 q가 비어있으면 exception

• 큐의 signature
  • type t: 큐의 추상적인 타입을 나타냄 모듈 구현에서 t의 실제 구현이 결정됨
  • exception E: 큐가 비어있을 때 요소를 제거하려는 시도에서 발생하는 예외
  • val empty: t: empty는 빈큐. empty는 t 타입의 값을 반환하며, 빈 큐를 생성함
  • val is_empty: t->bool 큐를 입력으로 받아서 bool을 반환
  • val enq : t -> int -> t: enq는 큐에 새로운 요소를 추가하고 새로운 큐를 반환함
  • val deq : t -> int * t: deq는 첫 번째 요소를 제거하고 나머지를 반환.
    • (int, t) 형태의 튜플이고, 제거된 정수와 나머지 리스트 t를 튜플 형태로 반환
  • val print : t -> unit: 큐의 내용을 출력함. 반환값은 unit이라서 다른 값을 딱히 반환하진 않음

• 큐의 구현: structure에 해당
  • type t = int list: 정수 리스트로 정의
  • exception E: 예외 정의
  • let empty = []: 빈 리스트로 빈 큐 생성
  • let enq q x = q @ [x]: 기존 list x에 q를 결합함
  • let is_empty q = q = [] : 빈 리스트와 동일한지 비교해서 true false 반환
  • let deq q = match q with [] -> raise E | h::t -> (h, t) 첫 번째 요소 제거하고 반환. 만약 []이면 E 발생
  • let rec print q = ... : q 내용을 출력하는 재귀 함수. head 출력하고 " "출력하고 재귀 함수로 tail을 다시 집어넣음
    • head를 계속 떼서 반환함

• 실제로 적용해보기
  • let q0 = IntQueue.empty 빈 큐 생성 []
  • let q1 = IntQueue.enq q0 1 []와 1을 결합 [1]
  • let q2 = IntQueue.enq q1 2 [1]와 2 결합 [1;2]
  • let (_, q3) = IntQueue.deq q2 // 일단 deq q2는 (1,2)인데, 여기에서 (_,2)니까 q3은 2임
  • 순서대로 리스트 내용물만 원소 사이에 공백 넣어서 출력함

• let q4 = q1 @ [2]
  • q1는 IntQueue.t 타입임. 모듈에서 정의된 큐 타입이라 내부적으론 int list일지라도 외부에서는 아님
  • 외부에서는 IntQueue.t라는 추상적인 타입으로만 봄
  • 리스트 연산자 @는 'a list인 리스트에 대해 사용됨.
  • 그래서 양쪽 다 list여야 하는데, 지금 q1은 리스트가 아니라IntQueue.t임

4. 예제 타임

4.1. append

append x y = x @ y; 라고 하고 싶었는데 rec을 써야되는 것 같음

rec 쓰면 이렇게 됨

4.2. Reverse

4.3. nth element

 

오류 구현하면서 했던 실수 -> 재귀 부분에서 (n-1)이 아니라 n-1로 입력하면 항상 예외가 반환됨

괄호가 없으면 컴파일러가 이것을 nth tl이라는 함수 호출과 n-1이라는 수식을 분리해서 해석

 

• 먼저 nth tl이라는 부분을 계산하고, 그 결과에서 n 값을 빼는 식으로 해석
• 그런데 nth 함수는 l과 n이라는 두 개의 인자를 받아야 하므로, nth tl 부분은 함수 호출로 해석될 수 없어서 오류 발생

 

4.4. remove-first

 

• remove_first 3 [1;2;3;4;5];;
• hd=1, tl=[2;3;4;5] -> 1::remove_frist 3 [2;3;4;5]
• hd=2 tl=[3;4;5] -> 1::2::remove_first 3 [3;4;5]
• hd=3 tl=[4;5] -> 1::2::[4;5] ->[1;2;4;5]

 

4.5. insert

 

4 [1;2;3;5;6]

1::4 [2;3;5]

1::2:: 4 [3;5]

1::2::3:: 4 [5;6]

1::2::3:: hd::a::tl

삽질과정: 4<5일때 5::4::6으로 넣는 실수...

삽질과정: 그냥 a>hd일때 바로 집어넣고 끝냈더니, 원하는 order가 안나옴

 

4.6. Insertion sort

[3;2;4;1]

3::[2;4;1] -> insert 3 (sort [2;4;1])

sort [2;4;1] -> 2::[4;1] -> insert 2 sort [4;1]

sort [4;1] -> 4::[1] -> insert 4 sort [1]

sort [1] -> 1::[] -> insert 1 sort []

------

insert 1 [] -> [1]

insert 4 [1] -> 1::insert 4 [] -> 1::[4] -> [1;4]

insert 2 [1;4] -> 1::insert 2 [4] -> 1::2::[4] -> [1;2;4]

insert 3 [1;2;4] -> [1]::insert 3 [2;4] -> 1::2::insert 3 [4] -> 1::2::3::[4] -> [1;2;3;4]

4.7. Calculator

 

5. Summary

 

 

정리 시작: 24.10.20. 16:18

정리 종료:

노동료~: (정리하면서 뭐 들었는지 쓰는 이유? 그냥 추억 회상용?...)

My ordinary life, The Living Tombstone, I Got No Time

>> 알고리즘이 나에게 들이민 노래...

배너 곡들... 피크타임 경연곡이랑 신곡 오토매틱 엄청 들음

attwn park님 곡들 피냐타와 나 좋아함