F＃中的尾部呼叫優化＃

Question

我真的可以做一些F＃中尾部呼叫優化的幫助。 我想解析一個樹狀結構，並在每一片葉子上進行計算。

我有問題的功能是calcLength

type Location = float * float 
type Radius = float 
type Width = float 
type Angle = float 

type Primitive =  
     | Circle of Location * Radius 
     | Ellipse of Location * Radius * Radius 
     | Square of Location * Width * Angle 
     | MultiPrimitive of Primitive List 

type Primitive with 
    member x.Length = 
     let rec calcLength x = 
      match x with 
      | Circle (_,r)  -> System.Math.PI * r * 2. 
      | Ellipse (_,r1,r2) -> System.Math.PI * 2. * sqrt( (r1 * r1) + (r2 * r2)/2.) 
      | Square (_, w,_) -> w * 4. 
      | MultiPrimitive [] -> 0. 
      | MultiPrimitive (head::tail) -> calcLength (MultiPrimitive tail) + (calcLength head) 

[<Fact>] 
let ``test discriminated unions``() = 
    let pattern = MultiPrimitive(
        [ 
         MultiPrimitive(
          [ 
           MultiPrimitive(
            [ 
            Square((10.,10.), 10., 45.); 
            Circle((3.,7.), 3.); 
            Circle((7.,7.), 3.); 
            Square((5.,2.), 3., 45.); 
            ]); 

          Square((10.,10.), 10., 45.); 
          Circle((3.,7.), 3.); 
          Circle((7.,7.), 3.); 
          Square((5.,2.), 3., 45.); 
          ]); 
         Square((10.,10.), 10., 45.); 
         Circle((3.,7.), 3.); 
         Circle((7.,7.), 3.); 
         Square((5.,2.), 3., 45.); 
        ]) 

    let r = pattern.Length 

我試圖使用延續的辦法有以下：

let rec calcLength x f = 
     match x with 
     | Circle (_,r)  -> f() + System.Math.PI * r * 2. 
     | Ellipse (_,r1,r2) -> f() + System.Math.PI * 2. * sqrt( (r1 * r1) + (r2 * r2)/2.) 
     | Square (_, w,_) -> f() + w * 4. 
     | MultiPrimitive [] -> f() 
     | MultiPrimitive (head::tail) -> calcLength head (fun() -> calcLength(MultiPrimitive tail) f) 

    calcLength x (fun() -> 0.) 

但步進通過與調試器顯示堆棧增長，任何幫助將真的讚賞。

Answer 1

使用CPS的常用方法是將結果傳遞給定的延續：

 let rec calcLength x k = 
      match x with 
      | Circle (_,r)  -> k (System.Math.PI * r * 2.) 
      | Ellipse (_,r1,r2) -> k (System.Math.PI * 2. * sqrt( (r1 * r1) + (r2 * r2)/2.)) 
      | Square (_, w,_) -> k (w * 4.) 
      | MultiPrimitive [] -> k 0. 
      | MultiPrimitive (head::tail) -> (calcLength head (fun h -> calcLength(MultiPrimitive tail) (fun t -> k (h + t)))) 

所以在MultiPrimitive情況下，你需要通過另一個繼續應對來自計算頭部的結果。