Discussion :

[SpiceGuid]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
type tree =
   | Leaf
   | Node of tree * int * tree

Je voudrais une fonction swap x y t qui, dans l'arbre t, échange le noeud x avec ses descendants de valeur y.

Par exemple à partir de cet arbre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let t = Node(Node(Node(Leaf,7,Leaf),1,Node(Leaf,4,Leaf)),
        5,
        Node(Node(Leaf,6,Leaf),3,Node(Leaf,2,Leaf)));;
 
swap 5 6 t;;

Voici ma fonction swap, mais je la trouve trop naïve car elle copie la totalité de l'arbre.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
let swap x y t =  
   let rec infix1 = function
      | Leaf -> Leaf
      | Node(l,a,r) ->
         if a = x then
            Node(infix2 l,y,infix2 r)
         else
            Node(infix1 l,a,infix1 r)
   and infix2 = function
      | Leaf -> Leaf
      | Node(l,a,r) ->
         Node(infix2 l,(if a = y then x else a),infix2 r)
   in infix1 t;;

Dans mon cas d'utilisation le noeud x n'a toujours qu'un seul descendant de valeur y.
Comment écrire swap x y t de façon a ce qu'elle ne copie qu'un chemin depuis la racine au lieu de la totalité de l'arbre ?

[LLB]

Tu peux renvoyer un booléen en plus qui indique s'il y a eu un changement dans l'arbre.

[LLB]

Plus simplement, tu peux utiliser l'égalité physique pour voir si l'un des deux fils a changé. Si non, tu renvoies l'ancien arbre.

[gasche]

La solution avec égalité physique est astucieuse mais, en un sens, "impure".
J'ai préféré essayer une version explicite :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
let default def = function
  | None -> def
  | Some x -> x
 
 
let change_node l l' a a' r r' = match l', a', r' with
| None, None, None -> None
| _ ->
    Some (Node (default l l', default a a', default r r'))
 
let swap x y t =  
   let rec infix1 = function
      | Leaf -> None
      | Node(l,a,r) ->
          let infix, a' =
            if a = x then infix2, Some y
            else infix1, None in
          change_node l (infix l) a a' r (infix r)
   and infix2 = function
      | Leaf -> None
      | Node(l,a,r) ->
          let a' = if a = y then Some x else None in
          change_node l (infix2 l) a a' r (infix2 r)
   in
   (infix1 t);;

En réalité il faudrait renvoyer (default t (infix1 t)), mais l'exposition de l'option permet de bien tester.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
# test;;
- : tree =
Node (Node (Leaf, 2, Leaf), 5,
 Node (Node (Leaf, 3, Leaf), 4, Node (Leaf, 6, Leaf)))
# swap 5 6 test;;
- : tree option =
Some
 (Node (Node (Leaf, 2, Leaf), 6,
   Node (Node (Leaf, 3, Leaf), 4, Node (Leaf, 5, Leaf))))
# swap 7 7 test;;
- : tree option = None

Mon deuxième test me fait penser qu'on pourrait tester "if x = y then None else ..", mais ce n'est pas bien important.

[SpiceGuid]

Merci à vous deux.
Il ne me reste plus qu'à choisir une solution et à l'adapter à mon cas d'utilisation (ils s'agit d'éditer graphiquement une lambda-expression par tirer-lâcher sur l'arbre de syntaxe abstraite).