Racket

ภาษา

Racket เป็นลูกหลานหนึ่งของภาษา LISP อ่านรายละเอียดเพิ่มเติมได้ที่ เอกสาร scheme

Racket มี IDE ชื่อ DrRacket สามารถดาว์นโหลดได้ที่เว็บไซต์ของ Racket

REPL

ส่วนล่างของจอ จะเป็น read-eval-print-loop คือพิมพ์ expression เข้าไป ระบบจะอ่าน คำนวณแล้วก็พิมพ์คำตอบ เช่น

> 5
5
> (+ 10 5)
15
> "hello"
"hello"
> (substring "hello" 1 3)
"el"
> (+ (* 4 5) 2)
22

ไวยากรณ์พื้นฐานของภาษา Racket คือการเรียกฟังก์ชัน:

(ฟังก์ชัน อาร์กิวเมนท์1 อาร์กิวเมนท์2 ...)

เราจะไม่สามารถเขียนวงเล็บเล่น ๆ ได้เลย เช่น ถ้าสั่ง (5) จะได้ error ดังนี้

> (5)
. . application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 5
  arguments...: [none]

define

ตัวอย่าง

(define (inc x)
  (+ x 1))
(define (dec x)
  (- x 1))
(define (square x)
  (* x x))

if

(define (myadd a b)
  (if (= b 0)
      a
      (myadd (inc a) (dec b))))

list

การใช้ quote (')

ถ้าใช้เครื่องหมาย single quote (') นำหน้า Racket จะไม่ evaluate วงเล็บนั้น แต่จะสร้าง list แทน

> (1 2 3 4)
. . application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 1
  arguments...:
   2
   3
   4
> '(1 2 3 4)
'(1 2 3 4)

การใช้ procedure list

โปรดอ่านprocedure เกี่ยวกับ list

โครงสร้างของ list

อันที่จริงแล้ว list มีนิยามว่า

1. อาจจะเป็น list ว่าง (null)
2. อาจจะเป็น pair (ใน racket เรียกว่า cons มาจาก construct) ของ ข้อมูล กับ list

ข้างล่างนี้คือตัวอย่างของโครงสร้างของ list

โครงสร้างเต็ม	รูปแบบโดยใช้ quote
null	'()
(cons 1 null)	'(1)
(cons "a" (cons "b" (cons "c" (cons "z" (cons "" null)))))	'("a" "b" "c" "z" "")

procedure เกี่ยวกับ list

ชื่อ procedure	คำอธิบาย	ตัวอย่าง
list	สร้าง list -- มีความแตกต่างกับการใช้ quote สร้าง list เล็กน้อย แต่โดยทั่วไปแล้วจะเหมือนกัน ใช้แทนกันได้	> (list 1 2 3) '(1 2 3) > (list) '()
null / empty	สร้าง '() ทั้งสอง procedure นี้เหมือนกันทุกประการ ใช้แทนกันได้	> null '() > empty '()
cons	สร้าง pair	> (cons 1 null) '(1) > (cons 1 '(1 2 3 4)) '(1 1 2 3 4)
list?	ทดสอบว่าเป็น list หรือไม่	> (list? null) #t > (list? '(1 2 3)) #t
null? / empty?	ทดสอบว่าเป็น '() หรือไม่	> (null? null) #t > (null? '(1 2 3)) #f
cons?	ทดสอบว่าเป็น cons -- กล่าวคือ list ที่ไม่ใช่ '() -- หรือไม่	(cons? '()) > #f (cons? '(1)) > #t
first	ดึงข้อมูล (ตัวแรก)	> (first '(1 2 3)) 1 > (first '()) first: contract violation expected: (and/c list? (not/c empty?)) given: '()
rest	ดึง list ของข้อมูลทั้งหมดนอกจากข้อมูลตัวแรก	> (rest '(1 2 3)) '(2 3) > (rest '(1)) '() > (rest '()) rest: contract violation expected: (and/c list? (not/c empty?)) given: '()

procedure ทั้งหมดในตารางใช้เวลา $O(1)$

• สังเกตว่าที่ racket สามารถหา rest ได้อย่างรวดเร็ว เนื่องจากโครงสร้างของ list ที่จริงแล้วคือ cons ซ้อนกัน การหา rest อันที่จริงแล้วจึงเป็นเพียงแค่การหาข้อมูลตัวหลังของ cons ตัวนอกสุด

การดำเนินการกับ list

(define (mylen lst)
  (if (null? lst)
      0
      (+ 1
         (mylen (rest lst)))))

> (mylen '("a" "b" "c" "d"))
4

local variables: let, let*

(define (f x)
  (let ([x1 (+ x 1)]
        [x2 (+ x 2)])
    (+ x1 x2)))

Useful functions

• equal?

> (equal? '() empty)
#t

== แบบฝึกหัด 1 ==
1. mysum
<pre>
> (mysum '(1 2 3))
6

2. mymax

> (mymax '(1 2 3 -1))
3

3. myappend

> (myappend '(1 2 3 4) 100)
'(1 2 3 4 100)

4. myreverse

> (myreverse '(1 2 3 4))
'(4 3 2 1)

5. myconcat

> (myconcat '(1 2 3 4) '(10 20 30))
'(1 2 3 4 10 20 30)

6. myslice

> (myslice '(1 2 3 4 5 6 7) 3 6)
'(4 5 6)

7. myrange

> (myrange 5 10)
'(5 6 7 8 9)

8. mycascade

> (mycascade '(1 2 3 4 5 6))
'(1 (2 (3 (4 (5 (6))))))

9. myflatten

> (myflatten '(1 (2 3) 4 (5 (6 7))))
'(1 2 3 4 5 6 7)

Tail recursion

(define (fact1 n x)
  (if (= n 0)
      x
      (fact1 (- n 1)
             (* n x))))

(define (fact n)
  (fact1 n 1))

Binary search tree

Representing BST

(define T '(5 
            (3 () (4 () ()))
            (12 (7 () (9 () ()))
                (15 () ()))))

Accessing value, left child, and right child

> (car T)
5
> (first (rest T))
'(3 () (4 () ()))
> (cadr T)
'(3 () (4 () ()))
> (caddr T)
'(12 (7 () (9 () ())) (15 () ()))

Seaching (using if)

(define (contains? node val)
  (if (null? node)
      #f
      (let ([nv (car node)]
            [lchild (cadr node)]
            [rchild (caddr node)])
        (if (= val nv)
          #t
          (if (< val nv)
              (contains? lchild val)
              (contains? rchild val))))))

Searching (using cond)

(define (contains? node val)
  (if (null? node)
      #f
      (let ([nv (car node)]
            [lchild (cadr node)]
            [rchild (caddr node)])
        (cond [(= val nv) #t]
              [(< val nv) (contains? lchild val)]
              [else (contains? rchild val)]))))

ท่าพื้นฐาน

Examples

Quicksort

(define (qsort lst)
  (cond
    [(empty? lst) empty]
    [(cons? lst)
      (let ([pivot (first lst)]
            [r (rest lst)])
        (append (qsort (filter (lambda (e) (< e pivot)) r))
                (append (list pivot)
                        (qsort (filter (lambda (e) (>= e pivot)) r)))))]))