The Two.

在王老师办公室上网玩的时候无意间看到了这个：

用Haskell实现的快速排序：

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

好简洁。

[]代表空list，所以第一行的意思就是，如果输入是空列表，输出也是空列表。

x:xs的意思是，一个list，第一个元素是x，剩下的是xs。（我不懂Haskell，我猜这就是lisp里的car/cdr吧）。

++的意思是把各个列表连结成一个大列表。

filter(<x) xs 是从xs中挑出所有小于x的元素组成列表。filter(>=x) xs 同理。

所以，上面这个快速排序实现的第二行的意思就是：组成一个列表，其中，所有小于x的排左边，并且进行快速排序；所有大于等于x的排右边，并且快速排序；x排中间。

另外，附上John Hughes写的为神马函数式编程很重要，晚上读一读。

补充：写了个scheme的实现：

(define (quicksort x)
  (cond
   ((null? x) ‘())
   (else (append
   (quicksort (filter (lambda (y) (< y (car x))) (cdr x)))
   (list (car x))
   (quicksort (filter (lambda (y) (>= y (car x))) (cdr x)))))))

写了第一个Scheme程序。

本来想写个汉诺塔非递归解的实现，但实在没弄明白怎么把规则/状态/操作抽象成纯函数。。慢慢想吧。。

还是递归解最爽，而且用Scheme实现看上去很优雅。。倒不是说我写的有多好，是因为Scheme里面用递归怎么看都漂亮。。

(begin
; MoveUpper means move plate 1 to n from peg a to c with help of b
  (define (MoveUpper n a b c)
    (begin
      (if (equal? n 1)
   (MoveBottom n a c)
   (begin
     (MoveUpper (- n 1) a c b)
     (MoveBottom n a c)
     (MoveUpper (- n 1) b a c)
     )
      )
    ))
; MoveBottom means move the plate n from a to c directly
  (define (MoveBottom n a c)
    (begin
      (display “Move “)
      (display n)
      (display ” from “)
      (display a)
      (display ” to “)
      (display c)
      (newline)
      )
    )
; Move 5 plates from peg 1 to peg 3 with help of peg 2
  (MoveUpper 5 1 2 3)
)

用的是MIT/GNU Scheme

另外，下载了Paul Graham的“On Lisp”，准备读一读。