ocaml-lib-devel — Developer's mailing list

[Ocaml-lib-devel] a PMap.add function in the style of PMap.union (was: Map with set operations over the keys)

[Martin J. <mar...@em...>]

On Mon, 6 Jun 2005, Christophe Raffalli wrote:

> > After a second though I think it's little overweighted to make the user
> > specify a merge function. Why not simply specify that in such cases, the
> > item of the first map is selected ? That seems more reasonable.
> >
>
> No, you can for instance implement multiset as map to natural ... and
> the merge function is then addition.
>
> Your merge function should even raise the exception Remove when you want
> to say that the result should be removed from the map ... (For insance,
> if you have Map to integer and want to say that 0 should be removed from
> the map).

Another function which could be useful would be one which adds one
element, just like:
  fun key value m -> union (singleton key value) m

but slightly more efficient, and accepting the same options as "union".


Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Martin J. <mar...@em...>]

On Mon, 6 Jun 2005, Christophe Raffalli wrote:

> Nicolas Cannasse wrote:
> >>>After a second though I think it's little overweighted to make the user
> >>>specify a merge function. Why not simply specify that in such cases, the
> >>>item of the first map is selected ? That seems more reasonable.
> >>>
> >>
> >>No, you can for instance implement multiset as map to natural ... and
> >>the merge function is then addition.
> >>
> >>Your merge function should even raise the exception Remove when you want
> >>to say that the result should be removed from the map ... (For insance,
> >>if you have Map to integer and want to say that 0 should be removed from
> >>the map).
> >
> >
> > I would say it's bad API design to use a "merge" function in order to remove
> > elements.
> > A more specific function should be provided.
>
> I do not think so. When your merge gives accidentally 0, and the value
> should be removed, you do not want to scan the map once more to remove
> the zero ...

I concur. Maybe we can use another name than "merge", but I like this use
of exceptions. Here the term "exception" is really appropriate since it's
an exception to the mathematical meaning of union (or intersection).

Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Martin J. <mar...@em...>]

On Mon, 6 Jun 2005, Nicolas Cannasse wrote:

> > > > Hello,
> > > >
> > > > Some useful operations over the keys of a map are not provided by the
> > > > standard Map module, neither by ExtLib's PMap, but are provided only
> by
> > > > the Set module.
> > >
> > > Yes I would also love to set  diff / union / intersection for PMaps.
> > > But I'm not sure which semantic is appropriate.
> > > Maybe only have diff / union / inter operations on *keys* would be
> enough ?
> > > Please fell free to post implementation, maybe based on Set module.
> >
> > What do you think of this:
> >
> > (* default merge = fun x y -> x *)
> > val union : ?merge:('b -> 'b -> 'b) -> ('a, 'b) t -> ('a, 'b) t -> ('a,
> 'b) t
> >
> > (* a merge function must be given to inter *)
> > val inter : merge:('b -> 'c -> 'd) -> ('a, 'b) t -> ('a, 'c) t -> ('a, 'd)
> t
> >
> > val diff : ('a, 'b) t -> ('a, 'c) t -> ('a, 'b) t
>
> Why not generalize a little more ?
>
> val union : merge:('b -> 'c -> 'd) -> ('a,'b) t -> ('a,'c) t -> ('a,'d) t
>
> The only problem is that we can't use "identity" as default merger.

It cannot be so simple with the union function because you have to provide
2 additional functions of type ('b -> 'd) and ('c -> 'd) to convert the
bindings which are not in both maps (cannot default to identity either).
This could also be achieved by only one merge function of type
('b option -> 'c option -> 'd), but that's really heavy.

In that case, I would first convert my maps of different types to the same
type and then use the union function which expects 2 maps of the same
type. Since the cost would be linear with respect to the size of the maps,
I guess it's OK.


Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Re: [Ocaml-lib-devel] Map with set operations over the keys

[fva <fv...@ts...>]

Hello


Christophe Raffalli wrote:

>Nicolas Cannasse wrote:
>  
>
>>>>After a second though I think it's little overweighted to make the user
>>>>specify a merge function. Why not simply specify that in such cases, the
>>>>item of the first map is selected ? That seems more reasonable.
>>>>        
>>>>
I like the idea of the merge function parameter... This makes sense when 
you do not rely on the identity to provide for equality of 
representations in the base set.

>>>No, you can for instance implement multiset as map to natural ... and
>>>the merge function is then addition.
>>>
>>>Your merge function should even raise the exception Remove when you want
>>>to say that the result should be removed from the map ... (For insance,
>>>if you have Map to integer and want to say that 0 should be removed from
>>>the map).
>>>      
>>>
>>I would say it's bad API design to use a "merge" function in order to remove
>>elements.
>>A more specific function should be provided.
>>    
>>
>
>I do not think so. When your merge gives accidentally 0, and the value
>should be removed, you do not want to scan the map once more to remove
>the zero ...
>  
>

In my opinion, this depends on the representation (i.e. eventually the 
semantics):

1) If you are representing the *support* i.e. those elements *not* 
mapping to the null element (whatever that means) you should remove 
those elements the merge operationg of which map to null

2) If you are representing the whole map/set/many-valued set whatever in 
its entirety, you should keep the merged value, whatever the result.

But again, this is just an opinion...

Regards,

    F. Valverde

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Nicolas C. <war...@fr...>]

> > I would say it's bad API design to use a "merge" function in order to
remove
> > elements.
> > A more specific function should be provided.
>
> I do not think so. When your merge gives accidentally 0, and the value
> should be removed, you do not want to scan the map once more to remove
> the zero ...

Then it's no longer a merge...
What you want is a more generic function that will do a merge+filter.

Nicolas

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Christophe R. <Chr...@un...>]

Nicolas Cannasse wrote:
>>>After a second though I think it's little overweighted to make the user
>>>specify a merge function. Why not simply specify that in such cases, the
>>>item of the first map is selected ? That seems more reasonable.
>>>
>>
>>No, you can for instance implement multiset as map to natural ... and
>>the merge function is then addition.
>>
>>Your merge function should even raise the exception Remove when you want
>>to say that the result should be removed from the map ... (For insance,
>>if you have Map to integer and want to say that 0 should be removed from
>>the map).
> 
> 
> I would say it's bad API design to use a "merge" function in order to remove
> elements.
> A more specific function should be provided.

I do not think so. When your merge gives accidentally 0, and the value
should be removed, you do not want to scan the map once more to remove
the zero ...

> Nicolas
> 

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Chr...@un...
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Nicolas C. <war...@fr...>]

>> After a second though I think it's little overweighted to make the user
>> specify a merge function. Why not simply specify that in such cases, the
>> item of the first map is selected ? That seems more reasonable.
>>
>
>No, you can for instance implement multiset as map to natural ... and
>the merge function is then addition.
>
>Your merge function should even raise the exception Remove when you want
>to say that the result should be removed from the map ... (For insance,
>if you have Map to integer and want to say that 0 should be removed from
>the map).

I would say it's bad API design to use a "merge" function in order to remove
elements.
A more specific function should be provided.

Nicolas

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Christophe R. <Chr...@un...>]

> 
> 
> After a second though I think it's little overweighted to make the user
> specify a merge function. Why not simply specify that in such cases, the
> item of the first map is selected ? That seems more reasonable.
> 

No, you can for instance implement multiset as map to natural ... and
the merge function is then addition.

Your merge function should even raise the exception Remove when you want
to say that the result should be removed from the map ... (For insance,
if you have Map to integer and want to say that 0 should be removed from
the map).


> Nicolas
> 

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Chr...@un...
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Nicolas C. <war...@fr...>]

> > What do you think of this:
> >
> > (* default merge = fun x y -> x *)
> > val union : ?merge:('b -> 'b -> 'b) -> ('a, 'b) t -> ('a, 'b) t -> ('a,
> 'b) t
> >
> > (* a merge function must be given to inter *)
> > val inter : merge:('b -> 'c -> 'd) -> ('a, 'b) t -> ('a, 'c) t -> ('a,
'd)
> t
> >
> > val diff : ('a, 'b) t -> ('a, 'c) t -> ('a, 'b) t
>
> Why not generalize a little more ?
>
> val union : merge:('b -> 'c -> 'd) -> ('a,'b) t -> ('a,'c) t -> ('a,'d) t
>
> The only problem is that we can't use "identity" as default merger.
>
> Nicolas

After a second though I think it's little overweighted to make the user
specify a merge function. Why not simply specify that in such cases, the
item of the first map is selected ? That seems more reasonable.

Nicolas

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Nicolas C. <war...@fr...>]

> > > Hello,
> > >
> > > Some useful operations over the keys of a map are not provided by the
> > > standard Map module, neither by ExtLib's PMap, but are provided only
by
> > > the Set module.
> >
> > Yes I would also love to set  diff / union / intersection for PMaps.
> > But I'm not sure which semantic is appropriate.
> > Maybe only have diff / union / inter operations on *keys* would be
enough ?
> > Please fell free to post implementation, maybe based on Set module.
>
> What do you think of this:
>
> (* default merge = fun x y -> x *)
> val union : ?merge:('b -> 'b -> 'b) -> ('a, 'b) t -> ('a, 'b) t -> ('a,
'b) t
>
> (* a merge function must be given to inter *)
> val inter : merge:('b -> 'c -> 'd) -> ('a, 'b) t -> ('a, 'c) t -> ('a, 'd)
t
>
> val diff : ('a, 'b) t -> ('a, 'c) t -> ('a, 'b) t

Why not generalize a little more ?

val union : merge:('b -> 'c -> 'd) -> ('a,'b) t -> ('a,'c) t -> ('a,'d) t

The only problem is that we can't use "identity" as default merger.

Nicolas

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Martin J. <mar...@em...>]

On Sat, 4 Jun 2005, Nicolas Cannasse wrote:

> > Hello,
> >
> > Some useful operations over the keys of a map are not provided by the
> > standard Map module, neither by ExtLib's PMap, but are provided only by
> > the Set module.
>
> Yes I would also love to set  diff / union / intersection for PMaps.
> But I'm not sure which semantic is appropriate.
> Maybe only have diff / union / inter operations on *keys* would be enough ?
> Please fell free to post implementation, maybe based on Set module.

What do you think of this:

(* default merge = fun x y -> x *)
val union : ?merge:('b -> 'b -> 'b) -> ('a, 'b) t -> ('a, 'b) t -> ('a, 'b) t

(* a merge function must be given to inter *)
val inter : merge:('b -> 'c -> 'd) -> ('a, 'b) t -> ('a, 'c) t -> ('a, 'd) t

val diff : ('a, 'b) t -> ('a, 'c) t -> ('a, 'b) t

These functions would be quite powerful, I think. The idea is to merge the
values which have the same key during the union and inter operations.
The keys are supposed to be interchangeable like before (in Set or Map) if
the comparison function says they are equal.

So I started the implementation, but it requires the quasi-duplication
and careful adaptation of a lot of code, essentially because the "merge"
arguments are not symmetric in this interface.

For now, only the following works:

val union : ('a, 'b) t -> ('a, 'b) t -> ('a, 'b) t
val inter : ('a, 'b) t -> ('a, 'b) t -> ('a, 'b) t
val diff : ('a, 'b) t -> ('a, 'c) t -> ('a, 'b) t

... where it is not specified which value is kept when 2 bindings have
the same key (union, inter), which is really not that great.

So let me know what you think, before I continue this implementation.

The code is attached to this email. It compiles but was not tested.


Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Nicolas C. <war...@fr...>]

> Hello,
> 
> Some useful operations over the keys of a map are not provided by the
> standard Map module, neither by ExtLib's PMap, but are provided only by
> the Set module.

Yes I would also love to set  diff / union / intersection for PMaps.
But I'm not sure which semantic is appropriate.
Maybe only have diff / union / inter operations on *keys* would be enough ?
Please fell free to post implementation, maybe based on Set module.

Nicolas

[Ocaml-lib-devel] Map with set operations over the keys

[Martin J. <mar...@em...>]

Hello,

Some useful operations over the keys of a map are not provided by the
standard Map module, neither by ExtLib's PMap, but are provided only by
the Set module.

Reason: removing a set of keys from a map of bindings could be done in
O(n) with a Map.diff function, but only in O(n log n) with the current
functions provided by the Map or Set modules.

An interface for the new functions of PMap could look like this (the
names are not very coherent, but it's just a draft):

(* Shortcuts, just for clarity *)
type ('a, 'b) map = ('a, 'b) t
type 'a set = ('a, unit) map

val diff : ('a, 'b) map -> ('a, 'c) map -> ('a, 'b) map

val union : ('a, 'b) map -> (a, 'b) map -> ('a, 'b) map
val key_union : ('a, 'b) map -> ('a, 'c) map -> 'a set

val inter : ('a, 'b) map -> ('a, 'c) map -> ('a, 'b) map
val inter2 : ('a, 'b) map -> ('a, 'c) map -> ('a, ('b, 'c)) map
val key_inter : ('a, 'b) map -> ('a, 'c) map -> 'a set

val key_subset : ('a, 'b) map -> ('a, 'c) map -> bool
val key_equal : ('a, 'b) map -> ('a, 'c) map -> bool

val keys : ('a, 'b) map -> 'a set
val key_set : ('a, 'b) map -> 'a PSet.t
val key_enum : ('a, 'b) map -> 'a Enum.t


Implementation: essentially copy-pasting functions from Set, with minor
modifications.

Is it something that could be added to PMap in ExtLib?
(or in ExtExtLib? :-)


Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Re: [Ocaml-lib-devel] Dllist

[John S. <sk...@us...>]

On Sun, 2005-05-29 at 16:25 +0200, Christophe TROESTLER wrote:

> You haven't much looked at the code, have you. 

No, i haven't.

> Also, from a point of view of efficiency, providing efficient low
> level data-structures that become inefficient (compared to a direct
> implementation) when wrapped to do what the user really wants is a
> waste of computer and human resources.

No dispute. The problem is deciding 'what the user really wants'.
For some interfaces that is easy, for others it is not.

Just try to design a graph library for example :)

> It is quite funny to take the [splice] function as a justification for
> your design when, IMO, its utility is far lower than the possibility
> of having empty lists.

In your opinion. However it is NOT my design. I suggested
to the original author a nodes-only interface would
be more appropriate. I am simply stating it again as best I can,
so you can understand the rationale.

I'm not claiming it is the best design for Extlib, I'm just
explaining that there is a reason it is the way it is.

Reopening the discussion is fine by me. If there is a decision
to replace the existing code, that is fine by me too.

I don't use dlist, it won't affect me. In fact I don't use
extlib either (it's too heavy to include in source form
in my product).

> In the end, it all boils down to which ADT we want to build. 

Yes. I agree. Except I'd say 'ADTS' plural.

> > Also, I can't contribute any experience with the particular
> > implementation in Extlib, because I don't use it.
> 
> But eventually intend to?

Not in the Felix project, unless INRIA adopts it, which was
the original hope.

For some other Ocaml development, I may well use it.

Part of the reason is enums: they're central to the design
of extlib, they're a great idea, the implementation is 
probably efficient .. but I have some misgivings about the
interface.  So I'm in the interesting position I think
enums are important and useful but not quite right:
roughly speaking they confuse forward and input iterators,
which C++ takes pains to distinguish: input iterators
MUST use eager semantics (or at least schedulable semantics),
whereas forward iterators would use lazy semantics.

-- 
John Skaller, skaller at users.sf.net
PO Box 401 Glebe, NSW 2037, Australia Ph:61-2-96600850 
Download Felix here: http://felix.sf.net

Re: [Ocaml-lib-devel] Dllist

[Christophe T. <chr...@us...>]

On Sun, 29 May 2005, John Skaller <sk...@us...> wrote:
> 
> Well my view is that a *base* library provides simple efficient
> things -- it is oriented to the computer NOT the user.

In the first mail your justification calls upon "mathematics" (in a
flawed way IMHO), now you refer to the computer.  Aren't these at the
opposite ends of the spectrum?  IMO, the interface is for the user
(thus must be mathematically well defined, simple yet powerful) and
the implementation is for the computer (thus allowed to use tricks to
achieve efficiency).

> ExtLib is positioned as a replacement system library.

Precisely!  If you look at the std lib, it does not provide
e.g. balanced binary trees leaving to you the task of implementing Map
and Set.  It provides data-structure interfaces, not down to the metal
low-level libraries (use C if that's what you are after).

> The point is that you can construct a 'container' design from a
> 'nodes-only' design with a wrapper, but not the other way around,

You haven't much looked at the code, have you.  If you had, you would
have noticed that the wrapper would only use the node data-structure,
the code for all functions being different enough to mandate rewriting
them.

Also, from a point of view of efficiency, providing efficient low
level data-structures that become inefficient (compared to a direct
implementation) when wrapped to do what the user really wants is a
waste of computer and human resources.

> For example, consider two lists A and B, and you join them to create
> a list C. What happens to A and B?  With the current implementation
> as I understand it, there isn't an issue, A, B, and C are now all
> the one list.

It is quite funny to take the [splice] function as a justification for
your design when, IMO, its utility is far lower than the possibility
of having empty lists.

In fact [splice l1 l2] will leave [l1] and [l2] in invalid states when
[l1] and [l2] are lists _with_ends_.  It is not the case for
_circular_ lists -- but given the name of the module, it is my
understanding that the doubly-linked list is what is targeted.  A
circular list module [CircularList] can also be built (and different
tricks may be imagined for its implementation).

In the end, it all boils down to which ADT we want to build.  One
wants to use a library for the operations it provides (in an efficient
manner) not because it is nice to the computer.

> Also, I can't contribute any experience with the particular
> implementation in Extlib, because I don't use it.

But eventually intend to?

ChriS

Re: [Ocaml-lib-devel] A PSet to match PMap?

[Nicolas C. <war...@fr...>]

> > Is anyone interested in adding a polymorphic set module to match the
> > polymorphic map module already in Extlib?  If there's interest, I may
> > go ahead and contribute one.
> 
> There isn't one already???
> 
> Hmm .. but this is probably the most commonly asked
> for extension to the standard ocaml library .. :)
> 
> 
> -- 
> John Skaller, skaller at users.sf.net
> PO Box 401 Glebe, NSW 2037, Australia Ph:61-2-96600850 
> Download Felix here: http://felix.sf.net

I agree. Yaron you're welcome to contribute a PSet.

Nicolas

Re: [Ocaml-lib-devel] Labels in list module

[Nicolas C. <war...@fr...>]

No purpose I think here.
Maybe sort was first added with optional argument, and other sorts were
added after that.

Nicolas

----- Original Message ----- 
From: "Yaron Minsky" <ym...@gm...>
To: "ExtLib" <oca...@li...>
Sent: Sunday, May 29, 2005 4:00 AM
Subject: [Ocaml-lib-devel] Labels in list module


I've been playing around with the possibility of adding labelled
interfaces to extlib to match the labelled interfaces available in the
standard library.  When I was looking over the list interface of
extlib, I noticed something odd:  The sort function has an optional
comparison argument, but the fast_sort, stable_sort and merge don't:
the argument is mandatory.  Is this on purpose, and if so, why?

Yaron

Re: [Ocaml-lib-devel] IO and random access

[Nicolas C. <war...@fr...>]

> Hi,
>
> Is it possible to use the IO module to do random access? From the API,
> this isn't clear at first look. And what about seek/tell functions?
>
> Jonathan

Seek is not possible since most IOs ( think socket streams ) are not
seekable.
As for tell you can use the pos_in and pos_out functions which wrap an IO an
return an coutable IO.

Nicolas

[Ocaml-lib-devel] IO and random access

[Jonathan R. <jon...@gm...>]

Hi,

Is it possible to use the IO module to do random access? From the API,
this isn't clear at first look. And what about seek/tell functions?

Jonathan

Re: [Ocaml-lib-devel] Dllist

[Brian H. <bh...@sp...>]

On Sun, 29 May 2005, John Skaller wrote:

>> Computer cycles are cheap compared
>> to human cycles.
>
> We don't part company on that statement however.
>
> There is actually reason for orienting the library
> components to what is simple for the machine,
> as well as plenty of experience that it is a good idea,
> precisely to make subsequent human use simple.

That's what I meant.  I prefer to optimize for human use over computer 
use.  And I don't sweat squezing every last cycle out of my code.  If I 
did, I'd be writting in assembler, or C at the most, not Ocaml.

> So there is no dispute on goals, merely on how to
> achieve them.

No, there is a dispute on goals.  Easy for humans to use, or easy for 
computers to use?  Or to put it a different way:

>
> The bottom line is that library design is difficult.
> It is always hard to choose between a lean, simple,
> efficient code, and a richer and more immediately
> useful one.

Yep.  And I'm down on the richer and more immediately usefull side.

>
> In my opinion .. and it is only that .. programming language
> standard libraries should not pre-empt the building of
> the richer, easier to use but more application specific
> style of library -- they should instead wrap up only
> low level concepts.

And if the library was written in Ocaml, it can be rewritten in Ocaml as 
well.  I've yet to see a library in extlib that'd take me more than a day 
to recreate, worst case.  And if I'm recreating the library for a special 
purpose, often times it takes less time than that, as I only recreate 
those functions I actually need.  Hell, I wrote the central data structure 
definitions and two core functions as throw-aways into an email.

>
> ExtLib is positioned as a replacement system library.

I'm more of the Java school of system libraries than the C school.

> With the container design. But this doesn't happen with the
> nodes only design. That's the point -- all lists are always
> valid at all times.

Define valid.  By one definition, in the above example all lists are 
always valid too.  Having no elements does not mean the list is invalid.

If you mean that some other code somewhere can get confused because list B 
changed- that can happen in both implementations.

>
>> Note that you can leave A and B in valid states.
>
> Yes, you can in this case, the issue isn't if they're
> valid, but what they *should* represent. That issue
> doesn't arise with the nodes only design.

Yes it does, it's just hidden behind the introduced complexity.  In 
appending B to A, you've changed list B.  In my implementation, you empty 
B.  In your implementation, you've appended list A to list B.  In both 
cases, you have still changed list B.

Worse yet, now changes to list B also change list A.  By the act of 
appending the two lists, I've created an identity that didn't exist 
before.

We can argue til the cows come home which behavior is better- but you 
can't pretend that the node-based implementation doesn't have side-effect 
problems.

> (a) arbitrary decisions have to be made,
> this is not the case for append (its clear you're emptying list B
> when you append it to A), but some other cut and paste operations
> leave one wondering which lists contain what, and

Yep.  And these decisions need to be made no matter what basic design we 
go with.  And they should be consistent, and they should be documented.

>
> (b) maintaining coherence turns out to be very expensive.
>

Yep.  On the other hand, if you want coherence, you should probably be 
using an applicative data structure.  For imperitive data structures, I'd 
be inclined to be maximally destructive, because it's likely the 
destructive variation is what is wanted.

> The point is that you can construct a 'container' design
> from a 'nodes-only' design with a wrapper, but not the
> other way around, so the nodes-only design is the right
> one to implement in a low level library by Occams razor.

And my point is that if I have to write a wrapper library, I won't use the 
base library because reimplementing it isn't that hard.

Brian

Re: [Ocaml-lib-devel] A PSet to match PMap?

[John S. <sk...@us...>]

On Sat, 2005-05-28 at 22:02 -0400, Yaron Minsky wrote:
> Is anyone interested in adding a polymorphic set module to match the
> polymorphic map module already in Extlib?  If there's interest, I may
> go ahead and contribute one.

There isn't one already???

Hmm .. but this is probably the most commonly asked
for extension to the standard ocaml library .. :)


-- 
John Skaller, skaller at users.sf.net
PO Box 401 Glebe, NSW 2037, Australia Ph:61-2-96600850 
Download Felix here: http://felix.sf.net

[Ocaml-lib-devel] A PSet to match PMap?

[Yaron M. <ym...@gm...>]

Is anyone interested in adding a polymorphic set module to match the
polymorphic map module already in Extlib?  If there's interest, I may
go ahead and contribute one.

Yaron

[Ocaml-lib-devel] Labels in list module

[Yaron M. <ym...@gm...>]

I've been playing around with the possibility of adding labelled
interfaces to extlib to match the labelled interfaces available in the
standard library.  When I was looking over the list interface of
extlib, I noticed something odd:  The sort function has an optional
comparison argument, but the fast_sort, stable_sort and merge don't:
the argument is mandatory.  Is this on purpose, and if so, why?

Yaron

Re: [Ocaml-lib-devel] Dllist

[John S. <sk...@us...>]

On Sat, 2005-05-28 at 15:39 -0500, Brian Hurt wrote:
> 
> On Sun, 29 May 2005, John Skaller wrote:
> 
> > Well my view is that a *base* library provides simple
> > efficient things -- it is oriented to the computer NOT the user.
> 
> This is where you and I part company.  

OK.

> Computer cycles are cheap compared 
> to human cycles.

We don't part company on that statement however.

There is actually reason for orienting the library
components to what is simple for the machine,
as well as plenty of experience that it is a good idea,
precisely to make subsequent human use simple.

So there is no dispute on goals, merely on how to
achieve them. 

The bottom line is that library design is difficult.
It is always hard to choose between a lean, simple,
efficient code, and a richer and more immediately
useful one.

In my opinion .. and it is only that .. programming language
standard libraries should not pre-empt the building of
the richer, easier to use but more application specific
style of library -- they should instead wrap up only
low level concepts.

ExtLib is positioned as a replacement system library.

> > The problem with doing that is that you can't so easily
> > chop bits of the list up, or splice bits of a list together.
> 
> Yep.  This is a problem with imperitive data structures.
> 
> >
> > For example, consider two lists A and B, and you join them
> > to create a list C. What happens to A and B?
> 
> A and B are now invalid lists.  Unless A is C.

With the container design. But this doesn't happen with the
nodes only design. That's the point -- all lists are always
valid at all times.

> Note that you can leave A and B in valid states.  

Yes, you can in this case, the issue isn't if they're
valid, but what they *should* represent. That issue
doesn't arise with the nodes only design.

> Conceptually, all the elements of B are removed from it an appended to A.
> 
> Yes, it's a destructive operation.  So?  Welcome to the imperitive world.

No, the 'so' is that 

(a) arbitrary decisions have to be made,
this is not the case for append (its clear you're emptying list B
when you append it to A), but some other cut and paste operations
leave one wondering which lists contain what, and 

(b) maintaining coherence turns out to be very expensive.

The point is that you can construct a 'container' design
from a 'nodes-only' design with a wrapper, but not the
other way around, so the nodes-only design is the right
one to implement in a low level library by Occams razor.

Note that I am NOT saying this is any kind of proof the
right choice was made -- I'm just saying there is a rational
basis for *both* choices. In fact, I'll bet there exist
more than just these two designs ..

Also, I can't contribute any experience with the particular
implementation in Extlib, because I don't use it.

-- 
John Skaller, skaller at users.sf.net
PO Box 401 Glebe, NSW 2037, Australia Ph:61-2-96600850 
Download Felix here: http://felix.sf.net

Re: [Ocaml-lib-devel] Dllist

[Brian H. <bh...@sp...>]

On Sun, 29 May 2005, John Skaller wrote:

> Well my view is that a *base* library provides simple
> efficient things -- it is oriented to the computer NOT the user.

This is where you and I part company.  Computer cycles are cheap compared 
to human cycles.

> The problem with doing that is that you can't so easily
> chop bits of the list up, or splice bits of a list together.

Yep.  This is a problem with imperitive data structures.

>
> For example, consider two lists A and B, and you join them
> to create a list C. What happens to A and B?

A and B are now invalid lists.  Unless A is C.

Note that you can leave A and B in valid states.  Consider my example 
implementation I posted earlier, I couple implement the O(1) append like 
this:

let append a b =
     match a.tail, b.head with
         | None, _ ->
             a.head <- b.head;
             a.tail <- b.tail;
             b.head <- None;
             b.tail <- None;
             ()
         | _, None -> ()
         | Some(x), Some(y) ->
             x.next <- y;
             y.prev <- x;
             a.tail <- b.tail;
             b.head <- None;
             b.tail <- None;
             ()
;;

Conceptually, all the elements of B are removed from it an appended to A.

Yes, it's a destructive operation.  So?  Welcome to the imperitive world.

Brian