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

Tutorials/Ocaml

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

hashnut 2019. 9. 17. 20:26

예제들을 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/

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

#### 'Tutorials > Ocaml' 카테고리의 다른 글

 OCaml Library module "List" implementation  (0) 2019.09.17 2019.09.17 2019.09.17 2019.09.16