So I’ve picked up a new book, Introduction to Algorithms, 3rd ed. and I’ve decided to try implementing some of them as a practice using Scheme, specifically I’m using a vanilla install of Chez Scheme.

(define isort 
    (lambda (l1 l2)
        (cond
            ((null? l1) l2)
            ((null? l2) (isort
                (cdr l1)
                (cons (car l1) l2)))
            ((<= (car l1) (car l2)) 
                (isort
                    (cdr l1)
                    (cons
                        (car l1)
                        l2)))
            ((> (car l1) (car l2))
                (isort
                    (cdr l1)
                    (cons 
                        (car l2) (isort 
                            (cons 
                                (car l1) 
                                '()) 
                            (cdr l2))))))))
(isort '(85 12 59 45 72 51) '())

Now that’s all fine and good, but we need ‘More Power’ as Tim the Toolman Taylor would say. I think it’d be nice if we could pass the function a comparator, so that we could do ascending and descending sorts.

(define isortf 
    (lambda (l1 l2 c1 c2)
        (cond
            ((null? l1) l2)
            ((null? l2) (isort
                (cdr l1)
                (cons (car l1) l2) c1 c2))
            ((apply 
                c1 (list 
                    (car l1) 
                    (car l2))) 
                (isortf
                    (cdr l1)
                    (cons
                        (car l1)
                        l2) 
                    c1 
                    c2))
            ((apply 
                c2 (list 
                    (car l1) (car l2)))
                (isortf
                    (cdr l1)
                    (cons 
                        (car l2) (isortf 
                            (cons 
                                (car l1) 
                                '()) 
                            (cdr l2) 
                            c1
                            c2)) 
                    c1
                    c2)))))

(isort '(3 4 2 1) '())
(isortf '(3 4 2 1) '() >= <)

When you write in Scheme, it all makes perfect sense to you. It looks hand crafted, like a fine old carving. But part of you knows it's probably completely incomprehensible to anyone else.

Oh well. At least I think it's beautiful.