OCaml 예제 코드 (Quicksort, Stack, Calculator, Prime Number Generator)

 

예제들을 OCaml로 구현해 보자.

OCaml quicksort code

(* pick the first element as a pivot *)
(*  ascending order *)
let rec qsort comp l = match l with
  | [] -> []
  | p::t ->
    let (l1,l2) = List.partition (fun x -> comp x p<0) t in
    (qsort comp l1) @ (p::qsort comp l2)

let _ =
  let l = [5;1;3;6;7;2;9;8;4;0] in
  print_endline "original list : ";
  List.iter (fun x -> print_int x;print_string " ") l;
  print_newline();
  print_endline "result of qsort : ";
  List.iter (fun x -> print_int x;print_string " ") (qsort compare l);
  print_newline()

---

OCaml Stack code

모듈로 구현하였다.

module type StackSig = 
sig
    type 'a stack
    exception StackEmpty

    val emptyStack : 'a stack
    val push : 'a stack * 'a -> 'a stack
    val pop : 'a stack -> 'a * 'a stack
end

module Stack : StackSig =
struct
    type 'a stack = 'a list
    exception StackEmpty
    let emptyStack = []
    let push (stk, itm) = itm::stk
    let pop stk =
        match stk with
          (itm::stack) -> (itm, stack)
        | [] -> raise StackEmpty
end

---

OCaml Calculator code

module type CalcSig = 
sig
    type exp = NUM of float
             | PLUS of exp * exp
             | MINUS of exp * exp
             | MUL of exp * exp
             | DIV of exp * exp
             | SQRT of exp
             | STORE of exp
             | RESTORE
             | SEQ of exp list

    val eval : exp -> float
end

module Calc : CalcSig =
struct
    type exp = NUM of float
             | PLUS of exp * exp
             | MINUS of exp * exp
             | MUL of exp * exp
             | DIV of exp * exp
             | SQRT of exp
             | STORE of exp
             | RESTORE
             | SEQ of exp list

    let s = ref 0.0

    let rec eval e =
        match e with
          NUM f -> f
        | PLUS (e1, e2) -> eval e1 +. eval e2
        | MINUS (e1, e2) -> eval e1 -. eval e2
        | MUL (e1, e2) -> eval e1 *. eval e2
        | DIV (e1, e2) -> eval e1 /. eval e2
        | SQRT e -> sqrt (eval e)
        | STORE e -> 
            let v = eval e in
                s := v;
                v
        | RESTORE -> !s
        | SEQ [] -> 0.0
        | SEQ [x] -> eval x
        | SEQ (x::l) -> (eval x; eval (SEQ l))
end

---

OCaml Prime Number Generator

(* gen a b : [a, ..., b] 리스트를 생성 *)
let rec gen a b =
    if a > b then []
    else a :: gen (a+1) b

(* filter f l : 리스트 l의 원소 x중 f(x)=true 인 것만 고른다.
   이 함수를 작성하지 않고 List.filter 를 써도 된다.
*)

let rec filter f l =
    match l with
      [] -> []
    | h::t -> if f h then
                h :: filter f t
              else
                  filter f t

(* [2, ..., n] 리스트를 만들고
   앞에서부터 머리값 h로 나뉘는 것들을 하나씩 지워나간다.
   단, h*h 가 n 보다 커지는 h 이후 할 필요없다.
*)

let sieve n =
    let rec loop l = 
        match l with
          [] -> []
        | h::t -> if h*h > n then l
                  else h :: loop (filter (fun x -> x mod h != 0) t)
    in
        loop (gen 2 n)

(* sieve 1000을 돌리고 출력한다. *)

let _ = List.iter (fun x -> print_int x; print_newline()) (sieve 1000)

 

Reference for more :

Quick sort : https://www.geeksforgeeks.org/quick-sort/

Stack : https://www.geeksforgeeks.org/stack-data-structure-introduction-program/

Calculator : https://www.geeksforgeeks.org/html-calculator/

Prime number generator : https://rosettacode.org/wiki/Extensible_prime_generator

https://stackoverflow.com/questions/20744025/prime-generator-algorithm