Sorted list

Sorted list

[tmp123]

Hello,

In order to implement a timers subsystem, I need a module with the 
following values:

*) add_timer : time -> ( unit -> unit ) -> timerid,
for public usage, where "add_timer t f" means execute "f" at time "t".  
The result is an identifier who allows cancelation of the timer.
*) cancel_timer: timerid -> unit
for public usage, cancel a previously added timer
*) peek_minimum_timer : unit -> ( time, unit -> unit )
for internal usage, get the timer with minimum time. Returns the time 
and the related function.
*) remove_minimum_timer : ?? -> unit
for internal usage, remove the timer with the minimum time. It will be 
called after execute a timer.

Thus, in a generic sense, what I need is a "sorted list", with easy 
insertion of elements, and peek/pop of the head (minimum).

Of the standard modules, the most similar seems "set", because allows 
insertion and has the funcion "min_elt". However, the problem is, if two 
timers have the same time, addition of the second one removes the first.

Please, has someone any sugestion?

Thanks a lot.

Re: [Caml-list] Sorted list

[Jon Harrop]

On Saturday 04 August 2007 10:35:23 tmp123@menta.net wrote:
> Please, has someone any sugestion?

Sounds like you want a multiset. There are several implementations out there. 
The first one on Google is this:

  http://lamp.epfl.ch/~sbriais/caml/multiset.tgz

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

Re: [Caml-list] Sorted list

[Philippe Wang]

tmp123@menta.net wrote:
> Hello,
>
> In order to implement a timers subsystem, I need a module with the 
> following values:
>
> *) add_timer : time -> ( unit -> unit ) -> timerid,
> for public usage, where "add_timer t f" means execute "f" at time 
> "t".  The result is an identifier who allows cancelation of the timer.
> *) cancel_timer: timerid -> unit
> for public usage, cancel a previously added timer
> *) peek_minimum_timer : unit -> ( time, unit -> unit )
> for internal usage, get the timer with minimum time. Returns the time 
> and the related function.
> *) remove_minimum_timer : ?? -> unit
> for internal usage, remove the timer with the minimum time. It will be 
> called after execute a timer.
>
> Thus, in a generic sense, what I need is a "sorted list", with easy 
> insertion of elements, and peek/pop of the head (minimum).
>
> Of the standard modules, the most similar seems "set", because allows 
> insertion and has the funcion "min_elt". However, the problem is, if 
> two timers have the same time, addition of the second one removes the 
> first.
>
> Please, has someone any sugestion?
>
> Thanks a lot.
Hello,

Let's remind that Set.Make is a functor that takes a module with
sig
  type t
  val compare : t -> t -> int
end

If you simply give him a compare function that never returns 0, then you 
can add multiple elements that are the same.

Cheers,

--
Philippe Wang
  mail[at]philippewang.info

Re: [Caml-list] Sorted list

[skaller]

On Sat, 2007-08-04 at 12:29 +0200, Philippe Wang wrote:
> tmp123@menta.net wrote:

> > Of the standard modules, the most similar seems "set", because allows 
> > insertion and has the funcion "min_elt". However, the problem is, if 
> > two timers have the same time, addition of the second one removes the 
> > first.
> >
> > Please, has someone any sugestion?
> >
> > Thanks a lot.
> Hello,
> 
> Let's remind that Set.Make is a functor that takes a module with
> sig
>   type t
>   val compare : t -> t -> int
> end
> 
> If you simply give him a compare function that never returns 0, then you 
> can add multiple elements that are the same.

You cannot do that! compare function must be a total order.

You must keep a list of functions to fire off at a given time,
so the map will be

	time -> timerid list

and you'll also need timerid -> time * (unit->unit) to fetch the
function from the id.

If you want "high performance" interrupt handling then you
should also:

(A) put close timers into the same list

(B) before returning from the interrupt,check to see
if there is another function to execute at a time less
than NOW + some constant.

Given those requirements a good data structure is not
so easy to find. A list is probably the best, assuming
interrupt performance is more important than inserting
and deleting timers.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Sorted list

[Brian Hurt]

On Sat, 4 Aug 2007, tmp123@menta.net wrote:

> Hello,
>
> In order to implement a timers subsystem, I need a module with the following 
> values:
>
> *) add_timer : time -> ( unit -> unit ) -> timerid,
> for public usage, where "add_timer t f" means execute "f" at time "t".  The 
> result is an identifier who allows cancelation of the timer.
> *) cancel_timer: timerid -> unit
> for public usage, cancel a previously added timer
> *) peek_minimum_timer : unit -> ( time, unit -> unit )
> for internal usage, get the timer with minimum time. Returns the time and the 
> related function.
> *) remove_minimum_timer : ?? -> unit
> for internal usage, remove the timer with the minimum time. It will be called 
> after execute a timer.
>
> Thus, in a generic sense, what I need is a "sorted list", with easy insertion 
> of elements, and peek/pop of the head (minimum).
>
> Of the standard modules, the most similar seems "set", because allows 
> insertion and has the funcion "min_elt". However, the problem is, if two 
> timers have the same time, addition of the second one removes the first.
>
> Please, has someone any sugestion?

What you want is a priority queue.

Here's a simple one: a leftist priority queue.  The core operation is 
join, which takes two priority queues and joins them together:

module type Req = sig
 	type t
 	val compare : t -> t -> int
end

module Make(Ord: Req) = struct

type elem = Ord.t;;

type t =
 	| Node of int * t * Ord.t * t
 	| Empty
;;

let height = function
 	| Empty -> 0
 	| Node(h, _, _, _) -> h
;;

let join p q =
 	match p, q with
 	| Empty, Empty -> Empty
 	| Empty, _ -> q
 	| _, Empty -> p
 	| Node(_, pl, px, pr), Node(_, ql, qx, qr) ->
 		let x, l, m, r =
 			if (Ord.compare px qx) <= 0 then
 				px, pl, pr, q
 			else
 				qx, p ql, qr
 		in
 		(* pick the tallest of l, m, and r to be the new left
 		 * node.  The new right node is the join of the remaining
 		 * two nodes.
 		 *)
 		let left, right =
 			if (height l) >= (height m) then
 				if (height l) >= (height r) then
 					l, (join m r)
 				else
 					r, (join l m)
 			else
 				if (height m) >= (height r) then
 					m, (join l r)
 				else
 					r, (join l m)
 		in
 		let h = 1 + (max (height left) (height right)) in
 		Node(h, left, x, right)
;;

let empty = Empty;;

let singelton x = Node(1, Empty, x, Empty);;

let is_empty = function
 	| Empty -> true
 	| Node(_, _, _, _) -> false
;;

let get_head = function
 	| Empty -> invalid_arg "head on empty priority queue!"
 	| Node(_, _, x, _) -> x
;;

let remove_head = function
 	| Empty -> invalid_arg "remove_head on empty priority queue!"
 	| Node(_, l, _, r) -> join l r
;;

let add q x =
 	let p = singleton x in
 	join q p
;;

let rec filter f = function
 	| Empty -> Empty
 	| Node(_, l, x, r) ->
 		if f x then
 			join (join (filter l) (singleton x)) (filter r)
 		else
 			join (filter l) (filter r)
;;

The one problem with this is that filter is O(N log N).  I'd probably just 
add a bit of mutable data to the timer structure, a boolean flag to say 
wether it's been deleted our not.  Then, when you remove the head node, 
you keep removing the head node while it's been deleted (i.e. a deleted 
node doesn't get removed until it times out).  If the number of deleted 
nodes reaches some sufficiently high percentage, you can then afford to 
filter the whole table and delete all of them at once.

Brian

Re: [Caml-list] Sorted list

[Daniel Bünzli]

Le 4 août 07 à 11:35, tmp123@menta.net a écrit :

> Please, has someone any sugestion?

I once did that by using a leftist heap. Your abstract timerid can  
have a mutable field that indicates if it was cancelled. When you  
peek/pop for the minimal one do it until you get on a timer that was  
not cancellled.

Daniel

P.S. You can use the following code for the heap. Public domain no  
license, no copyright.

(* A leftist heap data structure. *)
module Heap = struct
   type priority = float
   type 'a t =
     | Empty
     | Node of 'a t * int * priority * 'a * 'a t

   let rank = function
     | Empty -> 0
     | Node (_, r, _, _, _) -> r

   let make_node p v h h' =
     let r = rank h in
     let r' = rank h' in
     if r >= r' then Node(h, r' + 1, p, v, h')
     else Node(h', r + 1, p, v, h)

   let rec merge h h' = match h, h' with
   | h, Empty -> h
   | Empty, h -> h'
   | Node(a, _, p, v, b), Node (a', _, p', v', b') ->
       if p <= p' then make_node p v a (merge b h')
       else make_node p' v' a' (merge b' h)

   let empty = Empty

   let is_empty = function
     | Empty -> true
     | _ -> false

   let add h p v = merge (Node(Empty, 1, p, v, Empty)) h

   let min = function
     | Empty -> raise Not_found
     | Node(_, _, p, v, _) -> p, v

   let remove_min = function
     | Empty -> raise Not_found
     | Node(a, _, _, _, b) -> merge a b
end

Re: [Caml-list] Sorted list

[Philippe Wang]

skaller wrote:
> On Sat, 2007-08-04 at 12:29 +0200, Philippe Wang wrote:
>   
>> tmp123@menta.net wrote:
>>     
>
>   
>>> Of the standard modules, the most similar seems "set", because allows 
>>> insertion and has the funcion "min_elt". However, the problem is, if 
>>> two timers have the same time, addition of the second one removes the 
>>> first.
>>>
>>> Please, has someone any sugestion?
>>>
>>> Thanks a lot.
>>>       
>> Hello,
>>
>> Let's remind that Set.Make is a functor that takes a module with
>> sig
>>   type t
>>   val compare : t -> t -> int
>> end
>>
>> If you simply give him a compare function that never returns 0, then you 
>> can add multiple elements that are the same.
>>     
>
> You cannot do that! compare function must be a total order.
>   
Why not ?



        Objective Caml version 3.10.0

# include Set.Make(struct type t = int let compare : t -> t -> int = fun 
a b -> match compare a b with 0 -> 1 | n -> n end);;
type elt = int
type t
val empty : t = <abstr>
val is_empty : t -> bool = <fun>
val mem : elt -> t -> bool = <fun>
val add : elt -> t -> t = <fun>
val singleton : elt -> t = <fun>
val remove : elt -> t -> t = <fun>
val union : t -> t -> t = <fun>
val inter : t -> t -> t = <fun>
val diff : t -> t -> t = <fun>
val compare : t -> t -> int = <fun>
val equal : t -> t -> bool = <fun>
val subset : t -> t -> bool = <fun>
val iter : (elt -> unit) -> t -> unit = <fun>
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a = <fun>
val for_all : (elt -> bool) -> t -> bool = <fun>
val exists : (elt -> bool) -> t -> bool = <fun>
val filter : (elt -> bool) -> t -> t = <fun>
val partition : (elt -> bool) -> t -> t * t = <fun>
val cardinal : t -> int = <fun>
val elements : t -> elt list = <fun>
val min_elt : t -> elt = <fun>
val max_elt : t -> elt = <fun>
val choose : t -> elt = <fun>
val split : elt -> t -> t * bool * t = <fun>

# let x = empty ;;
val x : t = <abstr>
# let x = add 1 x ;;
val x : t = <abstr>
# let x = add 1 x ;;
val x : t = <abstr>
# let x = add 1 x ;;
val x : t = <abstr>
# let x = add 42 x ;;
val x : t = <abstr>
# let x = add 45 x ;;
val x : t = <abstr>
# elements x ;;
- : elt list = [1; 1; 1; 42; 45]

It works ! ... Or did I miss something ?

Re: [Caml-list] Sorted list

[Brian Hurt]

I forgot a bit of analysis as to why I recommend that data structure, and 
not others.  The advantage a priority queue has is that peeking at the 
head node (highest priority) element is O(1), and in this case very fast. 
This is in comparison with the O(log N) cost of using a map or tree-based 
list.  I was assuming that since you were implementing a timer queue, the 
bulk of the accesses will be "has the next timer timed out yet?  No- 
moving on..."

You can implement a mutable version of the leftist heap, and keep a parent 
pointer in the node.  This allows you to remove an arbitrary node in O(log 
N) time, during the delete function (as opposed to waiting for the timer 
to time out to remove it).  But it's a lot more complicated- the idea is 
easier to see in the purely functional code.

If you want to use a map, have each element be a list of timers set to 
expire at the same time.

Brian

Re: [Caml-list] Sorted list

[Oliver Bandel]

Hello,

do you have no real name?


Zitat von tmp123@menta.net:
[...]
>
> Of the standard modules, the most similar seems "set", because allows
> insertion and has the funcion "min_elt". However, the problem is, if two
> timers have the same time, addition of the second one removes the first.
>
> Please, has someone any sugestion?
>
[...]


You can make the type of the Set a pair,
with the time and the timerid (if it is created in
ascending order) as it's elements.

Then you can compare the time and the id.
Ocaml makes this for you easy:


========================================================

oliver@siouxsie2:~$ ocaml
        Objective Caml version 3.09.2

# let pl = [("12:17:22", 20); ("13:44:23", 3); ("12:17:22", 2);
  ("12:17:22",1); ("12:17:22",12)];;
val pl : (string * int) list =
  [("12:17:22", 20); ("13:44:23", 3); ("12:17:22", 2); ("12:17:22", 1);
   ("12:17:22", 12)]
# List.sort compare pl;;
- : (string * int) list =
[("12:17:22", 1); ("12:17:22", 2); ("12:17:22", 12); ("12:17:22", 20);
 ("13:44:23", 3)]
#
========================================================

So, a simple compare would also work for your Set.

Ciao,

Re: [Caml-list] Sorted list

[skaller]

On Sat, 2007-08-04 at 14:23 +0200, Philippe Wang wrote:
> skaller wrote:
> > On Sat, 2007-08-04 at 12:29 +0200, Philippe Wang wrote:
> >   

> > You cannot do that! compare function must be a total order.
> >   
> Why not ?

> It works ! ... Or did I miss something ?

Yes. Read the manual: the ordered type mandates a total order.

Just because the Ocaml type system is too weak too represent this
constraint does not remove your obligation to meet it.

Whether or not it happens to work with the current implementation
isn't relevant.  

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Sorted list

[skaller]

On Sat, 2007-08-04 at 08:36 -0400, Brian Hurt wrote:
> I forgot a bit of analysis as to why I recommend that data structure, and 
> not others.  

The priority queue here is a good data structure for 
amortising performance. A plain list is better if the interrupt
handling is time critical (whilst the inserts and deletes are not).

However, your threading model matters a lot here.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Sorted list

[Philippe Wang]

skaller wrote:
>  
>> It works ! ... Or did I miss something ?
>>     
>
> Yes. Read the manual: the ordered type mandates a total order.
>
> Just because the Ocaml type system is too weak too represent this
> constraint does not remove your obligation to meet it.
>
> Whether or not it happens to work with the current implementation
> isn't relevant.  
>
>   

Ok...
Still, using the current implementation (even if it means making a 
copy!) should be an efficient solution!

:-)

Re: [Caml-list] Sorted list

[tmp123]

Philippe Wang wrote:

> skaller wrote:
>
>> On Sat, 2007-08-04 at 12:29 +0200, Philippe Wang wrote:
>>  
>>
>>> tmp123@menta.net wrote:
>>>    
>>
>>
>>  
>>
>>>> Of the standard modules, the most similar seems "set", because 
>>>> allows insertion and has the funcion "min_elt". However, the 
>>>> problem is, if two timers have the same time, addition of the 
>>>> second one removes the first.
>>>>
>>>>       
>>>
>>> Hello,
>>>
>>> Let's remind that Set.Make is a functor that takes a module with
>>> sig
>>>   type t
>>>   val compare : t -> t -> int
>>> end
>>>
>>> If you simply give him a compare function that never returns 0, then 
>>> you can add multiple elements that are the same.
>>>     
>>
>>
>> You cannot do that! compare function must be a total order.
>>   
>
> Why not ?
>
>

Hello,

Thanks for your help.

The problem with this option seems to be in the deletion of the set 
elements. It is not posible to use "Set.remove", because the compare 
function never returns "equal".

Kind regards.

Re: [Caml-list] Sorted list

[tmp123]

[-- Attachment #1: Type: text/html, Size: 1746 bytes --]

Re: [Caml-list] Sorted list

[skaller]

On Sat, 2007-08-04 at 16:01 +0200, Philippe Wang wrote:
> skaller wrote:
> >  
> >> It works ! ... Or did I miss something ?
> >>     
> >
> > Yes. Read the manual: the ordered type mandates a total order.
> >
> > Just because the Ocaml type system is too weak too represent this
> > constraint does not remove your obligation to meet it.
> >
> > Whether or not it happens to work with the current implementation
> > isn't relevant.  
> >
> >   
> 
> Ok...
> Still, using the current implementation (even if it means making a 
> copy!) should be an efficient solution!

You don't know it works, just because 3 lines of tests worked.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Sorted list

[Brian Hurt]

On Sat, 4 Aug 2007, tmp123@menta.net wrote:

> skaller wrote:
>
>  On Sat, 2007-08-04 at 12:29 +0200, Philippe Wang wrote:
> 
>
>  tmp123@menta.net wrote:
> 
>
>  Of the standard modules, the most similar seems "set", because allows 
> insertion and has the funcion "min_elt". However, the problem is, if 
> two timers have the same time, addition of the second one removes the 
> first.
> 
> Please, has someone any sugestion?

Neither set nor map gives you the semantics you need.

Map is probably closer, but it doesn't give you the find minimal element.

Unortunately, the standard Ocaml solution in a situation like this is to 
implement your own data structure.  The good news is that this is easy. 
The bad news is that, because this is easy, there is little pressure on 
the maintainers of Ocaml to add features to the core library.

Brian

Re: [Caml-list] Sorted list

[tmp123]

[-- Attachment #1: Type: text/html, Size: 1746 bytes --]

Re: [Caml-list] Sorted list

[skaller]

On Sat, 2007-08-04 at 16:37 +0200, tmp123@menta.net wrote:

> It seems dificult to generate an unique identifier, for this subject
> or any other (in this sense, I feel nostalgic of the old C pointers). 
> 
> An integer counter could be valid, but, when the counter reaches the
> maximum, the counter needs to return to "0". From now on, before to
> return a new identifier, it should be checked if this value is already
> in use. And that means O(n).
> 
> I do not see solution for that.

Use the date + time + fresh integer modulo something big enough
you know the if the CPU count that fast, your timer queue runs out
of memory .. :)

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Sorted list

[skaller]

On Sat, 2007-08-04 at 11:09 -0400, Brian Hurt wrote:

> Unortunately, the standard Ocaml solution in a situation like this is to 
> implement your own data structure.  The good news is that this is easy. 
> The bad news is that, because this is easy, there is little pressure on 
> the maintainers of Ocaml to add features to the core library.

Well, I would like to see a community process for selecting,
implementing, documenting and maintaining a set of good algorithms
which go IN THE STANDARD DISTRIBUTION (under the usual LGPL+X licence,
with a disclaimer the code base isn't maintained by Inria, merely
distributed on behalf of the community).

So Inria should provide the repository, and the Ocaml team has
a final veto on selection .. but the work is done by outside
volunteers.

So please would the High Priests of the Cathedral like
to run a little Bazaar for their disciples?

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Sorted list

[Richard Jones]

On Sun, Aug 05, 2007 at 01:42:21AM +1000, skaller wrote:
> On Sat, 2007-08-04 at 11:09 -0400, Brian Hurt wrote:
> 
> > Unortunately, the standard Ocaml solution in a situation like this is to 
> > implement your own data structure.  The good news is that this is easy. 
> > The bad news is that, because this is easy, there is little pressure on 
> > the maintainers of Ocaml to add features to the core library.
> 
> Well, I would like to see a community process for selecting,
> implementing, documenting and maintaining a set of good algorithms
> which go IN THE STANDARD DISTRIBUTION (under the usual LGPL+X licence,
> with a disclaimer the code base isn't maintained by Inria, merely
> distributed on behalf of the community).

But what's wrong with extlib?  Now I know it's not the "Standard"
distribution, but that's a mere packaging issue.

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] Sorted list

[Brian Hurt]

On Sat, 4 Aug 2007, Richard Jones wrote:

> But what's wrong with extlib?  Now I know it's not the "Standard"
> distribution, but that's a mere packaging issue.

Actually, extlib is a wonderfull example of what's wrong with this idea. 
I have grown to have major philosophical differences with extlib- despite 
the fact that I'm one of the major contributors.  For example, I'm much 
more fond of functors at this point (and I understand them better) than I 
did when I first started contributing.  At this point, I also prefer 
purely functional data structures as a default, even at a performance 
penalty- there are damned few places that need to pure speed that 
imperitive data structures give you (there are some, but they're a 
distinct minority)- in the vast majority of places, the performance 
benefits of impertive data structures are vastly outweighed by the 
correctness gaurentees applicative data structures can give you.

Others may disagree (in fact, they do)- that's OK.  I do not want to 
restart the epic arguments that occurred on the extlib list here on the 
main list (please, dear God, no).  My point here is that the Ocaml 
community is much less in agreement on how these core libraries should 
look and act than, say, the C++ or Java communities.  Even if we limit 
ourselves to, say, the Brian Hurts of past and present, the Brian Hurt of 
three years ago would have designed a radically different library than the 
Brian Hurt of a year ago, who in turn would have a different view than the 
Brian Hurt of today (who is learning, and liking, monads).  And God only 
knows what nutzoid radical ideas the Brian Hurt of a year from now, or 
five years from now, will have.

Brian

Re: [Caml-list] Sorted list

[Julien Moutinho]

On Sun, Aug 05, 2007 at 01:42:21AM +1000, skaller wrote:
> On Sat, 2007-08-04 at 11:09 -0400, Brian Hurt wrote:
> 
> > Unortunately, the standard Ocaml solution in a situation like this is to 
> > implement your own data structure.  The good news is that this is easy. 
> > The bad news is that, because this is easy, there is little pressure on 
> > the maintainers of Ocaml to add features to the core library.
> 
> Well, I would like to see a community process for selecting,
> implementing, documenting and maintaining a set of good algorithms
> which go IN THE STANDARD DISTRIBUTION (under the usual LGPL+X licence,
> with a disclaimer the code base isn't maintained by Inria, merely
> distributed on behalf of the community).
> 
> So Inria should provide the repository, and the Ocaml team has
> a final veto on selection .. but the work is done by outside
> volunteers.
I am quite half-hearted about the idea of an Inrians' veto,
despite the fact that, they sure know how to select.
However if this could allow extra-Inrians to actually contribute to
(and learn) the jewelery, in a more _visible_ and _fast_ way,
which is _hardly_ the case currently, why not!  Let us be pragmatic.
That said... do they have enough manpower for such a peer-review task?

> So please would the High Priests of the Cathedral like
> to run a little Bazaar for their disciples?
Yep, Bazaar or another free software with a distributed repository model.

Amen.

Re: [Caml-list] Sorted list

[skaller]

On Sat, 2007-08-04 at 17:21 +0100, Richard Jones wrote:

> > Well, I would like to see a community process for selecting,
> > implementing, documenting and maintaining a set of good algorithms
> > which go IN THE STANDARD DISTRIBUTION (under the usual LGPL+X licence,
> > with a disclaimer the code base isn't maintained by Inria, merely
> > distributed on behalf of the community).
> 
> But what's wrong with extlib?  Now I know it's not the "Standard"
> distribution, but that's a mere packaging issue.

A 'mere' packaging issue??? That's the very issue that concerns me.

I think there are other (technical) problems with extlib too:
the iterator design is a bit suspicious, and the implementation
is using Obj.magic without Inria support.

However the packaging issue is the primary problem, for this
and other 3PLs (third party libraries).

My own package requires standard Python, Ocaml, and C++ distros.
That's it. That's already bad enough. The only 3PL's allowed
are provided as source and built by the Felix build system.
On the Ocaml side this includes Dypgen and OCS Scheme.
Extlib couldn't be included this way because it is LGPL.
Felix is FFAU (free for any use modulo propagating copyright
notices).

I carefully avoid 3PL's I can't include as source, and as
many complications -- such as camlp4/5 -- as possible.
[I wish I could use ulex .. but it uses camlp4/5 extensions]
Getting Ocaml to work at all on Windows is hard enough
for clients.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Sorted list

[skaller]

On Sat, 2007-08-04 at 19:35 +0200, Julien Moutinho wrote:
> On Sun, Aug 05, 2007 at 01:42:21AM +1000, skaller wrote:

> > So Inria should provide the repository, and the Ocaml team has
> > a final veto on selection .. but the work is done by outside
> > volunteers.
> I am quite half-hearted about the idea of an Inrians' veto,
> despite the fact that, they sure know how to select.

Inria will be held responsible for the packaging and libraries
even if they disclaim authorship: they have a right under those
circumstances to be selective and authoritarian.

They also have to manage the respository and ..

> That said... do they have enough manpower for such a peer-review task?

No, of course not: they don't have enough to do the type theory
they want to do. A project like Ocaml never has 'enough' resources.

It's a question of bang-for-buck: leverage. A small investment of
effort by Inria could provide a large return.

> > So please would the High Priests of the Cathedral like
> > to run a little Bazaar for their disciples?
> Yep, Bazaar or another free software with a distributed repository model.

Heh .. I wasn't actually suggesting bzr.. Inria use CVS so we'd be
stuck with that.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Sorted list

[skaller]

On Sat, 2007-08-04 at 13:17 -0400, Brian Hurt wrote:
> 
> On Sat, 4 Aug 2007, Richard Jones wrote:
> 
> > But what's wrong with extlib?  Now I know it's not the "Standard"
> > distribution, but that's a mere packaging issue.
> 
> Actually, extlib is a wonderfull example of what's wrong with this idea. 
> I have grown to have major philosophical differences with extlib- 

That doesn't make the idea wrong. As I said in another post, I have
major philosophical differences with some of the Ocaml standard libs--
Str being mentioned with considerable distaste. I add the lexing
system to that too, and probably more.

My point being: it isn't just 3PLs, but also the Ocaml standard
libs, that can have problems: this shouldn't stand in the way
of improving and augmenting the library.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Sorted list

[Richard Jones]

On Sun, Aug 05, 2007 at 03:54:47AM +1000, skaller wrote:
> On Sat, 2007-08-04 at 17:21 +0100, Richard Jones wrote:
> > > Well, I would like to see a community process for selecting,
> > > implementing, documenting and maintaining a set of good algorithms
> > > which go IN THE STANDARD DISTRIBUTION (under the usual LGPL+X licence,
> > > with a disclaimer the code base isn't maintained by Inria, merely
> > > distributed on behalf of the community).
> > 
> > But what's wrong with extlib?  Now I know it's not the "Standard"
> > distribution, but that's a mere packaging issue.
> 
> A 'mere' packaging issue??? That's the very issue that concerns me.
> 
> I think there are other (technical) problems with extlib too:
> the iterator design is a bit suspicious, and the implementation
> is using Obj.magic without Inria support.

Well you don't need to use those bits.  I use ExtList and ExtString
mainly.

> However the packaging issue is the primary problem, for this
> and other 3PLs (third party libraries).
> 
> My own package requires standard Python, Ocaml, and C++ distros.
> That's it. That's already bad enough. The only 3PL's allowed
> are provided as source and built by the Felix build system.
> On the Ocaml side this includes Dypgen and OCS Scheme.
> Extlib couldn't be included this way because it is LGPL.
> Felix is FFAU (free for any use modulo propagating copyright
> notices).
> 
> I carefully avoid 3PL's I can't include as source, and as
> many complications -- such as camlp4/5 -- as possible.
> [I wish I could use ulex .. but it uses camlp4/5 extensions]
> Getting Ocaml to work at all on Windows is hard enough
> for clients.

Well, Windows is a world apart.  It has no packaging system to speak
of, no versioning, no centralised repository, no installation policies
of note.  In other words, it's where Linux was circa 1993.

Linux distros on the other hand have all of the above, so it's just a
matter of doing 'apt-get install felix' and in a few months, 'yum
install felix'.  All dependencies on whatever esoteric libraries
required are resolved automatically with no user intervention.  If
that's too hard for users, they can click Applications -> Add/Remove
Software and pick and hunt for the package they require, and the
package + dependencies get installed.

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] Sorted list

[Christophe TROESTLER]

On Sat, 04 Aug 2007 14:23:15 +0200, Philippe Wang wrote:
> 
> It works ! ... Or did I miss something ?

Do not be satisfied after a quick test!

# module S = Set.Make(struct type t = int let compare : t -> t -> int = fun 
a b -> match compare a b with 0 -> 1 | n -> n end);;
# let x = S.add 1 (S.add 1 S.empty);;
# S.elements x;;
- : S.elt list = [1; 1]

# S.mem 1 x;;
- : bool = false

# S.equal x x;;
- : bool = false

# S.elements(S.remove 1 x);;
- : S.elt list = [1; 1]

Is that what you expect?

Cheers,
ChriS

Re: [Caml-list] Sorted list

[Jon Harrop]

On Saturday 04 August 2007 18:35:17 Julien Moutinho wrote:
> I am quite half-hearted about the idea of an Inrians' veto,
> despite the fact that, they sure know how to select.
> However if this could allow extra-Inrians to actually contribute to
> (and learn) the jewelery, in a more _visible_ and _fast_ way,
> which is _hardly_ the case currently, why not!  Let us be pragmatic.
> That said... do they have enough manpower for such a peer-review task?

I think it is vitally important to note that the purpose of the team at INRIA 
is to perform research related to programming languages.

The fact that the culmination of their research has been adopted worldwide by 
serious users for applications ranging from CPU verification to cancer 
research is a testament to the enormous practical value of their work.

However, they are in no way obliged to persue OCaml beyond research. To the 
best of my knowledge, research on OCaml is slowing. However, the rate of 
adoption of OCaml is increasing. So I agree that something must be done, but 
making statements about INRIA's alleged "responsibility" will go nowhere 
fast.

I believe we are all free to fork OCaml, create a new open source project and 
begin our own iterative improvements to it. I would like to see some of the 
industrial players with significant vested financial interests in OCaml 
collaborate in making or funding these improvements.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

Re: [Caml-list] Sorted list

[Erik de Castro Lopo]

Jon Harrop wrote:

> I believe we are all free to fork OCaml, create a new open source project and 
> begin our own iterative improvements to it.

Forking the library is ok, because it is licensed LGPL with the
linking exception. No problem there.

The Ocaml compiler is quite another matter. From this page:

    http://caml.inria.fr/pub/old_caml_site/ocaml/LICENSE.html

    "The compilers and tools (all other directories in the source
    distribution) are distributed under the terms of the Q Public
    License version 1.0."

which then links to this page:

    http://trolltech.com/products/qt/licenses/licensing/qpl

which contains a section 3 as follows:

    3. You may make modifications to the Software and distribute your
    modifications, in a form that is separate from the Software, such
    as patches. The following restrictions apply to modifications: 

    a. Modifications must not alter or remove any copyright notices in
    the Software.

    b. When modifications to the Software are released under this 
    license, a non-exclusive royalty-free right is granted to the 
    initial developer of the Software to distribute your modification
    in future versions of the Software provided such versions remain 
    available under these terms in addition to any other license(s) 
    of the initial developer.

Distributing modifications to the compiler in the form of patches is
a bit of a PITA.

Erik
-- 
-----------------------------------------------------------------
Erik de Castro Lopo
-----------------------------------------------------------------
"Mutable state is actually another form of manual memory management: every
time you over-write a value you are making a decision that the old value is
now garbage, regardless of what other part of the program might have been
using it." -- Paul Johnson

Re: [Caml-list] Sorted list

[Jacques GARRIGUE]

From: Erik de Castro Lopo <mle+ocaml@mega-nerd.com>

> Distributing modifications to the compiler in the form of patches is
> a bit of a PITA.

Why? Please remember that you can still distribute binary versions of
the modified software, so the constraint is just there to ensure that
source versions include the full original sources, together with the
modifications. A number of years ago I was doing it for olabl, and
this was not a big problem (the license was even more restrictive
then.)
No, the real problem is that forking is difficult to justify if
you provide only punctual improvements. So you still want the
modifications to go into the trunk, not in a specific forked
version...

Jacques Garrigue

Re: [Caml-list] Sorted list

[Erik de Castro Lopo]

Jacques GARRIGUE wrote:

> From: Erik de Castro Lopo <mle+ocaml@mega-nerd.com>
> 
> > Distributing modifications to the compiler in the form of patches is
> > a bit of a PITA.
> 
> Why?

The main problem is that it requires that the first step of the build
process for the modified source code to be the application of a patch. 
For more extensive modifications the patch can easily grow to an 
unweildy size.

There is also the problem of supplying revision control access to the
modified source code. Providing public revsion control would, I think,
be  considered distribution, but meeting the patches requirement for 
code in RC would be a PITA.

> Please remember that you can still distribute binary versions of
> the modified software,

I was aware of that.

> No, the real problem is that forking is difficult to justify if
> you provide only punctual improvements. So you still want the
> modifications to go into the trunk, not in a specific forked
> version.

Not completely. The JoCaml project is essentially a fork of
Ocaml, but done by people at INRIA. Due to the QPL licensing
issues, for an INRIA outsider to start a similar project (ie
something which requires many modifications, deep inside the
compiler) would be difficult if they wished to provide RC
access.

Erik
-- 
-----------------------------------------------------------------
Erik de Castro Lopo
-----------------------------------------------------------------
"There is no satisfactory substitute for excellence."
-- Dr. Arnold O. Beckman

Re: [Caml-list] Sorted list

[Richard Jones]

On Sun, Aug 05, 2007 at 09:44:59PM +1000, Erik de Castro Lopo wrote:
> Distributing modifications to the compiler in the form of patches is
> a bit of a PITA.

Again, just a packaging issue.  .debs and RPM explicitly support
keeping "pristine" sources and automatically applying patches to them.

Rich.

PS. Don't take this as advocacy for forking OCaml though - I think
that would be a crazy idea!

-- 
Richard Jones
Red Hat

Re: [Caml-list] Sorted list

[Richard Jones]

On Sun, Aug 05, 2007 at 10:31:48PM +1000, Erik de Castro Lopo wrote:
> The main problem is that it requires that the first step of the build
> process for the modified source code to be the application of a patch. 
> For more extensive modifications the patch can easily grow to an 
> unweildy size.

rpmbuild -bp ...

> There is also the problem of supplying revision control access to the
> modified source code. Providing public revsion control would, I think,
> be  considered distribution, but meeting the patches requirement for 
> code in RC would be a PITA.

It depends what would be considered as distribution, but revision
control systems like git essentially operate on pristine sources +
patches, and you could easily set it up so that one branch was the
pristine source and another branch contained your changesets (branches
are virtually free in git).

Again, I'm not suggesting that we fork OCaml.

Rich.

-- 
Richard Jones
Red Hat

RE: [Caml-list] Sorted list

[David Allsopp]

On Sat, 2007-08-04 at 20:07 +0100, Richard Jones wrote:
> Well you don't need to use those bits.  I use ExtList and ExtString
> mainly.

ExtList is underpinned by Obj.magic - its "tail recursive" implementations
work by manipulating the internal representation of a list rather than
writing "proper" O'Caml (it's a piece of genius and frankly is how the
StdLib ought to do it...).

> Well, Windows is a world apart.  It has no packaging system to speak
> of, no versioning, no centralised repository, no installation policies
> of note.  In other words, it's where Linux was circa 1993.

Spoken by someone who sounds like he hasn't used Windows since 1993? :o) My
understanding is that in 1993 finding any PC hardware capable of running
Linux was the amusing game... rose-tinted spectacles, perhaps?


David

Re: [Caml-list] Sorted list

[Xavier Leroy]

In reply to Brian Hurt's comment:

>>Unortunately, the standard Ocaml solution in a situation like this is to
>>implement your own data structure.  The good news is that this is easy.
>>The bad news is that, because this is easy, there is little pressure on
>>the maintainers of Ocaml to add features to the core library.

We'll leave the development of the be-all and end-all of data structure
libraries to others (see below).  At any rate, I noticed something
interesting in this thread, namely that even if the OCaml core library
provided an implementation of priority queues, it would probably not
have met the needs of the original poster, because textbook priority
queues do not provide a "remove" operation.  In other terms, it is
often inevitable to implement your own "tailor-fit" data structure;
that is part of programming.

In reply to John Skaller's request:

> Well, I would like to see a community process for selecting,
> implementing, documenting and maintaining a set of good algorithms

Why not.  Care to start such a process yourself?  Or more modestly
joining one of the existing efforts for building additional OCaml
libraries, like Extlib?

> which go IN THE STANDARD DISTRIBUTION (under the usual LGPL+X licence,
> with a disclaimer the code base isn't maintained by Inria, merely
> distributed on behalf of the community).
> So Inria should provide the repository, and the Ocaml team has
> a final veto on selection .. but the work is done by outside
> volunteers.

No way.  Neither you nor us want to deal with our (admittedly slow)
release cycle, with copyright assignments, etc.  Moreover, we
definitely do not have the time and manpower to build such an
infrastructure, decide between conflicting proposals, etc.  If a
community is willing to make such an effort, it will have to
self-organize.

> So please would the High Priests of the Cathedral like
> to run a little Bazaar for their disciples?

Bazaars are not run by priests.

- Xavier Leroy

Re: [Caml-list] Sorted list

[Xavier Leroy]

> ExtList is underpinned by Obj.magic -

Agreed.

> its "tail recursive" implementations
> work by manipulating the internal representation of a list rather than
> writing "proper" O'Caml (it's a piece of genius and frankly is how the
> StdLib ought to do it...).

I don't think so -- basically, Obj.magic isn't part of the OCaml
language and should not be used unless there is absolutely no other
option.  The Queue module is the standard library uses Obj.magic for
additional performance, but this is really sending the wrong message.
If tail recursion elimination modulo constructors (what Extlib is
doing manually) is really important, I believe it should be done by
the compiler, under the hood.  (That's not trivial, mind you.)

>>Well, Windows is a world apart.  It has no packaging system to speak
>>of, no versioning, no centralised repository, no installation policies
>>of note.  In other words, it's where Linux was circa 1993.
>
> Spoken by someone who sounds like he hasn't used Windows since 1993? :o)

I reluctantly but regularly use Windows to maintain the Windows port
of OCaml, and agree with Richard Jones's assessment.  Windows is
geared towards the installation of big, standalone programs like
Office or games, but has nothing comparable to the package management
facilities of Linux or BSD.

> My understanding is that in 1993 finding any PC hardware capable of
> running Linux was the amusing game... rose-tinted spectacles,
> perhaps?

Replace "Linux circa 1993" by "Unix variants circa 1993" (SunOS,
Ultrix, etc) if you wish.  But for the record, I was running NetBSD on
a bog-standard 486 PC in 1993, and installed Slackware Linux on the
same PC in 1994.

- Xavier Leroy

RE: [Caml-list] Sorted list

[David Allsopp]

> > its "tail recursive" implementations
> > work by manipulating the internal representation of a list rather than
> > writing "proper" O'Caml (it's a piece of genius and frankly is how the
> > StdLib ought to do it...).
>
> I don't think so -- basically, Obj.magic isn't part of the OCaml
> language and should not be used unless there is absolutely no other
> option.  The Queue module is the standard library uses Obj.magic for
> additional performance, but this is really sending the wrong message.
> If tail recursion elimination modulo constructors (what Extlib is
> doing manually) is really important, I believe it should be done by
> the compiler, under the hood.  (That's not trivial, mind you.)

Altering the compiler to do this would be the utopia, I agree - but if *you*
(i.e. Inria) wrote an implementation using Obj.magic this doesn't send a bad
message as such - the implementation of the Standard Library is *your*
problem: as long as the module interface is the same, a hypothetical future
version of O'Caml without Obj.magic could revert to the "slower" pure O'Caml
implementations. Surely the standard library should aim to have the fastest
implementation of these functions for any given version?

Purely out of interest, how "standardised" are the primitives of the O'Caml
runtime? Obj.magic may not be an official part of the language but what
about the %identity primitive in the runtime?

> I reluctantly but regularly use Windows to maintain the Windows port
> of OCaml, and agree with Richard Jones's assessment.  Windows is
> geared towards the installation of big, standalone programs like
> Office or games, but has nothing comparable to the package management
> facilities of Linux or BSD.

I completely agree that the Linux package management facilities are much
more impressive (though I've never particularly missed them as there are
other solutions for administration): but the assertion that Windows has
nothing "to speak of" seemed somewhat ill-founded (and based back in 1993:
cf. DOS 4/5 + Windows 3.0/3.1 which really didn't have any standard set-up
features!). But this is possibly rather off-topic for this
list/discussion...


David

Re: [Caml-list] Sorted list

[Erik de Castro Lopo]

Richard Jones wrote:

> Again, I'm not suggesting that we fork OCaml.

I am suggesting that it should only be done for experiments of
a large and intrusive nature (ie experiments of a JoCaml size
or larger).

Forking for incremental language improvements would indeed be
silly.

Erik
-- 
-----------------------------------------------------------------
Erik de Castro Lopo
-----------------------------------------------------------------
"C++ is like jamming a helicopter inside a Miata and expecting
some sort of improvement." -- Drew Olbrich

Re: [Caml-list] Sorted list

[skaller]

On Sun, 2007-08-05 at 18:26 +0200, Xavier Leroy wrote:
> In reply to Brian Hurt's comment:

> In reply to John Skaller's request:
> 
> > Well, I would like to see a community process for selecting,
> > implementing, documenting and maintaining a set of good algorithms
> 
> Why not.  Care to start such a process yourself?  Or more modestly
> joining one of the existing efforts for building additional OCaml
> libraries, like Extlib?

I am actually an extlib developer :)

> No way.  Neither you nor us want to deal with our (admittedly slow)
> release cycle, with copyright assignments, etc.  Moreover, we
> definitely do not have the time and manpower to build such an
> infrastructure, decide between conflicting proposals, etc.  If a
> community is willing to make such an effort, it will have to
> self-organize.

The community can self-organise, but that won't get extra
components in the standard distro.

In the case of adding functions to existing modules,
a separate distribution isn't even possible.

Extlib tried both these things already. It may be a good
or bad library, but it failed in its goals; none of it
has got into the standard distro, not even the ideas.

> Bazaars are not run by priests.

No, but the priests let the people use their courtyard
to run them, happily accept contributions, and provide
blessings occasionally :)

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Sorted list

[Andrej Bauer]

tmp123@menta.net wrote:
> It seems dificult to generate an unique identifier, for this subject or any 
> other (in this sense, I feel nostalgic of the old C pointers).

You can use references for that:

type id = unit ref

(** [unique_id ()] returns a unique reference. *)
let unique_id () = ref ()

(** [equal_id id1 id2] compares two ids for equality. *)
let equal_id id1 id2 = (id1 == id2)

Now the trouble here is that you might accidentally compare id's with = 
instead of ==. If I use references to functional values then I get a 
runtime exception rather than a type error. Abstract types don't help 
either, so I am out of ideas.

There are many theoretical reasons why abstract types should have their 
own user-defined equality tests (and the user might choose not to have 
an equality test at all). Where do PL designers like Xavier stand on 
this? SML has equality types (but that's not what I am talking about).

Best regards,

Andrej