2007년 여름 캠프에서는 functional language LISP의 한 분파인 Scheme을 가르쳐주고, Scheme의 pure functionality만을 이용해서 프로그램을 짜는 실습을 해보았다. LISP의 설계 당시의 의도를 이해하고자, 모든 data (심지어 프로그램까지도) LIST로 표현할 수 있다는 것에 대해서 실습해보았다.
마지막 프로젝트로는 scheme으로 quick sort를 짜는 것으로 하였고
16명 중 3명이 성공하였다.
최어빈 학생의 코드
;2
(define(attach l1 l2)
(if(null? l1)
l2
(cons (car l1) (attach (cdr l1) l2))))
;4
(define(part l1 l2 p o l)
(if(null? l)
(cons l1 l2)
(if(o (car l) p)
(part (cons (car l) l1) l2 p o (cdr l))
(part l1 (cons (car l) l2) p o (cdr l)))))
(define(partition p o l)
(part null null p o l))
;5
(define(sort o l)
(if(null? l)
l
(let ((temp (partition (car l) o (cdr l))))
(attach (sort o (car temp)) (cons (car l) (sort o (cdr temp)))))))
;Testing
(define list2 (list 1 3 8 5))
list2
(sort < list2)
무난하게 조교의 의도대로 코드를 짰다.
신민석 학생의 코드
(define (attach list1 list2)
(if(null? list1)
list2
(cons (car list1) (attach (cdr list1) list2))))
(define (partition pivot lst op)
(list (p_left pivot lst op) (p_right pivot lst op)))
(define (p_left pivot lst op)
(if(null? lst)
(list )
(if(op (car lst) pivot)
(attach (p_left pivot (cdr lst) op) (list (car lst)))
(p_left pivot (cdr lst) op))))
(define (p_right pivot lst op)
(if(null? lst)
(list )
(if(op (car lst) pivot)
(p_right pivot (cdr lst) op)
(attach (p_right pivot (cdr lst) op) (list (car lst))))))
(define (qsort op)
(lambda (lst) (quick_sort op lst)))
(define (quick_sort op lst)
(if(null? lst)
(list )
(if(null? (cdr lst))
(list (car lst))
(attach (attach (quick_sort op (car (partition (car lst) (cdr lst) op))) (list (car lst))) (quick_sort op (cadr (partition (car lst) (cdr lst) op)))))))
((qsort <) (list 5 4 3 6 7 8))
시간 복잡도 상으로 nlogn 이기는 하지만 파티션 부분에서 약간 비효율적인 부분이 있어 아쉽기는 하다. 그렇다고 해서 못 했다는 것은 아니다. 조교의 의도대로 잘 따라왔다.
김정섭 학생의 코드
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Q u i c k S o r t by LISP ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;push <list> <val>
;리스트 list 끝에 값 val 을 추가한다.
(define (push list1 val)
(if (null? list1)
(cons val null)
(cons (car list1) (push (cdr list1) val))
)
)
;xor <tf1> <tf2>
;진리값 tf1 과 진리값 tf2 의 배타적논리합을 구한다.
(define (xor a b)
(or (and (not a) b) (and (not b) a))
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;apply <func> <list>
;리스트 list 각 원소에 함수 func 적용한다.
(define (apply func list1)
(if (null? list1)
null
(cons (func (car list1)) (apply func (cdr list1)))
)
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;attatch <list1> <list2>
;리스트 list1 과 리스트 list2 를 하나로 합친다(list1 뒤에 list2).
(define (attatch list1 list2)
(if (null? list1)
(if (null? list2)
null
(cons (car list2) (attatch list1 (cdr list2)))
)
(cons (car list1) (attatch (cdr list1) list2))
)
)
(define (attatch2 list1)
(attatch (car list1) (car (cdr list1)))
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;partition <pivot> <list1> <op>
;((A) (B))인 list1 를 돌려준다. 단, A pivot B 의 순서가 연산자 op 를 참으로 한다.
;ex) (partition 3 (list 4 5 1 2 ) <) ((1 2) (4 5))
(define (partition pivot list1 op)
(
list (_p pivot list1 op #f) (_p pivot list1 op #t)
)
)
(define (_p pivot list1 op x)
(
if(null? list1) null (
if (xor (eval (list op (car list1) pivot)) x)
(push (_p pivot (cdr list1) op x) (car list1))
(_p pivot (cdr list1) op x)
)
)
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;qsort <op>
(define (qsort op)
(lambda (A)
(if (or (null? A) (null? (cdr A)))
A
( attatch2 (apply (qsort op) (partition (car A) A op)) )
)
)
)
((qsort <) (list 4 49 494 94 394 34 20 30 40293 402 4023 40294 09 5 1 2))
quick sort를 짠 세 학생 중에 가장 코드가 간결하고 이해하기 쉽다. 비록 여러 함수를 정의 해서 썼기 때문에 다른 학생보다 코드가 길기는 하지만, functional language의 장점을 십분 활용했다는 느낌이 든다. 조교가 기대했던 것보다 깔끔하게 잘 짜주었다.