Tail-rekursive Funktion zu finden, die Tiefe des Baums in Ocaml

Können Sie trivial tun dies durch drehen wird die Funktion in CPS (Continuation-Passing-Style). Die Idee ist, dass anstelle der Berufung depth left, und dann Dinge computing basierend auf diesem Ergebnis, Sie nennen depth left (fun dleft -> ...), wobei das zweite argument ist "was zu berechnen, sobald das Ergebnis (dleft) verfügbar ist".

let depth tree =
  let rec depth tree k = match tree with
    | Leaf x -> k 0
    | Node(_,left,right) ->
      depth left (fun dleft ->
        depth right (fun dright ->
          k (1 + (max dleft dright))))
  in depth tree (fun d -> d)

Dies ist ein bekannter trick, dass kann jede Funktion tail-rekursiv. Voilà, es ist tail-rec.

Den nächsten bekannten trick in der Tasche ist "defunctionalize" die CPS-Ergebnis. Die Darstellung der Fortsetzungen (die (fun dleft -> ...) Teile) als Funktionen ist ordentlich, aber möchten Sie vielleicht, um zu sehen, was es sieht aus wie data. Also ersetzen wir jedes dieser Verschlüsse durch eine konkrete Konstruktor eines Datentyps, wobei die freien Variablen in der it.

Wir haben hier drei Fortsetzung Verschlüsse: (fun dleft -> depth right (fun dright -> k ...)), die nur verwendet die Umgebungsvariablen right und k, (fun dright -> ...), die wiederverwendet k und die jetzt verfügbaren Links führen dleft, und (fun d -> d) die anfängliche Berechnung, dass nicht alles erfassen.

type ('a, 'b) cont =
  | Kleft of 'a tree * ('a, 'b) cont (* right and k *)
  | Kright of 'b * ('a, 'b) cont     (* dleft and k *)
  | Kid

Den defunctorized Funktion sieht wie folgt aus:

let depth tree =
  let rec depth tree k = match tree with
    | Leaf x -> eval k 0
    | Node(_,left,right) ->
      depth left (Kleft(right, k))
  and eval k d = match k with
    | Kleft(right, k) ->
      depth right (Kright(d, k))
    | Kright(dleft, k) ->
      eval k (1 + max d dleft)
    | Kid -> d
  in depth tree Kid
;;

Anstatt eine Funktion k und Ihre Anwendung auf die Blätter (k 0), Baue ich eine Daten-Typ ('a, int) cont werden muss später evaluated zu berechnen, ein Ergebnis. eval, wenn es übergeben bekommt eine Kleft, das tut, was die Schließung (fun dleft -> ...) war zu tun, das ist es rekursiv aufrufen depth auf den rechten Teilbaum. eval und depth sind wechselseitig rekursiv.

Schaue jetzt hart an der ('a, 'b) cont, was ist dieser Datentyp? Es ist eine Liste!

type ('a, 'b) next_item =
  | Kleft of 'a tree
  | Kright of 'b

type ('a, 'b) cont = ('a, 'b) next_item list

let depth tree =
  let rec depth tree k = match tree with
    | Leaf x -> eval k 0
    | Node(_,left,right) ->
      depth left (Kleft(right) :: k)
  and eval k d = match k with
    | Kleft(right) :: k ->
      depth right (Kright(d) :: k)
    | Kright(dleft) :: k ->
      eval k (1 + max d dleft)
    | [] -> d
  in depth tree []
;;

Sowie eine Liste ist ein stack. Was wir hier haben, ist eigentlich eine Materialisierung (transformation in Daten) der call stack des vorherigen rekursiven Funktion, mit der zwei verschiedene Fälle, entsprechend den beiden verschiedenen Arten von nicht-tailrec Anrufe.

Beachten Sie, dass die defunctionalization ist nur zum Vergnügen da. In der Praxis werden die CPS-version ist kurz, leicht zu leiten, die von hand eher leicht zu Lesen, und ich würde empfehlen, es zu benutzen. Verschlüsse muss zugewiesen werden, im Speicher, aber so sind die Elemente der ('a, 'b) cont - wenn auch diejenigen, die vielleicht vertreten werden mehr kompakt`. Ich würde stick auf die CPS-version, es sei denn, es gibt sehr gute Gründe, etwas komplizierter machen.

Es gibt eine ordentliche und eine generische Lösung, die mit fold_tree - und CPS - continuous-passing style:

let fold_tree tree f acc =
  let loop t cont =
    match tree with
    | Leaf -> cont acc
    | Node (x, left, right) ->
      loop left (fun lacc ->
        loop right (fun racc ->
          cont @@ f x lacc racc))
  in loop tree (fun x -> x)

let depth tree = fold_tree tree (fun x dl dr -> 1 + (max dl dr)) 0