Fonction récursive de la queue pour trouver la profondeur d'un arbre en Ocaml

vous pouvez vaguement faire cela en transformant la fonction en CPS (Continuation Passing Style). L'idée est qu'au lieu d'appeler depth left, et puis calculer des choses basées sur ce résultat, vous appelez depth left (fun dleft -> ...), où le second argument est "que pour calculer une fois le résultat (dleft) est disponible".

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)

c'est un truc bien connu qui peut rendre toute fonction tail-recursive. Voilà, c'est tail-rec.

le prochain truc bien connu dans le sac est de "defunctionalize" la CPS résultat. La représentation des continuations ((fun dleft -> ...) parts) en tant que fonctions est soigné, mais vous pouvez vouloir voir à quoi il ressemble en tant que données. Nous remplaçons donc chacune de ces fermetures par un constructeur concret d'un type de données, qui saisit les variables libres utilisées dans celui-ci.

ici nous avons trois fermetures de continuation: (fun dleft -> depth right (fun dright -> k ...)), qui ne réutilise que les variables d'environnement right et k,(fun dright -> ...), qui réutilise k et le résultat maintenant disponible à gauche dleft et (fun d -> d), le calcul initial, qui ne saisit rien.

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

la fonction defunctorisée ressemble à ceci:

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

au Lieu de construire une fonction k et l'appliquer sur les feuilles (k 0), je construis une donnée de type ('a, int) cont, qui doit être plus tard eval de calculer un résultat. eval, quand il reçoit un Kleft, n'est que la fermeture (fun dleft -> ...) était en train de faire, c'est de manière récursive appeler depth sur la droite la sous-arborescence. eval et depth sont mutuellement récursives.

Maintenant, le regard dur à ('a, 'b) cont, qu'est-ce que ce type de données? C'est une liste de!

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 []
;;

Et une liste est une pile. Ce que nous avons ici est en fait une réification (transformation en données) de la pile d'appels de la fonction récursive précédente, avec deux cas différents correspondant aux deux types différents d'appels non-taillec.

notez que la défunctionalisation n'est là que pour le plaisir. En pratique l' CPS version est courte, facile à dériver à la main, plutôt facile à lire, et je recommande de l'utiliser. Les fermetures doivent être attribuées en mémoire, tout comme les éléments de ('a, 'b) cont -- bien que ceux-ci puissent être représentés de manière plus compacte. Je m'en tiendrais à la version CPS à moins qu'il n'y ait de très bonnes raisons de faire quelque chose de plus compliqué.