* Multi-Index Container
@ 2005-12-01 22:42 Mako Tagliere
2005-12-02 0:19 ` [Caml-list] " skaller
2005-12-02 0:53 ` Jon Harrop
0 siblings, 2 replies; 4+ messages in thread
From: Mako Tagliere @ 2005-12-01 22:42 UTC (permalink / raw)
To: caml-list
Hi,
My colleagues and I often debate the relative merits of OCaml and C++.
After I tell them how expressive, fast, and all-around nifty OCaml is
("see! the debugger works backwards in time!"), they reply "yeah but
C++ has STL and Boost library, which make C++ every bit as expressive as
OCaml." When we repeated this debate recently, they challenged me to
show them an implementation of Boost's multi-index container
(http://www.boost.org/libs/multi_index/doc/index.html) in OCaml. A
bit of searching did not reveal an existing OCaml implementation.
Would someone in the OCaml community be willing to sketch out such an
implementation?
Thanks
Mako Tagliere
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [Caml-list] Multi-Index Container
2005-12-01 22:42 Multi-Index Container Mako Tagliere
@ 2005-12-02 0:19 ` skaller
2005-12-02 0:53 ` Jon Harrop
1 sibling, 0 replies; 4+ messages in thread
From: skaller @ 2005-12-02 0:19 UTC (permalink / raw)
To: Mako Tagliere; +Cc: caml-list
On Thu, 2005-12-01 at 14:42 -0800, Mako Tagliere wrote:
> Hi,
>
> My colleagues and I often debate the relative merits of OCaml and C++.
> After I tell them how expressive, fast, and all-around nifty OCaml is
> ("see! the debugger works backwards in time!"), they reply "yeah but
> C++ has STL and Boost library, which make C++ every bit as expressive as
> OCaml."
Total Rubbish! Some people will never learn. C++ templates
actually provide a bit more than ML can -- there is some
real functorial polymorphism there. However it isn't
properly structured, and neither is C++ polymorphism,
relying on dependent name lookup as it does.
C++ also doesn't have really basic things like tuples,
variants and first class functions. No, don't point
me at the crap in Boost -- a fine effort for C++
but it just doesn't compare with a real programming
language. Just try implementing a list: in Ocaml one line:
type 'a mylist = Empty | Cons of 'a * 'a mylist
Just try doing THAT with variants and tuples from
the Boost library. :)) Hint -- type recursion
doesn't work with templates. It is possible to do it
but it is VERY hard, it has to be done with open
recursion, which is closed using a partial specialisation.
And if you actually succeed .. hehe .. show me how
to do terse pattern matching like
match somelist with
| Empty -> ...
| Cons (elt, tail) -> ....
There is one, and ONLY one good way to do all this in
C++: using Felix.
> When we repeated this debate recently, they challenged me to
> show them an implementation of Boost's multi-index container
> (http://www.boost.org/libs/multi_index/doc/index.html) in OCaml. A
> bit of searching did not reveal an existing OCaml implementation.
Because Ocaml doesn't generally need it. Just use modules
(to enforce invariants) and multiple data structures,
Ocaml boxes (shares on the heap) the data anyhow.
Ocaml doesn't need multi-indexed containers in general,
they're trivial. It needs the opposite -- some way
of NOT sharing mutable data structures, which is the
default in C++.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [Caml-list] Multi-Index Container
2005-12-01 22:42 Multi-Index Container Mako Tagliere
2005-12-02 0:19 ` [Caml-list] " skaller
@ 2005-12-02 0:53 ` Jon Harrop
1 sibling, 0 replies; 4+ messages in thread
From: Jon Harrop @ 2005-12-02 0:53 UTC (permalink / raw)
To: caml-list
On Thursday 01 December 2005 22:42, Mako Tagliere wrote:
> My colleagues and I often debate the relative merits of OCaml and C++.
> After I tell them how expressive, fast, and all-around nifty OCaml is
> ("see! the debugger works backwards in time!"), they reply "yeah but
> C++ has STL and Boost library, which make C++ every bit as expressive as
> OCaml." When we repeated this debate recently, they challenged me to
> show them an implementation of Boost's multi-index container
> (http://www.boost.org/libs/multi_index/doc/index.html) in OCaml. A
> bit of searching did not reveal an existing OCaml implementation.
>
> Would someone in the OCaml community be willing to sketch out such an
> implementation?
In order to compare different languages meaningfully, you should try to solve
problems by writing independent implementations in different languages.
There is no point in trying to mimic individual features, paradigms or styles
found in other languages, as you suggest. Paul Graham's infamous "accumulator
generator" challenge is a fine example this mistake:
http://www.paulgraham.com/accgen.html
So you should ask your friends to try to come up with a real task with a C++
implementation that benefits from Boost's functionality, and then write your
own implementation in OCaml before comparing the two.
I thought the examples from the page that you cite might have been suitable
but the ones that I have looked at are all trivial in OCaml (and C++).
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists
^ permalink raw reply [flat|nested] 4+ messages in thread
* RE: Multi-index Container
@ 2005-12-02 4:50 Jonathan T Bryant
0 siblings, 0 replies; 4+ messages in thread
From: Jonathan T Bryant @ 2005-12-02 4:50 UTC (permalink / raw)
To: caml-list
[-- Attachment #1: Type: text/plain, Size: 230 bytes --]
How about something like the attached code? Completing the data
structures is left as an exercise for the reader... :)
-----------------------
--Jonathan Bryant
jtbryant@valdosta.edu
AIM: JonBoy3182
OAS AAS LLS
ZG214
[-- Attachment #2: multiSort.ml --]
[-- Type: application/octet-stream, Size: 5415 bytes --]
module Dataset :
sig
type 'a t
val create : unit -> 'a t
val add : 'a t -> 'a -> int
val remove : 'a t -> int -> 'a
val inspect : 'a t -> int -> 'a
val clear : 'a t -> unit
val register_add_observer : 'a t -> (int -> 'a -> unit) -> unit
val unregister_add_observer : 'a t -> (int -> 'a -> unit) -> unit
val register_remove_observer : 'a t -> (int -> 'a -> unit) -> unit
val unregister_remove_observer : 'a t -> (int -> 'a -> unit) -> unit
end = struct
type 'a t = {
mutable data : (int, 'a) Hashtbl.t;
mutable add_observers : (int -> 'a -> unit) list;
mutable remove_observers : (int -> 'a -> unit) list
}
let create () = {
data = Hashtbl.create 29;
add_observers = [];
remove_observers = []
}
let add ds e =
let idx = (Hashtbl.length ds.data) + 1 in
Hashtbl.add ds.data idx e;
List.iter (fun f -> f idx e) ds.add_observers;
idx
let remove ds idx =
let e = Hashtbl.find ds.data idx in
Hashtbl.remove ds.data idx;
List.iter (fun f -> f idx e) ds.remove_observers;
e
let inspect ds idx = Hashtbl.find ds.data idx
let clear ds =
Hashtbl.iter (fun idx -> fun e ->
List.iter (fun f -> f idx e) ds.remove_observers;
Hashtbl.remove ds.data idx
) ds.data
let register_add_observer ds f =
ds.add_observers <- (f::ds.add_observers)
let unregister_add_observer ds f =
ds.add_observers <- List.filter (fun o ->
if f = o
then false
else true) ds.add_observers
let register_remove_observer ds f =
ds.remove_observers <- (f::ds.remove_observers)
let unregister_remove_observer ds f =
ds.remove_observers <- List.filter (fun o ->
if f = o
then false
else true) ds.remove_observers
end
module DSList :
sig
type 'a t
val create : 'a Dataset.t -> 'a t
val cons : 'a t -> 'a -> unit
val hd : 'a t -> 'a
val nth : 'a t -> int -> 'a
val rev : 'a t -> unit
val iter : ('a -> unit) -> 'a t -> unit
val destroy : 'a t -> unit
end = struct
type 'a t = {
data : 'a Dataset.t;
mutable repr : int list
}
let add_listener l idx e =
l.repr <- (idx::l.repr)
let remove_listener l idx e =
l.repr <- (List.filter (fun x -> if x = idx then false else true) l.repr)
let create ds =
let self = { data = ds; repr = [] } in
Dataset.register_add_observer ds (add_listener self);
Dataset.register_remove_observer ds (remove_listener self);
self
let cons l e = let _ = Dataset.add l.data e in ()
let hd l = Dataset.inspect l.data (List.hd l.repr)
let nth l idx = Dataset.inspect l.data (List.nth l.repr idx)
let rev l = l.repr <- (List.rev l.repr)
let iter f l = List.iter (fun idx -> f (Dataset.inspect l.data idx)) l.repr
let destroy l =
Dataset.unregister_add_observer l.data (add_listener l);
Dataset.unregister_remove_observer l.data (remove_listener l)
end
module DSSortedList :
sig
type 'a t
val create : 'a Dataset.t -> 'a t
val cons : 'a t -> 'a -> unit
val hd : 'a t -> 'a
val nth : 'a t -> int -> 'a
val iter : ('a -> unit) -> 'a t -> unit
val destroy : 'a t -> unit
end = struct
type 'a t = {
data : 'a Dataset.t;
mutable repr : int list
}
let add_listener l idx e =
l.repr <- (List.sort (fun x -> fun y ->
compare (Dataset.inspect l.data x) (Dataset.inspect l.data y)
) (idx::l.repr))
let remove_listener l idx e =
l.repr <- (List.filter (fun x -> if x = idx then false else true) l.repr)
let create ds =
let self = { data = ds; repr = [] } in
Dataset.register_add_observer ds (add_listener self);
Dataset.register_remove_observer ds (remove_listener self);
self
let cons l e = let _ = Dataset.add l.data e in ()
let hd l = Dataset.inspect l.data (List.hd l.repr)
let nth l idx = Dataset.inspect l.data (List.nth l.repr idx)
let iter f l = List.iter (fun idx -> f (Dataset.inspect l.data idx)) l.repr
let destroy l =
Dataset.unregister_add_observer l.data (add_listener l);
Dataset.unregister_remove_observer l.data (remove_listener l)
end
let print_ds_list l =
Printf.printf "[ ";
DSList.iter (fun x -> Printf.printf "%s; " x) l;
Printf.printf "]\n"
let print_ds_sorted_list l =
Printf.printf "[ ";
DSSortedList.iter (fun x -> Printf.printf "%s; " x) l;
Printf.printf "]\n"
let test_text = ["four"; "score"; "and"; "seven"; "years"; "ago"; "our";
"fathers"; "brought"; "forth"; "upon"; "this"; "continent"; "a"; "new";
"nation"; "concieved"; "in"; "liberty"; "and"; "dedicated"; "to"; "the";
"proposition"; "that"; "all"; "men"; "are"; "created"; "equal"; "we"; "are";
"now"; "engaged"; "in"; "a"; "great"; "civil"; "war"; "testing"; "whether";
"that"; "nation"; "or"; "any"; "nation"; "so"; "concieved"; "can"; "survive";
"we"; "are"; "met"; "on"; "a"; "great"; "battlefield"; "of"; "that"; "war"]
let () =
let ds = Dataset.create () in
let dsl1 = DSList.create ds in
let dsl2 = DSSortedList.create ds in
Printf.printf "Empty Lists:\n";
print_ds_list dsl1;
print_ds_sorted_list dsl2;
List.iter (fun w ->
DSList.cons dsl1 w;
Printf.printf "Added word \"%s\":\n" w;
print_ds_list dsl1;
print_ds_sorted_list dsl2
) test_text;
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2005-12-02 18:14 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2005-12-01 22:42 Multi-Index Container Mako Tagliere
2005-12-02 0:19 ` [Caml-list] " skaller
2005-12-02 0:53 ` Jon Harrop
2005-12-02 4:50 Multi-index Container Jonathan T Bryant
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).