commons/ocollection.ml

   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
  74   method add2: 'a -> unit = fun a ->
  75     o#add a +> ignore;
  76     ()
  77
  78
  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