PL2. OCaml

OCaml 언어란?

• 여러가지 사용법을 가지는 상위 (high-level) 언어
  • 절차형, 객체지향, 함수형 등의 프로그래밍을 모두 지원
• 편의성
  • 자동으로 메모리 관리 (garbage collector)
• 안정성
  • 타입 시스템

OCaml 설치하기

apt install ocaml
vi test.ml

// test.ml
print_string "Hello World"
:wq

ocamlc test.ml -o test
./test

Ocaml의 기초 문법

값에 이름 붙이기

let i = 1
let s = "hello world"
let b = true
let _ = print_endline "hello world"

값의 이름은 소문자로 시작해야 한다.
_를 unit타입이라고 부른다.

타입

모든 값은 타입을 가지며, 코드에 타입을 명시할 수도 있다.

let i = 1 (* i : int *)
let s = "hello world" (* s : string *)
let b = true (* b : bool *)

let i : int = 1
let s : string = "hello world"
let b : bool = true

타입 추론

OCaml은 자동으로 정확하게 타입을 추론해 주고, 프로그래밍에 타입 에러가 있다면 미리 잡아준다

따라서 타입을 쓰지 않아도 되지만, 모듈 타입, 레퍼런스 등 반드시 써야만 하는 경우도 가끔 있다

함수 정의하기

다양한 방법으로 함수를 정의할 수 있다.

let incr x = x + 1
let y = incr 5

let incr fun x -> x + 1
let y = incr 5

let y = (fun x -> x + 1) 5

함수도 값

함수도 값으로 취급하며, 그 값에 incr이라는 이름을 붙인 것으로 생각하면 된다.

모든 값은 타입을 가지므로, 함수도 타입을 가진다.

let incr : int -> int = fun x -> x + 1
let incr : float -> float = fun x -> x +. 1.0

함수 역시 OCaml이 자동으로 타입을 추론한다.

main 함수는?

OCaml은 main이 없다.

일련의 정의 (let)의 집합이며, 위에서부터 하나씩 실행한다.

예를 들어 factorial 함수는 다음과 같다.

let rec fact n =
  if n <= 0 then 1
  else n * fact (n - 1)

let x = fact 10

let _ = print_edline (string_of_int x)

Assignment

Ex 1. gcd

다음 함수를 작성하시오

• gcd : int -> int -> int
• 이 함수는 두 음이 아닌 정수의 최대공약수를 반환한다.
• 유클리드 호제법을 이용하여 구현하라.

Ex 1. Solution

let rec gcd : int -> int -> int = 
fun n m ->
  if n < m then
    if n == 0 then
      m
    else gcd (m - n) n
  else
    if m == 0 then
      n
    else gcd (n - m) m

Ex 2. prime

다음 함수를 작성하시오

• prime : int -> bool
• 이 함수는 그 숫자가 소수인지 판별한다.

Ex 2. Solution

let prime: int -> bool =
fun n -> 
  let rec loop i = 
    if (i * i > n) then true
    else if (n mod i <> 0) then loop (i + 1)
    else false 
  in n >= 2 && loop 2

Ex 3. sec_last

다음 함수를 작성하시오

• sec_last : int list -> int
• 이 함수는 리스트의 마지막에서 두번째 원소를 반환한다.

Ex 3. Solution

let rec length : int list -> int = 
fun li ->
  match li with
  | [] -> 0
  | _ :: tl -> 1 + length tl
;;

let rec nth : int list -> int -> int = 
fun li n ->
  match li with
  | [] -> failwith "Too Short"
  | hd :: tl ->
    if n == 0 then hd
    else nth tl (n - 1)
;;

let sec_last : int list -> int =
fun li ->
  let len = length li in
  nth li (len-2)
;;

Ex 4. fibo

다음 함수를 작성하시오

• fibo : int -> int
• 이 함수는 n번째 피보나치수를 반환한다.
• n은 0보다 큰 자연수이다.
• 함수는 "tail recursion" 스타일이어야 한다.

Ex 4. Solution

let fibo : int -> int =
fun n ->
  if (n < 0) then raise (Failure "Error")
  else
    let rec fibo_tail n prev sum=
      match n with 
      | 0 -> prev
      | 1 -> sum
      | _ -> fibo_tail (n-1) (sum) (prev + sum)
    in fibo_tail n 0 1 

Ex 5. range

다음 함수를 작성하시오

• range : int -> int -> int list
• 이 함수는 n 이상 m 이하의 모든 수로 이루어진 정렬된 리스트를 반환한다.
• n이 m보다 크면 빈 리스트를 반환한다.

Ex 5. Solution

let range : int -> int -> int list =
fun n m ->
  if (n > m) then []
  else
    let rec loop n m =
      if (n = m) then [m]
      else n::(loop (n+1) m)
    in loop n m

Ex 6. merge

다음 함수를 작성하시오

• merge : int list -> int list -> int list
• 이 함수는 두개의 내림차순으로 정렬된 리스트를 입력받는다.
• 두 리스트의 모든 원소를 포함한 내림차순으로 정렬된 리스트를 반환한다.

Ex 6. Solution

let rec merge : int list -> int list -> int list = 
fun a b ->
  match (a, b) with
  | [], [] -> []
  | [], _ -> b
  | _, [] -> a
  | hd_a::tl_a, hd_b::tl_b ->
    if (hd_a > hd_b) then
      (hd_a)::(merge (tl_a) b)
    else
      (hd_b)::(merge a (tl_b))

Ex 7. sigma

다음 함수를 작성하시오

• sigma : int * int * (int -> int) -> int
• sigma(a, b, f)는 다음 식의 결과값을 반환한다.

$\sum_{n = a} ^b f(n)$

Ex 7. Solution

let rec sigma : int * int * (int -> int) -> int =
fun (n, m, f) ->
  if (n > m) then 0
  else
    (f n) + sigma (n+1, m, f)

Ex 8. tail3

다음 함수를 작성하시오

• fold3 : ('a -> 'b -> 'c -> 'd -> 'a) -> 'a -> 'b list -> 'c list -> 'd list -> 'a
  이는 다음을 의마한다.
  fold3 f a b c d = f ... (f (f a b1 c1 d1) b2 c2 d2) ... bn cn dn

Ex 8. Solution

let rec fold3 : ('a -> 'b -> 'c -> 'd -> 'a) -> 'a -> 'b list -> 'c list -> 'd list -> 'a =
  fun f a b c d ->
    match (b, c, d) with
    | [], [], [] -> a
    | hd_b::tl_b, hd_c::tl_c, hd_d::tl_d -> fold3 f (f a hd_b hd_c hd_d) tl_b tl_c tl_d
    | _ -> failwith "Different Lengths"