Archive | ML RSS feed for this section

Struktur data dan algoritma Tree pada ML (Meta Language)

26 Sep

Konsep struktur data Tree telah dipelajari pada kuliah struktur data dan algoritma. Soal-soal pada latihan tutorial kali ini adalah soal-soal yang relatif pernah dikerjakan secara imperatif. Peserta diharapkan memahami bagaimana algoritma tree direpresentasi dalam pemrograman fungsional. Peserta juga diharapkan dapat membandingkan penyelesaian imperatif dengan fungsional pada setial soal yang diberikan. Tuliskan analisa perbandingan dalam komentar program. Analisa perbandingan dapat meliputi: kompleksitas running time dan alokasi memory, kemudahan pembuatan/perbaikan/modifikasi program, dan kemudahan membaca program. Gunakan sebisa mungkin higher order function pada setiap soal. Bila ada yang kurang jelas pada soal, silahkan tambahkan asumsi anda.

1. Buatlah sebuah fungsi bernama “soal1”. Fungsi tersebut menerima sebuah string, dan menghasilkan list of pair, yang tiap pairnya menyatakan karakter dan jumlah kemunculan karakter tersebut pada string input. Urutan pada pair output tidak penting.

soal1 :  string → (char * int) list

Contoh:

– soal1 “saya makan”

> val it = [(#”s”, 1), (#”a”,4), (#”y”,1), (#”m”,1), (#”k”,1), (#”n”,1)]

(Catatan: soal ini terkait dengan penerapan huffman code untuk kompresi,  harap melanjutkan lagi pengerjaannya hingga sampai encoding dan decoding, tidak perlu  dikumpulkan pada tutorial, tapi sebagai bagian persiapan ujian)

2. Buatlah sebuah fungsi bernama “soal2”. Fungsi tersebut membaca sebuah input dengan struktur data tree dan memeriksa apakah input tree tersebut merupakan binary search tree atau tidak. Struktur data tree didefinisikan dengan:

datatype bst = Leaf | Node of int * bst * bst

soal2 : bst → bool

Contoh:

– val t1 = Node(6, Node(4,Leaf,Leaf),
Node(15, Node(11,Leaf,Leaf), Node(24,Leaf,Leaf)));
– soal2 t1;
> val it = true : bool

3. Buatlah sebuah fungsi bernama “soal3” yang menerima satu argument tree. Fungsi ini akan mencetak isi tree yang diberikan secara inorder. (hint: gunakan perintah “print”);

soal3 : bst → unit

4. Buatlah sebuah fungsi bernama “soal4” yang memiliki dua argumen. Argumen pertama adalah sebuah list bilangan dan argumen kedua adalah sebuah tree. Fungsi ini akan memasukan argumen pertama kedalam tree satu persatu mulai dari elemen pertama pada list, dengan tetap mempertahankan struktur binary search tree namun tidak perlu balance.

soal4 : int list → bst → bst

5. Buatlah sebuah fungsi bernama “soal5”. Fungsi ini serupa dengan “soal4” namun dengan mengimplementasikan AVL Tree. Input tree yang diberikan bila bukan merupakan AVL Tree maka soal5 memberikan output berupa exception “Input bukan AVL Tree”. (hint: gunakan
“raise”)
soal5 : int → bst → bst

JAWABAN:

load "List";
load "Int";

datatype bst = Leaf | Node of int * bst * bst;

val tr = Node (4,
Node (2,
Node (1, Leaf, Leaf),
Node (3, Leaf, Leaf)
),
Node (6,
Node (5, Leaf, Leaf),
Node (7, Leaf, Leaf)
)
);

val ntr = Node (4,
Node (2,
Node (3, Leaf, Leaf),
Node (1, Leaf, Leaf)
),
Node (6,
Node (5, Leaf, Leaf),
Node (7, Leaf, Leaf)
)
);

val soal1 = let
fun calc [] = []
| calc (c::cs)= let
val next = List.filter (fn x => x <> c) cs
in (c,length cs - length next + 1) :: (calc next) end
in calc o explode end;

fun inorder Leaf = []
| inorder (Node (k,l,r)) = inorder l @ [k] @ inorder r;

val soal2 = let
fun sorted [] = true
| sorted [_] = true
| sorted (x1::x2::xs) = x1 <= x2 andalso sorted (x2::xs)
in sorted o inorder end;

val soal3 = (map (print o Int.toString)) o inorder

fun insert (k,Leaf) = Node (k, Leaf, Leaf)
| insert (k, Node (x,l,r))= if k < x
then Node (x, insert (k,l), r)
else Node (x, l, insert (k,r))

exception NotBST;
fun soal4 ls tree = if soal2 tree
then foldl insert tree ls;
else raise NotBST

fun rotateR Leaf = Leaf
| rotateR (Node (k,Leaf,r)) = Node (k,Leaf,r)
| rotateR (Node (k,Node (l,ll,lr),r)) = Node (l,ll,Node (k,lr,r));

fun rotateL Leaf = Leaf
| rotateL (Node (k,l,Leaf)) = Node (k,l,Leaf)
| rotateL (Node (k,l,(Node (r,rl,rr)))) = Node (r,Node (k,l,rl),rr);

fun height Leaf = 0
| height (Node (_,l,r)) = Int.max (height l, height r) + 1

fun balance Leaf = Leaf
| balance (Node (k,l,r)) = if height l > height r
then let
fun rotate' tree = case tree of Leaf => Leaf
| (Node (x,xl,xr)) => if height xr > height xl
then rotateL tree
else tree
val subtree = (k,rotate' l,r)
in rotateR (Node subtree) end
else let
fun rotate' tree = case tree of Leaf => Leaf
| (Node (x,xl,xr)) => if height xl > height xr
then rotateR tree
else tree
val subtree = (k,l,rotate' r)
in rotateL (Node subtree) end;

fun isBalanced Leaf = true
| isBalanced (Node (k,l,r)) = Int.abs (height l - height r) <= 1
andalso isBalanced l
andalso isBalanced r;

fun rebalance Leaf = Leaf
| rebalance (Node (k,l,r)) = let
val tree = Node (k,rebalance l, rebalance r)
in if isBalanced tree
then tree
else balance tree
end;

exception NotAVL;
fun soal5 k tree = if soal2 tree andalso isBalanced tree
then rebalance (insert (k,tree))
else raise NotAVL;

Tags: , ,

Find real square roots in ML

3 May

Okay, pada kesempatan kali ini kita akan membahas functional programming ML untuk mencari nilai akar real dari sebuah bilangan a. Berikut adalah code-nya, silakan dilihat dan dipelajari:

fun findroot (a, x, acc) =
   let val nextx = (a/x + x) / 2.0
   in if abs (x-nextx) < acc*x then nextx
      else findroot (a, nextx, acc)
   end;

fun sqroot a = findroot (a, 1.0, 1.0E~10);

Kita dapat juga menulis fungsi tersebut dengan menggunakan metode seperti di bawah ini, sehingga terdapat fungsi di dalam fungsi. Check this out!

fun sqroot a =
   let val acc = 1.0E~10
   fun findroot x =
      let val nextx = (a/x + x) / 2.0
      in if abs (x-nextx) < acc*x then nextx
         else findroot nextx
      end
  in findroot 1.0 end;

Ya cukup sekian kodingan untuk menemukan atau find nilai real dari operasi akar atau square roots dari sebuah bilangan a di atas. Semoga dapat memberikan inspirasi bagi semua. Silakan mencoba, terima kasih.

Tags: , , , ,

Make Fibonacci Numbers in ML

3 May

Hari ini kita akan mencoba membuat fungsi yang akan mengembalikan fibonacci number atau urutan angka yang merupakan barisan fibonacci. Implementasi fungsi pada ML yang akan dibahas di bawah ini terbagi 2, menjadi fibonacci versi naive dan fibonacci yang lebih cepat atau faster.

Okay, berikut implementasi fibonacci versi naive:

fun fib 0 = 0
   |fib 1 = 1
   |fib n = fib(n-2) + fib(n-1);

Selanjutnya kita akan definisikan fungsi fibonacci yang implementasinya akan lebih cepat daripada fungsi di atas:

fun fib(prev, curr:int) = (curr, prev+curr);

fun fibpair (n) =
   if n=1 then (0,1)
   else fib(fibpair(n-1));

Fungsi di atas akan lebih cepat daripada sebelumnya walaupun kita tidak memakai tail recursive. Silakan mencoba dan berkreasi sendiri dengan fungsi fibonacci yang saya paparkan, terima kasih.

Tags: , , , , ,

Function to return last element of a list in ML

1 May

Pada kesempatan kali ini, saya akan menjelaskan fungsi yang dapat kita pakai dalam fungsional programming menggunakan Meta Language atau ML. Fungsi ini berfungsi untuk mengembalikan elemen terakhir dari sebuah list. Berikut fungsinya:

fun lastElement [] = raise Empty
   |lastElement [x] = x
   |lastElement (_::xs) = lastElement xs;

Fungsi di atas adalah fungsi yang diharapkan karena akan memaksimumkan penggunaan pattern matching.

Perhatikan bahwa [x] ekuivalen dengan x::[].

Empty merupakan exception standar yang berguna untuk menandakan bahwa tidak ada elemen dalam list, yang juga digunakan oleh fungsi built-in hd dan tl. Boleh juga membuat exception sendiri.

Selain fungsi di atas, kita juga dapat membuat sebuah fungsi lain seperti di bawah ini yang memiliki fungsi yang sama, yaitu untuk mengembalikan elemen terakhir pada sebuah list:

fun lastElement [] = raise Empty
   |lastElement (x::xs) = if null xs then x else lastElement xs;

Perhatikan bahwa null xs ekuivalen dengan xs = [] atau xs = nil.

Okay, cukup sekian pembahasan fungsi untuk me-return atau mengembalikan last element dari sebuah list di functional programming menggunakan Meta Language atau ML. Semoga dapat membantu semuanya…

Tags: , , , , ,