ผลต่างระหว่างรุ่นของ "Racket"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 2 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน)
แถว 1: แถว 1:
 
== ภาษา ==
 
== ภาษา ==
 
Racket เป็นลูกหลานหนึ่งของภาษา LISP  อ่านรายละเอียดเพิ่มเติมได้ที่ [http://theory.cpe.ku.ac.th/wiki/images/01204435-lect02-scheme.pdf เอกสาร scheme]
 
Racket เป็นลูกหลานหนึ่งของภาษา LISP  อ่านรายละเอียดเพิ่มเติมได้ที่ [http://theory.cpe.ku.ac.th/wiki/images/01204435-lect02-scheme.pdf เอกสาร scheme]
 +
 +
Racket มี IDE ชื่อ DrRacket สามารถดาว์นโหลดได้ที่[http://racket-lang.org/ เว็บไซต์ของ Racket]
  
 
=== REPL ===
 
=== REPL ===
แถว 45: แถว 47:
 
       a
 
       a
 
       (myadd (inc a) (dec b))))
 
       (myadd (inc a) (dec b))))
 
=== lambda ===
 
  
 
=== list ===
 
=== list ===
'''การใช้ quote (')''' ถ้าใช้เครื่องหมาย single quote (') นำหน้า Racket จะไม่ evaluate list นั้น
+
; การใช้ quote (')
 +
ถ้าใช้เครื่องหมาย single quote (') นำหน้า Racket จะไม่ evaluate วงเล็บนั้น แต่จะสร้าง list แทน
 
<pre>
 
<pre>
 
> (1 2 3 4)
 
> (1 2 3 4)
แถว 63: แถว 64:
 
</pre>
 
</pre>
  
 +
; การใช้ procedure list
 +
โปรดอ่าน[[#procedure เกี่ยวกับ list|procedure เกี่ยวกับ list]]
 +
 +
==== โครงสร้างของ list ====
 +
อันที่จริงแล้ว list มีนิยามว่า
 +
# อาจจะเป็น list ว่าง (<tt>null</tt>)
 +
# อาจจะเป็น pair (ใน racket เรียกว่า <tt>cons</tt> มาจาก '''cons'''truct) ของ ''ข้อมูล'' กับ ''list''
 +
 +
ข้างล่างนี้คือตัวอย่างของโครงสร้างของ list
 +
{| class="wikitable"
 +
|-
 +
! โครงสร้างเต็ม !! รูปแบบโดยใช้ quote
 +
|-
 +
| null || '()
 +
|-
 +
| (cons 1 null) || '(1)
 +
|-
 +
| (cons "a" (cons "b" (cons "c" (cons "z" (cons "" null))))) || '("a" "b" "c" "z" "")
 +
|}
 +
 +
==== procedure เกี่ยวกับ list ====
 +
{| class="wikitable"
 +
|-
 +
! ชื่อ 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 ทั้งหมดในตารางใช้เวลา <math>O(1)</math>
 +
 +
* สังเกตว่าที่ racket สามารถหา rest ได้อย่างรวดเร็ว เนื่องจากโครงสร้างของ list ที่จริงแล้วคือ cons ซ้อนกัน การหา rest อันที่จริงแล้วจึงเป็นเพียงแค่การหาข้อมูลตัวหลังของ cons ตัวนอกสุด
 +
 +
==== การดำเนินการกับ list ====
 
<pre>
 
<pre>
 
(define (mylen lst)
 
(define (mylen lst)
แถว 69: แถว 171:
 
       (+ 1
 
       (+ 1
 
         (mylen (rest lst)))))
 
         (mylen (rest lst)))))
 +
 +
> (mylen '("a" "b" "c" "d"))
 +
4
 
</pre>
 
</pre>
 +
 +
=== lambda ===
  
 
=== local variables: let, let* ===
 
=== local variables: let, let* ===
แถว 80: แถว 187:
 
=== Useful functions ===
 
=== Useful functions ===
  
* null?, list?, equal?
+
* equal?
 
<pre>
 
<pre>
> (null? '(1))
 
#f
 
> (null? '())
 
#t
 
> (list? 1)
 
#f
 
> (list? '(1 2 3))
 
#t
 
> empty
 
'()
 
 
> (equal? '() empty)
 
> (equal? '() empty)
 
#t
 
#t
</pre>
 
 
* first, rest
 
<pre>
 
> (define lst '(1 2 3 4 5))
 
> (first lst)
 
1
 
> (rest lst)
 
'(2 3 4 5)
 
> (first (rest lst))
 
2
 
</pre>
 
 
* list, cons
 
<pre>
 
> (list 1 2 3)
 
'(1 2 3)
 
> (list '(1 2 3) 4 5 6)
 
'((1 2 3) 4 5 6)
 
> (cons 1 '(2 3 4))
 
'(1 2 3 4)
 
> (cons '(1 2) '(3 4 5))
 
'((1 2) 3 4 5)
 
</pre>
 
  
 
== แบบฝึกหัด 1 ==
 
== แบบฝึกหัด 1 ==
แถว 192: แถว 265:
 
             (12 (7 () (9 () ()))
 
             (12 (7 () (9 () ()))
 
                 (15 () ()))))
 
                 (15 () ()))))
 +
</pre>
 +
 +
Accessing value, left child, and right child
 +
<pre>
 +
> (car T)
 +
5
 +
> (first (rest T))
 +
'(3 () (4 () ()))
 +
> (cadr T)
 +
'(3 () (4 () ()))
 +
> (caddr T)
 +
'(12 (7 () (9 () ())) (15 () ()))
 
</pre>
 
</pre>
  
แถว 225: แถว 310:
 
=== functional programming ===
 
=== functional programming ===
 
=== filter, map, fold ===
 
=== filter, map, fold ===
 +
 +
=== Examples ===
 +
==== Quicksort ====
 +
<pre>
 +
(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)))))]))
 +
</pre>
  
 
== แบบฝึกหัด 2 ==
 
== แบบฝึกหัด 2 ==

รุ่นแก้ไขปัจจุบันเมื่อ 23:47, 30 ตุลาคม 2557

ภาษา

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 ทั้งหมดในตารางใช้เวลา

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

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

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

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

lambda

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)]))))

ท่าพื้นฐาน

functional programming

filter, map, fold

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)))))]))

แบบฝึกหัด 2