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)
Partager