Tail Call Optimization in F#

Question

I could really do with some help with tail call optimization in F#. I am trying to parse a tree like structure and perform a calculation on each leaf.

The function I'm having problems with is 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

I attempted to use the continuation approach with the following:

    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.)

But stepping through with the debugger showed the stack growing, any help would be Really appreciated.

possible duplicate of [What is tail-recursion?](http://stackoverflow.com/questions/33923/what-is-tail-recursion) — CoderDennis, Feb 10 '15 at 20:26
If you're using Visual Studio, then by default, tail-call optimization is disabled in Debug mode to give you better stack traces. Try enabling this in project options. — Tomas Petricek, Feb 10 '15 at 20:29

Lee · Accepted Answer · 2015-02-11T09:02:04.743

2

The usual way to use CPS is to pass the result to the given continuation:

        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))))

so in the MultiPrimitive case you need to pass another continuation to deal with the result from calculating the head.

edited Feb 11 '15 at 09:02

answered Feb 10 '15 at 20:22

Lee

142,018
20
234
287

Hi @Lee, Thanks for answering. To get your code to work, I had to add h to calcResult. `| MultiPrimitive (head::tail) -> (calcLength head (fun h -> h + calcLength(MultiPrimitive tail) k))` Is that correct? – Mike Coxeter Feb 11 '15 at 04:58
1

@MikeCoxeter - Sorry about that, the sum should be passed to the continuation - see update. – Lee Feb 11 '15 at 09:03
Hi @Lee, Can this also be solved using the ``Accumulator Pattern``? The need to call ``calcLength`` twice, once for head and once for tail seems to rule out this pattern. – Mike Coxeter Feb 13 '15 at 04:39

Tail Call Optimization in F#

1 Answers1