LISP Practice

Quick-sort


(defmacro for-all (x op xs)
`(remove-if-not #'(lambda (y) (,op y x)) xs))

(defun qsort (nums)
(if (not nums)
()

(let ((x (first nums))
(xs (rest nums)))
(if (eq x nil)
()

(append
(qsort (for-all x < xs))
(list x)
(qsort (for-all x >= xs)))))))


Permutation

(defun remove-first (n nums)
(remove n nums :count 1))

(defun join-sublists (superlist)
(reduce #'(lambda (l1 l2) (append l1 l2)) superlist))

(defun permute-sorted-list (nums perm)
(if (eq nums nil)
(list perm)

(let ((unique-nums (remove-duplicates nums))) (join-sublists
(mapcar (lambda (n)
(permute-sorted-list (remove-first n nums) (append perm (list n))))
unique-nums)))))

(defun permutation (nums)
(permute-sorted-list (sort nums #'<) '()))


LISP 初體驗

原本以為 LISP 只是一個普通的 functional language，所以之前都沒去接觸。但是在看完<<駭客與畫家>>之後，開始對 LISP 產生興趣。

書裡面提到 LISP 擁有許多最近新語言開始導入的 feature，而 LISP 也擁有一些其他語言沒有的功能。像我主要是被 LISP 的 macro 吸引（比 C 的 macro 強大多了。可以先把他想像成是 return 程式碼的 function，而且是在 compile 前先展開。），所以開始看 <<Practical Common Lisp>> 一書。目前為止，大家比較熟悉的語言中，我只有在 Perl 6 裡面看到 (http://en.wikipedia.org/wiki/Perl_6#Macros)。

大部分的人對 LISP 的印象就是一堆噁心的括號，寫個加法都要用 (+ 1 2) 這種前置式來敘述，實在是不符合人類的直覺。而 LISP 整個程式碼都是這樣 -- 由一堆 "list" 所組成。(* (+ 1 2) (+ 3 4)) 有一個 list，第一個元素是 * 這個 "function"，第二、三個是另外兩個 list。類似這樣的語法，在定義 function、if、while 等等都一樣。

但這之前隱含了一件事實：LISP 本身的程式碼，就是一個資料結構! 所以 LISP 的 macro 做的事情就是生出程式碼的資料結構，我覺得這就比 Perl 6 的 macro 那種 template 的方式優雅多了。不過，這個優點是建立在令人卻步的括號海上的...

接下來，po 幾個我的 LISP 練習 XD