วันนี้นั่งเรียนภาษา
Oz ซึ่งเป็น
functional programming ตัวหนึ่ง
เห็นตัวอย่าง function การ insert binary tree
ดูน่าสนใจดี
เพราะ Variable ใน Oz assign ได้ครั้งเดียว
ถ้า assign ซ้ำอีกครั้ง ก็จะเกิด exception
เริ่มที่ definition ก่อน
node ใน binary tree นี้จะประกอบด้วย key กับ value
โดยการจัดเรียบ tree จะใช้วิธีการ compare ค่า key
ถ้าค่า key มีค่าน้อยกว่า ก็จะอยู่ กิ่งซ้าย
ถ้ามากกว่า ก็อยู่ฝั่งขวา
ถ้าเรา insert tree ด้วย key="B" จะได้ tree หน้าตาดังนี้
insert procedure ใน Oz เขียนดังนี้
proc {Insert Key Value TreeIn ?TreeOut}
if TreeIn == nil then TreeOut = tree(Key Value nil nil)
else
local tree(K1 V1 T1 T2) = TreeIn in
if Key == K1 then TreeOut = tree(Key Value T1 T2)
elseif Key < K1 then
local T in
TreeOut = tree(K1 V1 T T2)
{Insert Key Value T1 T}
end
else
local T in
TreeOut = tree(K1 V1 T1 T)
{Insert Key Value T2 T}
end
end
end
end
end?TreeOut ที่บรรทัดบนสุดหมายความว่า
ตัวแปรนี้เป็น output parameter (แสดงว่า return parameter ได้หลายตัว)
tree(key value left right) คือ tuple data type
(คิดว่า implement ข้างใน คงจะเป็น linked-list)
local tree(K1 V1 T1 T2) = TreeInอันนี้คือการ declare variable ที่ชื่อ K1, V1, T1, T2
โดยการเปรียบเทียบ structure ของ LHS (left-hand-size) กับ RHS
ดังนั้นถ้า TreeIn มี value = (pok 1 nil nil)
ค่า K1 ก็จะเท่ากับ pok
V1 ก็จะเท่ากับ 1, ...
ทดลองเขียน scheme ที่ทำแบบนี้บ้าง
(เพราะ scheme ก็เป็น functional programming เหมือนกัน)
(define (make-tree key value left right)
(list 'TREE key value left right))
(define (get-key tree-in)
(cadr tree-in))
(define (get-value tree-in)
(caddr tree-in))
(define (get-left tree-in)
(cadddr tree-in))
(define (get-right tree-in)
(cadddr (cdr tree-in)))
(define (insert-tree key value tree-in)
(if (eq? tree-in '()) (make-tree key value '() '())
(let ((root-key (get-key tree-in))
(root-value (get-value tree-in))
(left-tree (get-left tree-in))
(right-tree (get-right tree-in)))
(cond ((string=? key root-key)
(make-tree key value left-tree right-tree))
((string<? key root-key)
(make-tree root-key root-value
(insert-tree key value left-tree)
right-tree))
(else
(make-tree root-key root-value
left-tree
(insert-tree key value right-tree)))))))
code ยาวกว่าหน่อย เพราะพยายามเขียนแบบสื่อความหมาย
สุดท้ายก็ลอง ruby บ้าง
โดย ruby จะมี method อยู่ 2 แบบ
แบบที่ 1 ชื่อ
insert ใช้วิธีแก้ไข tree structure เลย
ส่วนแบบที่ 2 ชื่อ
insert_immutable ซึ่งเรียนแบบวิธีการ
ที่ Oz กับ Scheme ใช้
class Node
attr_accessor :key, :value, :left, :right
def initialize (key, value, left, right)
@key = key
@value = value
@left = left
@right = right
end
end
def insert (key, value, node)
case
when node.key == key
node.value = value
when node.key > key
if node.left == nil
node.left = Node.new(key, value, nil, nil)
else
insert(key, value, node.left)
end
else
if (node.right == nil)
node.right = Node.new(key, value, nil, nil)
else
insert(key, value, node.right)
end
end
end
def insert_immutable(key, value, node)
case
when node == nil
Node.new(key, value, nil, nil)
when node.key == key
Node.new(key, value, node.left, node.right)
when node.key > key
Node.new(node.key,
node.value,
insert_immutable(key, value, node.left),
node.right)
else
Node.new(node.key,
node.value,
node.left,
insert_immutable(key, value, node.right))
end
end
ruby ไม่ได้เขียนแบบ object แท้
ลองแล้วมันไม่เหมาะกับ immutable style
code มันดูเยิ่นเย้อ
