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的情况下你需要通过另一个延续来处理计算头部的结果。

F# 中的尾调用优化

Tail Call Optimization in F#

f#

tail-recursion

tail-call-optimization