Map for FGL

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
29 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Map for FGL

Christian Maeder
Hi,

I wonder how well

http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Inductive-Internal-FiniteMap.html

performs wrt. other Map implementations.

It may be worth replacing this implementation, too.

Cheers Christian
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Map for FGL

Adrian Hey
Hello,

On Monday 09 Jan 2006 1:11 pm, Christian Maeder wrote:

> Hi,
>
> I wonder how well
>
> http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Induct
>ive-Internal-FiniteMap.html
>
> performs wrt. other Map implementations.
>
> It may be worth replacing this implementation, too.

I suspect it doesn't compare too well with Data.Tree.AVL, though I've
never measured it to be honest. It's based on "AVL trees" (or rather
trees where left and right sub-tree heights differ by at most 1), but
doesn't seem to use the AVL algorithm itself. IIRC it stores (boxed!)
height in each tree node, not "balance factor". As well as requiring
an extra field (same as Adams) this also causes other inefficiencies.
Insertion requires inspection of nodes which aren't on the insertion
path to determine the balance factor, which has gotta slow things down.

That said, it should still do a pretty good job of balancing and the
balancing mechanism itself and node size will have little impact on
look up times (for example).

It'd be worth a look at to see what functions this provides that
weren't provided by the old FiniteMap implementation, and whether or
not these are still absent from Data.Map (I believe this was the
original motivation for FGL having it's own private implementation in
the first place).

Regards
--
Adrian Hey



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Map for FGL

Adrian Hey
On Monday 09 Jan 2006 6:28 pm, Adrian Hey wrote:
> I suspect it doesn't compare too well with Data.Tree.AVL, though I've
> never measured it to be honest. It's based on "AVL trees" (or rather
> trees where left and right sub-tree heights differ by at most 1), but
> doesn't seem to use the AVL algorithm itself. IIRC it stores (boxed!)
> height in each tree node, not "balance factor". As well as requiring
> an extra field (same as Adams) this also causes other inefficiencies.
> Insertion requires inspection of nodes which aren't on the insertion
> path to determine the balance factor, which has gotta slow things down.

Oh, and not forgeting that it's lazy (no strict fields of seqs)
anywhere. This may be good thing, but I suspect (for AVL trees at
least) it's a bad thing because of the way height/balance information
propogates up the tree.

Regards
--
Adrian Hey

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Map for FGL

Christian Maeder
In reply to this post by Adrian Hey
Adrian Hey wrote:
>
> It'd be worth a look at to see what functions this provides that
> weren't provided by the old FiniteMap implementation, and whether or
> not these are still absent from Data.Map (I believe this was the
> original motivation for FGL having it's own private implementation in
> the first place).

splitFM :: Ord a => FiniteMap a b -> a -> Maybe (FiniteMap a b, (a, b))
combines delFrom and lookup

splitMinFM :: Ord a => FiniteMap a b -> Maybe (FiniteMap a b, (a, b))
combines splitFM and minFM

The above two are special. splitFM could be expressed using
Data.Map.updateLookupWithKey (with one traversal), I think.

splitMinFM corresponds to Data.Map.deleteFindMin

Christian
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Map for FGL

Adrian Hey
In reply to this post by Adrian Hey
On Monday 09 Jan 2006 6:28 pm, Adrian Hey wrote:
> That said, it should still do a pretty good job of balancing and the
> balancing mechanism itself and node size will have little impact on
> look up times (for example).

..or maybe not. Looking at this code again reminds me of something
strange that happened when I tested the RedBlack tree implementation
Chris Okasaki sent me a while back. It required precisely twice as
many comparisons as the RedBlack code Malcolm Wallace supplied.

I'm not sure exactly why, but I suspect it probably had something to
do with the use of either guarded equational style code (or maybe
if then elses) rather than "case compare x y of.." style code.

The FGL implementation seems to do the same thing. So I guess
lookup performance might not be too good either, at least for
non-trivial comparisons.

Regards
--
Adrian Hey



 

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Who needs Ord for Sets and Maps anyway?

Adrian Hey
On Wednesday 11 Jan 2006 7:09 am, Adrian Hey wrote:
> The FGL implementation seems to do the same thing. So I guess
> lookup performance might not be too good either, at least for
> non-trivial comparisons.

Well, speaking of "non-trivial comparisons" reminds me of something
that's been worrying me about this whole approach to implementing
Sets and Maps. I.E. Requiring that element/key types are instances
of Ord and assuming that lookup etc is achieved by performing some
kind of binary search.

This seems wrong in general. E.G. A trie based implementation of
ListSet/ListMap does not require that lists are instances of Ord.
Furthermore, a trie based implementation for Lists is likely
to be very much more efficient than the proposed polymorphic
Sets/Maps based on balanced binary trees, because it avoids
a lot of repeated comparison on the same list element.

What I really want is Sets/Maps that work efficiently where the
element/keys can be arbitrarily complex data structures, so
comparison is non-trivial and typically quite expensive.
(I guess we need to restrict "arbitrarily complex" to
exclude cyclic data structures.)

So couldn't we generalise the idea of tries to work with any data type?

Suppose I wanted a Set or Map of pairs. The obvious implementation
(using current polymorphic Sets/Maps) would be..

-- Set of pairs (a,b)
newtype Set2 a b = Set2 (Map a (Set b))

-- Map of pairs (a,b) to values v
newtype Map2 a b v = Map2 (Map a (Map b v))

.. and for triples ..

-- Set of triples (a,b,c)
newtype Set3 a b c = Set3 (Map a (Set2 b c))
-- or perhaps ..
newtype Set3 a b c = Set3 (Map2 a b (Set c))

-- Map of triples (a,b,c) to values v
newtype Map3 a b c v = Map3 (Map a (Map2 b c v))
-- or perhaps ..
newtype Map3 a b c v = Map3 (Map2 a b (Map c v))

This can obviously be extended for any product type or data
constructor of arbitrary arity. For sum of product types
with N distinct constructors, what's needed is an N-tuple
of product Sets/Maps (one for each constructor), with nullary
constructors just using a simple Bool/Maybe.

So, assuming this scheme can be used to implement Sets/Maps for
any product or algebraic data type, the only real implementation
needed is something like IntSet/IntMap (which could be used for
CharSet/CharMap etc too). We'd probably want a hand generated
implementation for Lists using "proper" tries, but other than
these cases couldn't all this stuff just be derived by the
compiler? (would be nice if it could).

The only problem I see here is the structural equality problem
we've discussed at some length recently. The above scheme assumes
structural equality. If this isn't what's wanted then I guess
we'd have to rely on hand written instances (as is the case with
Eq/Ord).

This also highlights another reason why IMO specifying "biasing"
is bad, because doing this implicitly assumes that Sets/Maps somehow
contain concrete structural representations of elements/keys.
This is not necessarily so. It's not true with any implementation
like that described above (or even simple tries).

Hmm.., just thought of something else. Although this scheme does
not require types to be instances of Ord, it would be nice if
derived or hand written instances of Set/Map were consistent with
any Ord instances, so we could have meaningful ordering with
functions like elemsAscending, foldAscending etc..

elemsAscending :: (Set s e, Ord e) => s e -> [e]
foldAscending :: (Set s e, Ord e) => (e -> a -> a) -> a -> s e -> a

Any comments? Or maybe suggestions about how to use exotic ghc
extensions (about which I understand little) to implement this?
(I know we shouldn't be assuming ghc, in an ideal world :-)

[P.S
 Now of course having written all this I decided this must surely
 have been done already by someone :-) Googling for "generalised
 tries" quickly took me to this paper by Ralf Hinze..

  http://citeseer.ist.psu.edu/233124.html

 which in turn references Chris Okasakis book

So why don't we implement something like this? (somehow:-)
]

Regards
--
Adrian Hey

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Who needs Ord for Sets and Maps anyway?

Okasaki, C. DR   EECS
Adrian Hey wrote:
> Well, speaking of "non-trivial comparisons" reminds me of something
> that's been worrying me about this whole approach to implementing
> Sets and Maps. I.E. Requiring that element/key types are instances
> of Ord and assuming that lookup etc is achieved by performing some
> kind of binary search.
>
> This seems wrong in general. [...]

and

> This also highlights another reason why IMO specifying "biasing"
> is bad, because doing this implicitly assumes that Sets/Maps somehow
> contain concrete structural representations of elements/keys.
> This is not necessarily so. It's not true with any implementation
> like that described above (or even simple tries).

You've just highlighted why the collections hierarchy in Edison was a
lattice of 8 classes.  Basically, there are two choices in each of three
different dimensions:

  1. The set/map distinction
  2. Require Ord or don't (your first point above)
  3. "Observable" or not (your second point above)

I think the last point is the one that caused the most confusion, but it
is exactly the issue you highlight above -- some structures contain the
actual elements/keys, but some (such as tries or sets based on bitmaps)
don't.  The non-observable parts of the hierarchy are there precisely to
support implementations like tries and bitmaps where it is not easy to
get your hands on the actual elements.

-- Chris
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Who needs Ord for Sets and Maps anyway?

Okasaki, C. DR   EECS
In reply to this post by Adrian Hey
[My sincere apologies for the multiple posts.  I forgot to include the
subject line on my previous post, which makes it unclickable in the
archive...]

I wrote:
> You've just highlighted why the collections hierarchy in Edison was a
> lattice of 8 classes.  Basically, there are two choices in each of
> three different dimensions:
>
>  1. The set/map distinction
>  2. Require Ord or don't (your first point above)  3. "Observable" or
> not (your second point above)

Oops, I typed too fast.  Edison actually has two choices in each of four
different dimensions.  The first is the set/map distinction, but those
are in two separate class hierarchies.  Within each of those class
hierarchies, the three dimensions are Ord/not, Observable/not, and
"unique"/not, where the last dimension is the difference between sets
and bags.

-- Chris
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Who needs Ord for Sets and Maps anyway?

Adrian Hey
In reply to this post by Okasaki, C. DR EECS
Hello Chris,

> I think the last point is the one that caused the most confusion, but it
> is exactly the issue you highlight above -- some structures contain the
> actual elements/keys, but some (such as tries or sets based on bitmaps)
> don't.  The non-observable parts of the hierarchy are there precisely to
> support implementations like tries and bitmaps where it is not easy to
> get your hands on the actual elements.

Yes, the more I think about this the more difficult it seems to produce
abstract, polymorphic and efficent Sets/Maps. The Ord/Binary tree
approach really does seem a bit naive to me now (even if it does use
AVL trees :-) But realistic alternatives seem to require the use of
language features that are non-standard (and mostly beyond my grasp
at the moment anyway, but I've never really looked at them seriously).

We can produce specialised implementations for particular types and
include them in standard libs. But this still doesn't address the real
problem (well I think it's the real problem) of how users can easily
produce implementations for their own (non-standard) types. Just
deriving Ord won't be good enough.

Is Edison still being maintained, BTW? I wasn't even aware that is was
distributed (with GHC least) until quite recently. (It seems a pity to
have it languishing in obscurity under hslibs.)

Regards
--
Adrian Hey



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Who needs Ord for Sets and Maps anyway?

ajb@spamcop.net
G'day all.

Quoting Adrian Hey <[hidden email]>:

> Is Edison still being maintained, BTW? I wasn't even aware that is was
> distributed (with GHC least) until quite recently. (It seems a pity to
> have it languishing in obscurity under hslibs.)

I adopted it for a while, but stopped actively maintaining it because
discussion on this list seemed to indicate that nobody really wanted it.

Some day I'm going to cabalise it at least, so that should at least
make it less obscure.

Cheers,
Andrew Bromage
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Who needs Ord for Sets and Maps anyway?

Sebastian Sylvan
On 1/19/06, [hidden email] <[hidden email]> wrote:

> G'day all.
>
> Quoting Adrian Hey <[hidden email]>:
>
> > Is Edison still being maintained, BTW? I wasn't even aware that is was
> > distributed (with GHC least) until quite recently. (It seems a pity to
> > have it languishing in obscurity under hslibs.)
>
> I adopted it for a while, but stopped actively maintaining it because
> discussion on this list seemed to indicate that nobody really wanted it.
>
> Some day I'm going to cabalise it at least, so that should at least
> make it less obscure.

Well, for the record. I think the lack of good "standardised" data
structures is one of the main problems with Haskell (and one of the
easiest to fix). So if you do have the incliniation and time to work
on it, I know I'd sure apreciate it!

A good "standard" class hierarchy for collections and several
implementations is very much needed, IMO.

/S

--
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Who needs Ord for Sets and Maps anyway?

John Meacham
In reply to this post by Adrian Hey
On Wed, Jan 18, 2006 at 09:16:00AM +0000, Adrian Hey wrote:
> We can produce specialised implementations for particular types and
> include them in standard libs. But this still doesn't address the real
> problem (well I think it's the real problem) of how users can easily
> produce implementations for their own (non-standard) types. Just
> deriving Ord won't be good enough.

It would be interesting to use DrIFT to produce generalized Tries from
arbitrary abstract data types. It seems like it should be possible. is
there any literature on this sort of thing? It can probably be done
(less efficiently) with Data.Generics too.
        John

--
John Meacham - ⑆repetae.net⑆john⑈
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Who needs Ord for Sets and Maps anyway?

ajb@spamcop.net
In reply to this post by Sebastian Sylvan
G'day all.

Quoting Sebastian Sylvan <[hidden email]>:

> A good "standard" class hierarchy for collections and several
> implementations is very much needed, IMO.

For the record, the consensus seemed to be that we needed something, but
Edison wasn't it.

One problem that I got bogged down in was the idea that some data structures
most sensibly reside in monads (e.g. IOArrays) and some do not.  A consistent
interface for both proved elusive.

Cheers,
Andrew Bromage
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re[2]: Who needs Ord for Sets and Maps anyway?

Bulat Ziganshin
In reply to this post by John Meacham
Hello John,

Thursday, January 19, 2006, 4:12:00 AM, you wrote:

JM> It would be interesting to use DrIFT to produce generalized Tries from
JM> arbitrary abstract data types. It seems like it should be possible. is
JM> there any literature on this sort of thing? It can probably be done
JM> (less efficiently) with Data.Generics too.

and also with Template Haskell. when i was interested in generic
programmimg with Haskell, i found 7 projects, which can be used for
it:

drift
-fgenerics
TH
generic haskell
polyp
SYB
strafunski



--
Best regards,
 Bulat                            mailto:[hidden email]



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Who needs Ord for Sets and Maps anyway?

Adrian Hey
In reply to this post by John Meacham
Hello

On Thursday 19 Jan 2006 1:12 am, John Meacham wrote:
> It would be interesting to use DrIFT to produce generalized Tries from
> arbitrary abstract data types.

I'm not sure what DrIFT actually does, but it sounds like what you're
suggesting should be interesting. I was thinking it wouldn't be to
hard to write a program that took any Haskell data type definition
(call it MyType) and automatically emitted MyTypeSet and MyTypeMap
generalised trie types and associated functions and class instances.

Of course the problem comes in that having created these types it
should go on to create MyTypeSetSet,MyTypeSetMap,MyTypeMapSet,
MyTypeMapMap..Hmm :-)

Regards
--
Adrian Hey


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re[2]: Who needs Ord for Sets and Maps anyway?

Bulat Ziganshin
In reply to this post by ajb@spamcop.net
Hello ajb,

Thursday, January 19, 2006, 4:47:28 AM, you wrote:

>> A good "standard" class hierarchy for collections and several
>> implementations is very much needed, IMO.

asn> One problem that I got bogged down in was the idea that some data structures
asn> most sensibly reside in monads (e.g. IOArrays) and some do not.  A consistent
asn> interface for both proved elusive.

at least, arrays library have two completely different interfaces for
immutable and mutable arrays, although these interfaces has much in
common and moreover MArray in IO monad can be used to create "differential"
IArray. i think that it is the very good design that just need to be
entirely copied for general collection classes


--
Best regards,
 Bulat                            mailto:[hidden email]



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Who needs Ord for Sets and Maps anyway?

Johannes Waldmann
In reply to this post by ajb@spamcop.net

> Quoting Sebastian Sylvan <[hidden email]>:
>
>> A good "standard" class hierarchy for collections and several
>> implementations is very much needed, IMO.

Yes, yes, and yes. I think the Java collections framework
http://java.sun.com/docs/books/tutorial/collections/index.html
is quite brilliant (regarding both the implementations and the
interface design) and I wonder what keeps us from copying it
as literally as possible. This is not a rhetorical question.

They solve the problem of what comparison method to use for the elements
by providing constructors that have a Comparator<E> object as argument.
What's wrong with that? (Does it solve the problems that were discussed
here recently?)

I fear (or I hope) that the average well-trained Java programmer is way
ahead of the average Haskell programmer when using data structures *and*
hiding them behind interfaces. I've seen too many Haskell sources
(including my own) that use concrete collection/map types (Data.List,
Data.Map)  all over the place where in fact interfaces (see
Collection<E>, List<E> etc.) would be the right thing.

In Haskell, we would need existential types to express that a function
returns "an object of *some* type that implements the (hypothetical) Set
interface". I guess the notational extra work for that is the main
reason (at least for me) for wrongly preferring concrete datatypes
over abstract types in Haskell.

PS (I know this is heresy but - can we please in Haskell-0X rename
"class" to "interface" so that the non-Haskell world knows what we're
talking about. You know if the mountain's not gonna walk to the prophet,
then ...) (note that I'm currently not proposing to rename "data" to
"class". But looking at GADT data definitions still makes me wonder...)
--
-- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 --
---- http://www.imn.htwk-leipzig.de/~waldmann/ -------

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Who needs Ord for Sets and Maps anyway?

Jean-Philippe Bernardy
On 1/19/06, Johannes Waldmann <[hidden email]> wrote:

>
> > Quoting Sebastian Sylvan <[hidden email]>:
> >
> >> A good "standard" class hierarchy for collections and several
> >> implementations is very much needed, IMO.
>
> Yes, yes, and yes. I think the Java collections framework
> http://java.sun.com/docs/books/tutorial/collections/index.html
> is quite brilliant (regarding both the implementations and the
> interface design) and I wonder what keeps us from copying it
> as literally as possible. This is not a rhetorical question.

A lot of things differ between haskell and java. The type system, the
undelying paradigms are different. We can use the java collections as
a source of inspiration, but merely copying is impractical.

> They solve the problem of what comparison method to use for the elements
> by providing constructors that have a Comparator<E> object as argument.
> What's wrong with that? (Does it solve the problems that were discussed
> here recently?)

What if we do the union of two Sets constructed with different comparators ?

> I fear (or I hope) that the average well-trained Java programmer is way
> ahead of the average Haskell programmer when using data structures *and*
> hiding them behind interfaces. I've seen too many Haskell sources
> (including my own) that use concrete collection/map types (Data.List,
> Data.Map)  all over the place where in fact interfaces (see
> Collection<E>, List<E> etc.) would be the right thing.

Haskell has a long tradition of using concrete lists. Breaking from
that tradition involves quite a lot of problems.

If you wish, I suggest to look at Robert Will's "Dessy", which
implements something close to that.

> In Haskell, we would need existential types to express that a function
> returns "an object of *some* type that implements the (hypothetical) Set
> interface". I guess the notational extra work for that is the main
> reason (at least for me) for wrongly preferring concrete datatypes
> over abstract types in Haskell.

If I understand correctly, those are unrelated issues. We can
parameterize over the collection type using the usual Haskell
mechanisms (no need for subtyping).

> PS (I know this is heresy but - can we please in Haskell-0X rename
> "class" to "interface" so that the non-Haskell world knows what we're
> talking about. You know if the mountain's not gonna walk to the prophet,
> then ...) (note that I'm currently not proposing to rename "data" to
> "class". But looking at GADT data definitions still makes me wonder...)

Haskell is just different; if one can't get beyond lexical issues,
there's IMHO no hope to make the paradigm shift needed to write good
haskell.

Cheers,
JP.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Who needs Ord for Sets and Maps anyway?

Johannes Waldmann
Jean-Phillipe Bernardy wrote:

> What if we do the union of two Sets constructed with different comparators ?

The union of two ordered sets with different specifactions
for their (externally visible) structure (ordering) is not defined.
Or rather, it is up to the user to specify explicitely what he wants
(i. e. name the comparator for the result).

Or do you mean that an implementation of "union" could be more efficient
if both sets have the same internal representation (e. g. balanced
tree). A Java implementation would probably use "instanceof"
to check for that. With the current framework and Sun's implementation,
the TreeSet implementation (Red-Black trees) does not have a specialiced
implementation of "addAll", as far as I could see.

The underlying question is: what should be the type of "union".
Java: interface Collection<E> { addAll(Collection<? extends E> c) }
naive Haskell: class Collection c where union :: c e -> c e -> c e
The Java thing is existential: each implementation of addAll
has to accept *any* collection as an argument,
while the Haskell implementation knows that both arguments
have identical representation.  So the Java version is more
flexible for the user of the library. One could try
class Collection c where union :: Collection d => c e -> d e -> c e
and use a specialized implementation for  c e -> c e -> c e.

This works for arguments of functions,
but what about a function that by design returns "any" collection,
without telling the caller about the implementation.
Then we sure have to wrap it up in an existential type?
My point is that hiding the implementation is actually the recommended
coding style (not just for Java) but it is syntactically inconvenient in
Haskell. But perhaps I missed something.

Best regards,
--
-- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 --
---- http://www.imn.htwk-leipzig.de/~waldmann/ -------

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Who needs Ord for Sets and Maps anyway?

Jean-Philippe Bernardy
On 1/19/06, Johannes Waldmann <[hidden email]> wrote:

> The union of two ordered sets with different specifactions
> for their (externally visible) structure (ordering) is not defined.
> Or rather, it is up to the user to specify explicitely what he wants
> (i. e. name the comparator for the result).
>
> Or do you mean that an implementation of "union" could be more efficient
> if both sets have the same internal representation (e. g. balanced
> tree). A Java implementation would probably use "instanceof"
> to check for that. With the current framework and Sun's implementation,
> the TreeSet implementation (Red-Black trees) does not have a specialiced
> implementation of "addAll", as far as I could see.
>
> The underlying question is: what should be the type of "union".
> Java: interface Collection<E> { addAll(Collection<? extends E> c) }
> naive Haskell: class Collection c where union :: c e -> c e -> c e
> The Java thing is existential: each implementation of addAll
> has to accept *any* collection as an argument,
> while the Haskell implementation knows that both arguments
> have identical representation.  So the Java version is more
> flexible for the user of the library. One could try
> class Collection c where union :: Collection d => c e -> d e -> c e
> and use a specialized implementation for  c e -> c e -> c e.

I see your point now. However, I suspect the homogeneous typing is
less surprising for the user. It is also much more inline with the
haskell style. See for example, Num class:
(+) :: a -> a -> a

> This works for arguments of functions,
> but what about a function that by design returns "any" collection,
> without telling the caller about the implementation.
> Then we sure have to wrap it up in an existential type?
> My point is that hiding the implementation is actually the recommended
> coding style (not just for Java) but it is syntactically inconvenient in
> Haskell. But perhaps I missed something.

Subtyping and binary methods is not something so obvious... And
certainly I do not want to emulate the java solution with existential
types :)

In any case, please don't confuse implementation hiding and
polymorphism. Those are mixed in most OO languages, and indeed in
java, but separated in haskell. For example, Data.Set is
"monomorphic", but still an abstract data type (one cannot observe the
internal structure, and indeed we are considering changing it)

Cheers,
JP.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
12