Commit | Line | Data |
---|---|---|
34e49164 C |
1 | open Common |
2 | ||
3 | (*****************************************************************************) | |
4 | (* Collection *) | |
5 | (*****************************************************************************) | |
6 | (* | |
7 | * The derived classes of collections: | |
8 | * - sequence(next, nth): array, list, stack, queue, and mixed | |
9 | * (fast cons, fast snoc, fast append, cf okasaki) | |
10 | * - set(union): setl, setb, seti, seth | |
11 | * - assoc(find): assocl, mapb, hash, btree, multimap (mais bof, can do | |
12 | * with map of set) | |
13 | * - graph: graph1way, graph2way, graphref, graphmatrix? | |
14 | * | |
15 | * Some features/notes: | |
16 | * - views a la wadler to make it cool (I hate get/set). | |
17 | * - take list in parameters to be able to construct value as is easily | |
18 | * - take the comparaison function in parameters (=> functorial set made cool) | |
19 | * make l [], h [], ... as in perl, and pass the func from pervasive | |
20 | * in oo form (list, ...) | |
21 | * - pure/impure: could put 2 interface, with one that show that inpure | |
22 | * by making the operation return unit, but simpler to have one interface. | |
23 | * - the core method and default method (via virtual classes) | |
24 | * better to use virtual than typeclass, virtual play both roles: | |
25 | * an interface and default code | |
26 | * | |
27 | * - pb binary methods: use tosetb tricks, or via (not safe) Obj.magic. | |
28 | * - array/list are both a sequence _and_ a dictionnary, so are both | |
29 | * a collection(a) and a collection(i,a) at the same time. But cant do that. | |
30 | * So for array, I see it mainly as an assoc => favor assoc, and | |
31 | * for list, I see it mainly as a collection => favor collection | |
32 | * | |
33 | * ??mixins: comparable, iterator, via virtual class in ocaml | |
34 | * ?? kind of haskell class + default value | |
35 | * | |
36 | * ?? persistence, caching, peut prendre en param le type de map qu'il cache, | |
37 | * comme en perl, evite du marshalling kan wrapped = bdb. | |
38 | * | |
39 | * ?? lazy wrapper, how avoid complexity of having to define each time | |
40 | * a hashP, hashC, hashL, hashPCL, ... ? | |
41 | * | |
42 | * ?? I define those classes cos their name are cool, say what is intended to | |
43 | * do with | |
44 | * | |
45 | * todo: cf book on algo, a la rivest/sedgewick | |
46 | * todo: recreate collection hierarchy, inspire smalltalk ? haskell ? merd ? | |
47 | * todo: put a clean sequence (inherit collection) and make array a special | |
48 | * class | |
49 | * todo: make ostack (FIFO), oqueue (LIFO) | |
50 | * | |
51 | * | |
52 | * influences: okasaki, merd (pixel), java classes, smalltalk classes | |
53 | *) | |
54 | ||
55 | (*---------------------------------------------------------------------------*) | |
56 | type ('a, 'b) view = Empty | Cons of 'a * 'b | |
57 | ||
58 | class virtual ['a] ocollection = | |
59 | object(o: 'o) | |
60 | inherit Objet.objet | |
61 | ||
62 | method virtual empty: 'o | |
63 | method virtual add: 'a -> 'o | |
64 | ||
65 | method virtual iter: ('a -> unit) -> unit | |
66 | method virtual view: ('a, 'o) view | |
67 | ||
68 | (* no need virtual, but better to redefine for efficiency *) | |
69 | method virtual del: 'a -> 'o (* can do default with: view+iter *) | |
70 | method virtual mem: 'a -> bool (* can do default with: mem(tolist) *) | |
71 | method virtual null: bool (* can do default with: lenght(tolist)= 0 *) | |
72 | ||
73 | ||
485bce71 C |
74 | method add2: 'a -> unit = fun a -> |
75 | o#add a +> ignore; | |
76 | () | |
77 | ||
78 | ||
34e49164 C |
79 | |
80 | method fold: 'b. ('b -> 'a -> 'b) -> 'b -> 'b = fun f a -> | |
81 | let a = ref a in | |
82 | o#iter (fun e -> a := f !a e); | |
83 | !a | |
84 | ||
85 | method tolist: 'a list = | |
86 | List.rev (o#fold (fun acc e -> e::acc) []) | |
87 | method fromlist: 'a list -> 'o = | |
88 | fun xs -> xs +> List.fold_left (fun o e -> o#add e) o#empty | |
89 | ||
90 | method length: int = | |
91 | (* oldsimple: o#tolist +> List.length *) | |
92 | (* opti: *) | |
93 | let count = ref 0 in | |
94 | o#iter (fun e -> incr count); | |
95 | !count | |
96 | ||
97 | method exists: ('a -> bool) -> bool = fun f -> | |
98 | o#tolist +> List.exists f | |
99 | ||
100 | method filter: ('a -> bool) -> 'o = fun f -> | |
101 | (* iter and call add from empty, or del *) | |
102 | o#tolist +> List.filter f +> o#fromlist | |
103 | ||
104 | (* forall, fold, map *) | |
105 | ||
106 | method getone: 'a = | |
107 | match o#view with Cons (e,tl) -> e | Empty -> failwith "no head" | |
108 | method others: 'o = | |
109 | match o#view with Cons (e,tl) -> tl | Empty -> failwith "no tail" | |
110 | ||
111 | end | |
112 |