Scheme快排

#lang racket
(define (quicksort l)
  (define (divide l base)
    (if (null? l) '( () () () )
        (let ([first (car l)]
              [remain (divide (cdr l) base)])
          (cond
            [(< first base)
             (cons (cons first (car remain)) (cdr remain))]
            [(> first base) (list (car remain) (second remain) (cons first (last remain)))] ;用了second/last之类的racket only语法,换成cdar/cddar也行吧
            [(= first base) (list (car remain) (cons first (second remain)) (last remain))]
            )
          )
        )
    )
  (if (<= (length l) 1)
      l
      (let ([divided-list (divide l (car l))])
        (append (quicksort (car divided-list)) (second divided-list) (quicksort (last divided-list)))
        )
      )
  )

(define (gen-rand-list n)
  (if (= n 0) '()
      (cons (random 1000000) (gen-rand-list (- n 1)))
      )
  )

(define g (gen-rand-list 200000))

(time (length (quicksort g)))  ;解释执行1700ms左右,证明是快排。编译:cpu time: 656 real time: 657 gc time: 278

accumulate

std::accumulate

template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );
//(1)   
template< class InputIt, class T, class BinaryOperation >
T accumulate( InputIt first, InputIt last, T init,
              BinaryOperation op );
//(2)   

异曲同工。。。

sicp ex2.16

给出一个一般性的解释,为什么等价的代数表达式在区间运算中导致不同的计算结果?能设计出一个没有这样缺陷的区间算术包吗?或者不可能做到?

(开学前图书馆摸摸鱼。。。

R1R2/(R1+R2)要想能被规约成1/(1/R1 + 1/R2)相当于:上下都乘了一个R1R2的逆元。。。

可是
区间运算的逆元并不一定存在……
而且也不满足分配律所以更不能构成一个除环……

所以通常的代数运算规律是不能应用于(Range, +, *)上的……

没有缺陷的区间运算……等价于求多元函数的f(x,y,z,...)的最大值和最小值。。。解析解肯定不一定有了……

大概可以用一些数值方法来解决?比如说对于一个函数把内侧所有的Range(例如说x=[1,2], y=[3,4])都取一些离散的点(x=1.23 y=3.88)let然后求解子表达式,最后算出所有奇怪玩意的最小值?)

As to devising an interval-arithmetic package that does not have this shortcoming… As the authors state, "This problem is very difficult". So much so that the IEEE started working on a standard for interval arithmetic back in 2008… and they’re still going as I write this. So, yes, it’s very difficult – and certainly beyond the scope of our current exposure to Scheme at this point in the book!