rust練習之高階過程

在學習rust的過程中，了解了高階函數的知識，說白了就是函數可以作為參數，也可以傳回一個函數，正好最近看到了scip公開課裡面講高階過程這一章，有個求平方根的過程，裡面的lisp實作相當的簡潔優美，基本是對數學公式的形式化書寫。這裡用rust實作一下，看看差別有多大。

主要實作了傳入函數作為參數，并将函數作為傳回值，并以函數式風格實作了平方根求值。

以下是實作過程和具體代碼:

rust中參數的函數類型是以trait來實作的，這樣的trait有三個，分别是FnOnce,FnMut,Fn

• FnOnce

  : 可以調用一次，會轉移執行環境中的值

• FnMut

  : 可變引用可以調用多次，可以改變執行環境中的值. 繼承自FnOnce(所有實作了FnMut的類型也實作了FnOnce).

• Fn

  : 共享引用，可以調用多次.既不可以轉移，也不可以改變執行環境的值. 繼承自FnMut，同樣也繼承自FnOnce

對應的trait定義

pub trait Fn<Args> : FnMut<Args> {
   extern "rust-call" fn call(&self, args: Args) -> Self::Output;
}
pub trait FnMut<Args> : FnOnce<Args> { 
   extern "rust-call" fn call_mut(&mut self, args: Args) -> Self::Output;
}
pub trait FnOnce<Args> { 
   type Output; extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
}
           

牛頓疊代公式

首先實作求導函數，傳入參數類型為函數，并傳回導函數的一階近似，結果是針對原函數的一個計算，依然以函數的形式傳回。因為肯定會多次調用，是以使用Fn，這裡傳入和傳回的函數都是同一個類型，即

Fn(f64)->f64

，由于傳回值引用了傳入參數，是以需要指定lifetime 'a，以保證傳入參數不會提前失效，并需要Box包裝，以便确定傳回類型的大小。這裡傳回函數是以閉包的形式，由于閉包的lifetime為目前函數，要想傳回這個閉包并且在函數以外調用，需要使用move轉移閉包。

//導函數
const DX: f64 = 0.000001;//微分函數的分母，盡可能的小，但由于浮點數的精度限制，取得太小，反而誤差會擴大
fn deriv<'a, F>(f: &'a F) -> Box<Fn(f64) -> f64 + 'a>
    where F: Fn(f64) -> f64 
{
    Box::new(move |x| (f(x + DX) - f(x - DX)) / (2.0 * DX))
}
           

牛頓疊代法的實作，調用了上面實作的導函數

//牛頓疊代法近似
fn newton<'a, F>(f: &'a F) -> Box<Fn(f64) -> f64 + 'a>
    where F: Fn(f64) -> f64 
{
    Box::new(move |x| x - (f(x) / deriv(f)(x)))

}
           

通過不動點算法，用牛頓疊代函數逼近所求的值，當誤差小于某個值的時候，傳回結果。這裡的trans函數是針對函數fnt的疊代函數，是以其類型為函數，其輸入參數也為函數，對應的trait：

Fn(&'a F) -> Box<Fn(f64) -> f64 + 'a>

//函數不動點逼近
fn fixed_point<'a, F, T>(fnt: &'a F, trans: T, first_guess: f64) -> f64
    where F: Fn(f64) -> f64,
          T: Fn(&'a F) -> Box<Fn(f64) -> f64 + 'a> 
{
    let tolerance = 0.0000001;
    let close_enough = |a: f64, b: f64| (a - b).abs() > tolerance;
    let f = trans(fnt);
    let mut guess = first_guess;
    let mut next: f64 = f(guess);
    while close_enough(guess, next) {
        // println!("guess next:{}", next);
        guess = next;
        next = f(next);
    }
    next
}
           

求平方根函數，即y2=x，對應y既為x的平方根，對于函數y2-x應用牛頓疊代函數，使用不動點函數進行計算。

fn sqrt(x: f64) -> f64 {

    let func = |y: f64| y.powi(2) - x;
    fixed_point(&func, newton, 1.0)
}
           

測試結果

fn main() {
    let x = 2.0;
    let func = |y: f64| y.powi(2) - x;
    let dx = deriv(&func);
    println!(" derivative y^2-x:{}", dx(1.0));
    let y = newton;
    let nt = y(&func);
    println!("newton method:{}", nt(1.4142));
    let val = fixed_point(&func, newton, 1.0);
    println!("fixed point,sqrt:{}", val);
    let x = 3.0;
    println!("sqrt(x):{}={}", x, sqrt(x));
}
           

可以看到和lisp比起來，rust實作這種函數式程式設計，還是很别扭，沒有lisp那麼直覺，不過也足夠簡潔了，閉包還是很強大的。

實際上，如果隻是簡單的這種方法求平方根，過程式方法一樣可以實作。這裡最重要的是fixed_point實作了一種求不動點的通用算法，參數裡的fnt和trans函數可以有很多中不同的實作，比如平方根求值，可以用牛頓疊代法的二次逼近，也可以用線性疊代的一次逼近。而依據函數不動點定理，可以對很多不同的函數求解。隻需要實作其函數式，并代入到fixed_point函數即可。實際上是一種函數式抽象。

附注：對應的lisp實作

來源：

SICP Higher-Order Procedures

(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

(define (newton-transform g)  
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

(define tolerance 0.00001)
(define (fixed-point f first-guess) 
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (fixed-point-of-transform g transform guess) 
    (fixed-point (transform g) guess))

(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (- (square y) x))
                            newton-transform
                            1.0))