Оптимизация звонков в 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

Обычный способ использования сП передать результат данного продолжения:

 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 случае вам нужно пройти еще одно продолжение, чтобы иметь дело с результатом от вычисления головы.