可计算函数如何编写快速排序

这是新的尝试，我们不妨使用一种语法糖来解释，首先有一门编程语言，它有以下规则
1 + 1
=> 2

[1] + [1]
=> [1 1]

0 + 1
=> 1

[] + [1]
=> [1]

1 true 0
=> 1
1 false 0
=> 2

1 =? 0
=> false

0 =? 0
=> true

[h.t] = [1 2 3 4 5]

h
=> 1

t
=> [2 3 4 5]

compare = [> < >= <=]

[h.t] compare n = [h] (h compare n) [] + (t compare n)
[] compare n = []

[h.t] qst = (t <= h) qst + [h] + ((t > h) qst)
[] qst = []

到这里为止，就定义了一个良好的快速排序，这里是具体的实现。

(define my-list
  (lambda (data)

    (define (qst li)
      (if (= 0 (li 'length))
      (my-list '())
      (
       (
        (qst ((li 't) '<= (li 'h)))
        '+
        (my-list (list (li 'h)))
       )
       '+
       (qst ((li 't) '> (li 'h)))
      )
      )
    )
    
    (define self
      (lambda args
    (define msg (car args))
    (define arg (cdr args))

    (define (add-list res data l2)
      (if (null? data)
          (if (= (l2 'length) 0) (reverse res)
          (add-list (cons (l2 'car) res) '() (l2 'cdr)))
          (add-list (cons (car data) res) (cdr data) l2)))
    
    (define (find-index ini index data)
      (if (null? data) '()
          (if (= ini index) (car data)
              (find-index (+ ini 1) index (cdr data)))))
    (define (mul-vec data B)
      (if (= (length data) (B 'length))
          (if (= (B 'length) 0) 0
          (+ (* (car data) (B 'car)) (mul-vec (cdr data) (B 'cdr))))
          'err))
    (define (add-vec data B)
      (if (= (length data) (B 'length))
          (if (= (B 'length) 0) '()
              (cons (+ (B 'car) (car data)) (add-vec (cdr data) (B 'cdr))))
          'err))
    (define (gen-compare comp)
      (define (prdata data n)
        (if (eq? data '())
        '()
        (if (comp (car data) n)
            (cons (car data) (prdata (cdr data) n))
            (prdata (cdr data) n))))
      prdata)
    
    (define pdata (gen-compare >))
    (define mdata (gen-compare <=))
    
    (cond
     ((eq? msg 'data) data)
     ((eq? msg 'length) (length data))

     ((eq? msg 'qst) (qst self))
     
     ((eq? msg '>) ( my-list (pdata data (car arg))))
     ((eq? msg '<=) ( my-list (mdata data (car arg))))
     
     ((eq? msg '*) (mul-vec data (car arg)))
     ((eq? msg '+=) (my-list (add-vec data (car arg))))
     ((eq? msg '+) ( my-list (add-list '() data (car arg))))
     ((eq? msg 'car) (car data))
     ((eq? msg 'h) (self 'car))
     ((eq? msg 't) (self 'cdr))
     ((eq? msg 'cdr) ( my-list (cdr data)))
     (else (find-index 0 msg data)))))
    
    self
    )
  )

可以这样来使用

(define A (my-list '(1 2 3)))

(A 'data)
=> (1 2 3)

(define B (my-list '(10 2 1)))
(define c (my-list '(3 4 5 6 7)))

((((c '+ A) '+ B) 'qst) 'data)
=> (1 1 2 2 3 3 4 5 6 7 10)

(((A '+ B) '+ (A '+ C)) 'data)
=> (1 2 3 10 2 1 1 2 3 3 4 5 6 7)

这就是使用方法，这个代码可以在mit-scheme上运行，大家有兴趣可以下载来调试一下