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情况下，你需要通过另一个继续应对来自计算头部的结果。