Discussion :

[SpiceGuid]

Bonjour,

J'ai lu Nested Datatypes et je suis loin d'avoir tout assimilé.
Pourtant je ne suis pas très ambitieux, je me contenterais bien d'écrire quelques fonctions même élémentaires pour 'a nest et 'a bush.
Pour 'a nest j'y arrive assez bien, avec peu de mérite personnel puisque j'ai été aidé par Okasaki (Purely functional data structures).
Ça donne à peu près ça :

Code OCaml :

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
type 'a nest =
   | Nil
   | Cons of 'a * ('a * 'a) nest
 
let rec size : 'a . 'a nest -> int = function
   | Nil -> 0
   | Cons(_,t) -> 1 + 2 * size t
 
(* utility function *)
let map_pair f (x,y) = (f x,f y)
 
let rec map : 'a 'b . ('a -> 'b) -> 'a nest -> 'b nest = 
   fun f -> function
   | Nil -> Nil
   | Cons(h,t) -> Cons(f h,map (map_pair f) t)
 
let rec nth : 'a . int -> 'a nest -> 'a =
   fun n -> function
   | Nil -> failwith "nest lookup"
   | Cons(h,t) ->
         if n=0 then h else 
         let x,y = nth (n/2) t in
         if n mod 2 = 0 then x else y

Là où ça coince c'est pour le type 'a bush, je voudrais bien définir size , map, nth pour ce type.
Pour l'instant je n'arrive qu'à ébaucher un squelette de map par analogie avec le cas de 'a nest.
J'ai tenté (en vain) plusieurs map_bush sans succès.

Code OCaml :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type 'a bush =
   | Nil
   | Cons of 'a * ('a bush) bush
 
(* utility function *)
let rec map_bush : 'a 'b . ('a -> 'b) -> 'a bush -> 'b bush =
   fun f -> function
   | Nil -> Nil
   | Cons(h,t) -> ???  
 
let rec map : 'a 'b . ('a -> 'b) -> 'a bush -> 'b bush = 
   fun f -> function
   | Nil -> Nil
   | Cons(h,t) -> Cons(f h,map (map_bush f) t)

[cvanaret]

Hop, le lien correct vers le papier.

[SpiceGuid]

à rks`, qui nous propose :

Code OCaml :

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

1
2
3
4
let rec map : 'a 'b. ('a -> 'b) -> 'a bush -> 'b bush =
  fun f -> function
  | Nil -> Nil
  | Cons(h, t) -> Cons(f h,map (map f) t)

Par contre on s'accorde à admettre que cette version de size est trop naïve :

Code OCaml :

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

1
2
3
let rec size : 'a . 'a bush -> int = function
  | Nil -> 0
  | Cons(_,t) -> 1 + size t

Donc on fait du sur-place pour size et nth. Certains vont jusqu'à mettre en doute le fait que 'a bush est un authentique conteneur. Alors que moi j'en suis intimement convaincu. Ça n'est pas forcément un conteneur utile mais ça stocke des données, indéniablement.