ทดลอง Implement Binary Tree Insert with Oz,Scheme,Ruby

วันนี้นั่งเรียนภาษา 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 มันดูเยิ่นเย้อ