The container problem

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

The container problem

Andrew Coppin
Take a look around you. Haskell provides several sorts of container. We
have:

  Data.List
  Data.Set
  Data.Map
  Data.Hashtable
  Data.ByteString
  Data.Sequence
  Data.Array
  Data.Tree
  Data.IntSet
  Data.IntMap
  ...

In other words, we have *a lot* of different data containers. And yet,
each one provides its own unique API.

To anybody used to OO languages, that sounds pretty crazy. In something
like Java or Smalltalk or Eiffel, you have an abstract class that
represents "container", and maybe a seperate one for "ordered
container", and then concrete subclasses for each kind of container.
Each one may add a few unique methods of its own, but basically all the
containers have a uniform API, and you can write functions that work for
any arbitrary [ordered] container.

In Haskell, you can't do this. Why is that?

To me, it seems that there are two sticking points:

1. Historical reasons.

2. The Haskell '98 type system.

(1) is obviously solvable. (2) is harder.

Some containers can contain *any* type of data. Haskell permits
parametric polymorphism, so this is no problem:

  Data.List.map :: (a -> b) -> [a] -> [b]

Other containers only support *one* type of data:

  Data.ByteString.Char8.map :: (Char -> Char) -> ByteString -> ByteString

The type has a different kind, and the function parameter's type is more
constrained. Yet still this poses no problem.

However... now try writing a class that both of these functions could be
methods of. Good luck with that, by the way...

This is AFAIK also the reason why, e.g., Set is *not* an instance of
Monad; you can't write a valid instance. The type checker won't have it.

To ears accustomed to the OO way, all this makes it sound like Haskell's
type system sucks. (Which is rich, because in half the OO languages, you
can't write a type-safe container that works for arbitrary element types
in the first place! Haskell is a Big Win here.)

If I understand this correctly, to solve this problem you need either
Functional Dependencies or Associated Types. Is that correct?

I also gather that "FDs have problems" - although I have no idea what
those problems are. Everybody's hoping that ATs will fix this, but ATs
are still kinda new. (Are they even fully implemented in GHC yet?)

Can anybody correct/expand on this state of affires? I just want to make
sure I understand our position correctly...

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

Re: The container problem

Albert Y. C. Lai
Andrew Coppin wrote:
> If I understand this correctly, to solve this problem you need either
> Functional Dependencies or Associated Types. Is that correct?

A motivating example in papers on FD is exactly typeclasses for
containers. Okasaki puts this into practice in the Edison library.
Despite its comprehensiveness, elegance, and the Okasaki name brand, it
did not become mainstream. I don't know why.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: The container problem

Achim Schneider
In reply to this post by Andrew Coppin
Andrew Coppin <[hidden email]> wrote:

> [...]
I completely agree that Hashtable should instance Map and alike.

>   Data.List.map :: (a -> b) -> [a] -> [b]
>
> Other containers only support *one* type of data:
>
>   Data.ByteString.Char8.map :: (Char -> Char) -> ByteString ->
> ByteString
>
> The type has a different kind, and the function parameter's type is
> more constrained. Yet still this poses no problem.
>
> However... now try writing a class that both of these functions could
> be methods of. Good luck with that, by the way...
>
Well the type _could_ be
map :: (a -> b) -> ByteString a -> ByteString b
and have a hell a lot of plumbing that utterly destroys ByteString's
optimisation.

But then you'll be happy to know that there's already Data.Stream.List,
with more coming at the same speed as we can order pizza for dons.

http://hackage.haskell.org/trac/ghc/ticket/915


--
(c) this sig last receiving data processing entity. Inspect headers
for copyright history. All rights reserved. Copying, hiring, renting,
performance and/or broadcasting of this signature prohibited.

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

Re: Re: The container problem

Dougal Stanton-2
On Fri, Sep 26, 2008 at 8:01 PM, Achim Schneider <[hidden email]> wrote:

>
> But then you'll be happy to know that there's already Data.Stream.List,
> with more coming at the same speed as we can order pizza for dons.
>
> http://hackage.haskell.org/trac/ghc/ticket/915
>

I was hoping that ticket would reveal the delivery address that we had
to send pizza to, but instead it revealed that streams stuff is not
scheduled for inclusion until GHC 6.12. :-(

Cheers,

D
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: The container problem

John Van Enk
> ...revealed that streams stuff is not scheduled for inclusion until GHC 6.12

How many pizzas will it take to bump that to 6.10? :D

On Fri, Sep 26, 2008 at 3:23 PM, Dougal Stanton <[hidden email]> wrote:
On Fri, Sep 26, 2008 at 8:01 PM, Achim Schneider <[hidden email]> wrote:

>
> But then you'll be happy to know that there's already Data.Stream.List,
> with more coming at the same speed as we can order pizza for dons.
>
> http://hackage.haskell.org/trac/ghc/ticket/915
>

I was hoping that ticket would reveal the delivery address that we had
to send pizza to, but instead it revealed that streams stuff is not
scheduled for inclusion until GHC 6.12. :-(

Cheers,

D
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



--
/jve

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

Re: Re: The container problem

Andrew Coppin
John Van Enk wrote:
> > ...revealed that streams stuff is not scheduled for inclusion until
> GHC 6.12
>
> How many pizzas will it take to bump that to 6.10? :D
So basically Don is like the dining philosophers, except instead of
turning spaghetti into philosophy, he turns pizza into world-beating
Haskell awesomeness?

Damn, we need to pool our resources and buy more pizza, people!! o_O

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

Re: Re: The container problem

Andrew Coppin
In reply to this post by Dougal Stanton-2
Dougal Stanton wrote:
> I was hoping that ticket would reveal the delivery address that we had
> to send pizza to, but instead it revealed that streams stuff is not
> scheduled for inclusion until GHC 6.12. :-(
>  

As I understand it, the [list] stream-fusion library is on Hackage
*now*, you can use it *now*. They just want to wait awhile and benchmark
it a bit more before making it the GHC default.

...is how *I* understood things. Clarification, anybody?

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

Re: Re: The container problem

John Van Enk
In reply to this post by Andrew Coppin
Does the quality of the pizza matter, or is it a matter of sheer quantity? If it's a balance of the two, then we need to do some experimentation.

Lets start donating a specific quantity of pizzas to Don every week, but vary the quality of the pizza. We'll check his Hackage submissions and then tune the pizza algorithm to the desired output. :)

On Fri, Sep 26, 2008 at 3:39 PM, Andrew Coppin <[hidden email]> wrote:
John Van Enk wrote:
> ...revealed that streams stuff is not scheduled for inclusion until GHC 6.12

How many pizzas will it take to bump that to 6.10? :D
So basically Don is like the dining philosophers, except instead of turning spaghetti into philosophy, he turns pizza into world-beating Haskell awesomeness?

Damn, we need to pool our resources and buy more pizza, people!! o_O


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



--
/jve

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

Re: The container problem

Achim Schneider
In reply to this post by Andrew Coppin
Andrew Coppin <[hidden email]> wrote:

> John Van Enk wrote:
>
> So basically Don is like the dining philosophers, except instead of
> turning spaghetti into philosophy, he turns pizza into world-beating
> Haskell awesomeness?
>
Is that the problem where you have to calculate the probability of
the pizza arriving pre-cut as ordered based on the true and pretended
availability of knives and pizza cutters at the delivery address?

--
(c) this sig last receiving data processing entity. Inspect headers
for copyright history. All rights reserved. Copying, hiring, renting,
performance and/or broadcasting of this signature prohibited.

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

Re: The container problem

Derek Elkins
In reply to this post by Andrew Coppin
On Fri, 2008-09-26 at 19:15 +0100, Andrew Coppin wrote:

> Take a look around you. Haskell provides several sorts of container. We
> have:
>
>   Data.List
>   Data.Set
>   Data.Map
>   Data.Hashtable
>   Data.ByteString
>   Data.Sequence
>   Data.Array
>   Data.Tree
>   Data.IntSet
>   Data.IntMap
>   ...
>
> In other words, we have *a lot* of different data containers. And yet,
> each one provides its own unique API.
>
> To anybody used to OO languages, that sounds pretty crazy. In something
> like Java or Smalltalk or Eiffel, you have an abstract class that
> represents "container", and maybe a seperate one for "ordered
> container", and then concrete subclasses for each kind of container.
> Each one may add a few unique methods of its own, but basically all the
> containers have a uniform API, and you can write functions that work for
> any arbitrary [ordered] container.
>
> In Haskell, you can't do this. Why is that?

Obviously you certainly can.  That there isn't a "standard" form is in
my opinion not really historical or limitations of H98, though there are
certainly some aspect of those.  You can do a not horrible job in just
H98.  You can do a much better job using common extensions (and yes, in
particular MPTCs and fundeps.)  As Albert Lai alluded to, you can use
Edison if you want this, right now, today.  I think the problem is again
that the Perfect Interface hasn't been found and for several reasons
which I'll enumerate, there is not a pressing desire for a reasonable
compromise.

One aspect of it is a bit of a You Aren't Going To Need It.
Particularly for applications, there is usually very little gain in
practice and for Haskell many of the container libraries have identical
interface subsets so that you do end up being able to change
implementation by changing a single import.  This is further reinforced
by there being a single obvious choice for common data structures.
Admittedly, it would still be nice to be more explicit about this and to
program to interfaces, especially for library code.

Another reason is that often you can use an intermediate data structure,
especially lists, for operations.  Lists are the
iterators/IEnumerable/generators of Haskell.  So if I just need to
traverse a data structure, I can just write an interface that accepts a
list.

Of course, since Haskell isn't Java, I'm not subject to the choice of
interfaces the data structure implementer decided to implement or not.
When this happens in Java the "standard" solution is to use an adapter
class.  In Haskell, I can just write the instance.  In particular, I can
decide on whatever interface I need, write my code to that interface and
just instantiate it for the relevant data types and users can
instantiate it for their data types.  If you want an OrderableCollection
class, you can simply write one today.  You don't need to ask anyone's
permission or coordinate with anyone.

There are some general reasons too.  Typically asymptotic complexity
guarantees are considered part of the interface for a data structure.
If you do this you either end up with loose constraints that aren't very
useful or tight ones that provide nice guarantees but exclude all but a
few data structures.  This leads back to the first reason, YAGNI.  You
often have particular properties that you want and thus end up with
particular data structures.  Admittedly, you can still require tight
complexity constraints and if someone wants to violate them, the
performance problems are their fault but maybe convenience outweighs
performance in that case.  Usually, though, there are convenient
conversions between the types.

Finally, there -are- several more or less standard classes that capture
different general operations on data structures (though there certainly
could be more.) They, of course, have different names and different
interfaces and different factorings from imperative equivalents.  We
have Functor, Applicative, Monad, MonadPlus, Monoid, Foldable,
Traversable, IArray, MArray and others.  Notice how the ridiculous
proliferation of array types in Haskell has pressed the issue and led to
the creation of IArray and MArray.

Ultimately, it would still be beneficial to have some more standard
interfaces for this sort of thing.  There just hasn't been enough of a
fire under the community's rear.  This again suggests that YAGNI.

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

Re: The container problem

Andrew Coppin
Derek Elkins wrote:
> One aspect of it is a bit of a You Aren't Going To Need It.
>  

Personally, I haven't had a huge problem with this in practice.

What it basically means is that if you write a library function, *you*
have to decide what containers you're going to use. It's not really
possible to let the user decide. You kind of have to hard-wire it
yourself. That's the only real problem with it. Sometimes it's
irritating to convert an array to a list, feed it to some function, and
then immediately convert it back to an array again, for example. (Not
only annoying, but presumably not that efficient.)

> Another reason is that often you can use an intermediate data structure,
> especially lists, for operations.  Lists are the
> iterators/IEnumerable/generators of Haskell.  So if I just need to
> traverse a data structure, I can just write an interface that accepts a
> list.
>  

This is the other part of it. In Haskell, a list in some sense "is" a
control-flow loop. If the compiler's inlining is half as good as it's
supposed to be, converting an array to a list and then feeding it to
some function hopefully ends up being inlined so that you end up with
the function directly iterating over the array. Hopefully the function's
output ends up being similar. So it's not like you build a while list in
memory and then consume it. It's not even like the GC has to go round
and free all the list cells. The list itself never actually exists as
such at runtime.

Alternatively, I'm talking complete nonesense... o_O

> Of course, since Haskell isn't Java, I'm not subject to the choice of
> interfaces the data structure implementer decided to implement or not.
> When this happens in Java the "standard" solution is to use an adapter
> class.  In Haskell, I can just write the instance.  In particular, I can
> decide on whatever interface I need, write my code to that interface and
> just instantiate it for the relevant data types and users can
> instantiate it for their data types.  If you want an OrderableCollection
> class, you can simply write one today.  You don't need to ask anyone's
> permission or coordinate with anyone.
>  

Haskell class membership is "open" in this way - a useful feature, IMHO.

> Finally, there -are- several more or less standard classes that capture
> different general operations on data structures (though there certainly
> could be more.) They, of course, have different names and different
> interfaces and different factorings from imperative equivalents.  We
> have Functor, Applicative, Monad, MonadPlus, Monoid, Foldable,
> Traversable, IArray, MArray and others.  Notice how the ridiculous
> proliferation of array types in Haskell has pressed the issue and led to
> the creation of IArray and MArray.
>  

As already noted, Data.Set *should* be a Monad, but can't be. The type
system won't allow it. (And I know I'm not the first person to notice
this...) Similar fun and frolics with Functor, and presumably
Applicative and Foldable (I haven't actually heard of these until just now).

Frankly, the whole "array" thing is slightly crazy to me. There are
several things which the array libraries ought to support, but don't:
- Making "slices" of arrays. (I.e., generating a subarray in O(1) by
using transparent reindexing.)
- Linked lists of arrays that provide an array-like interface.
(ByteString.Lazy does this, but only for Word8 or Char.)
- It really ought to be possible to unbox *any* type. Technically this
is implementable now, but I can't find details of how...
- Performing "map" in-place for mutable arrays. (This must surely be a
very common operation.)
- Build-in functions for joining arrays together, and splitting at a
given index.
- Array sorting. [Arrays have O(1) indexing, which has big implications
for what sorting algorithm to choose.]
- Lists have about 5,000,000 functions for processing them. Arrays have,
like, a dozen. Just how efficient is it to convert an array to a list,
process it, and then convert it back?

> Ultimately, it would still be beneficial to have some more standard
> interfaces for this sort of thing.  There just hasn't been enough of a
> fire under the community's rear.  This again suggests that YAGNI.
>  

I see... ;-)

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

Re: The container problem

David Menendez-2
On Fri, Sep 26, 2008 at 5:37 PM, Andrew Coppin
<[hidden email]> wrote:
>
> As already noted, Data.Set *should* be a Monad, but can't be. The type
> system won't allow it. (And I know I'm not the first person to notice
> this...)

I wouldn't say that. It's important to remember that Haskell class
Monad does not, and can not, represent *all* monads, only (strong)
monads built on a functor from the category of Haskell types and
functions to itself.

Data.Set is a functor from the category of Haskell types *with
decidable ordering* and *order-preserving* functions to itself. That's
not the same category, although it is closely related.

--
Dave Menendez <[hidden email]>
<http://www.eyrie.org/~zednenem/>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: The container problem

Jason Dusek
  Can someone explain, why is it that Set can not be a Monad?

--
_jsn
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: The container problem

Bugzilla from jonathanccast@fastmail.fm
On Fri, 2008-09-26 at 15:25 -0700, Jason Dusek wrote:
> Can someone explain, why is it that Set can not be a Monad?

It can't even be a functor (which all monads are).  You can't implement

    fmap (+) $ Set.fromList [1, 2, 3]

with Data.Set, because you can't order functions of type Integer ->
Integer in a non-arbitrary way.  So you can't have a balanced binary
tree of them in a non-arbitrary way, either.  Something like

    fmap putStrLn $ Set.fromList ["Hello", "world"]

is similar.

Since Data.Set is implemented in Haskell, it can only use facilities
available to Haskell libraries.  So it can't work for arbitrary
elements; but a Functor instance requires that it does work.

jcc


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

Re[2]: The container problem

Bulat Ziganshin-2
In reply to this post by Andrew Coppin
Hello Andrew,

Saturday, September 27, 2008, 1:37:12 AM, you wrote:

answering your questions

1) there is 2 libs providing common Java-like interfaces to
containers: Edison and Collections. almost noone uses it

2) having common type class for various things is most important when
you write library that whould be able to deal with any if these
things. when you just write application program, having the same
interface plus ability to change imports in most cases are enough. and
such meta-libraries are rather rare in Haskell world

3) as laready said, we have classes for traversing containers that
probably covers most of usage scenarios for Java too

now about arrays - they are much less used in Haskell than in
imperative languages, especially mutable ones. to some degree, you may
use parallel arrays, which are still informally supported, to some
degree you may add required operations yourself (array package is
pretty basic), and for some of your operations you need to provide
more advanced array datastructure supporting slicing. try to use lists
when something you need cannot be implemented with arrays. of my
10kloc "realworld" program, i had only one place when arrays are used

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

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

Re: The container problem

Dan Weston
In reply to this post by Bugzilla from jonathanccast@fastmail.fm
More specifically, although a set is a perfectly good (lowercase)
functor, Set is not a (Haskell) Functor.

Set's map has an Ord constraint, but the Functor type constructor is
parametric over *all* types, not just that proper subset of them that
have a total ordering.

But see attempts to fix this:

http://okmij.org/ftp/Haskell/types.html#restricted-datatypes
http://www.randomhacks.net/articles/2007/03/15/data-set-monad-haskell-macros

Dan

Jonathan Cast wrote:

> On Fri, 2008-09-26 at 15:25 -0700, Jason Dusek wrote:
>> Can someone explain, why is it that Set can not be a Monad?
>
> It can't even be a functor (which all monads are).  You can't implement
>
>     fmap (+) $ Set.fromList [1, 2, 3]
>
> with Data.Set, because you can't order functions of type Integer ->
> Integer in a non-arbitrary way.  So you can't have a balanced binary
> tree of them in a non-arbitrary way, either.  Something like
>
>     fmap putStrLn $ Set.fromList ["Hello", "world"]
>
> is similar.
>
> Since Data.Set is implemented in Haskell, it can only use facilities
> available to Haskell libraries.  So it can't work for arbitrary
> elements; but a Functor instance requires that it does work.

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

Re: The container problem

Don Stewart-2
In reply to this post by Bulat Ziganshin-2
bulat.ziganshin:

> Hello Andrew,
>
> Saturday, September 27, 2008, 1:37:12 AM, you wrote:
>
> answering your questions
>
> 1) there is 2 libs providing common Java-like interfaces to
> containers: Edison and Collections. almost noone uses it
>
> 2) having common type class for various things is most important when
> you write library that whould be able to deal with any if these
> things. when you just write application program, having the same
> interface plus ability to change imports in most cases are enough. and
> such meta-libraries are rather rare in Haskell world
>
> 3) as laready said, we have classes for traversing containers that
> probably covers most of usage scenarios for Java too
>
> now about arrays - they are much less used in Haskell than in
> imperative languages, especially mutable ones. to some degree, you may
> use parallel arrays, which are still informally supported, to some
> degree you may add required operations yourself (array package is
> pretty basic), and for some of your operations you need to provide
> more advanced array datastructure supporting slicing. try to use lists
> when something you need cannot be implemented with arrays. of my
> 10kloc "realworld" program, i had only one place when arrays are used

Bulat, have you looked at any of the newer array libraries, such as
uvector, vector, carray or hmatrix?

I'd be interested what you think of them. Especially uvector's
interface.

-- Don
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: The container problem

Brandon S Allbery KF8NH
In reply to this post by John Van Enk
On 2008 Sep 26, at 15:42, John Van Enk wrote:
Lets start donating a specific quantity of pizzas to Don every week, but vary the quality of the pizza. We'll check his Hackage submissions and then tune the pizza algorithm to the desired output. :)

Premature optimization is the root of all evil.  :)

-- 
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [hidden email]
system administrator [openafs,heimdal,too many hats] [hidden email]
electrical and computer engineering, carnegie mellon university    KF8NH



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

Re: The container problem

Derek Elkins
In reply to this post by Andrew Coppin
On Fri, 2008-09-26 at 22:37 +0100, Andrew Coppin wrote:
> Derek Elkins wrote:
> > One aspect of it is a bit of a You Aren't Going To Need It.
> >  
>
> Personally, I haven't had a huge problem with this in practice.

I suspected as much.  Personally I'd recomend worrying about the
problems you actually encounter, rather than worrying about problems
that maybe you'll have later.  Solving problems that you don't have
isn't very gratifying for you.

> > Finally, there -are- several more or less standard classes that capture
> > different general operations on data structures (though there certainly
> > could be more.) They, of course, have different names and different
> > interfaces and different factorings from imperative equivalents.  We
> > have Functor, Applicative, Monad, MonadPlus, Monoid, Foldable,
> > Traversable, IArray, MArray and others.  Notice how the ridiculous
> > proliferation of array types in Haskell has pressed the issue and led to
> > the creation of IArray and MArray.
> >  
>
> As already noted, Data.Set *should* be a Monad, but can't be.

No it shouldn't.  Data.Set forms a categorical monad but not one over
Haskell which is what the Monad class expresses.  Data.Set doesn't meet
the interface of Monad and doesn't provide the same guarantees.
Incidentally, Java would have the same problem if it was capable of
expressing something equivalent to the Monad type class; the "issue" is
with parametric polymorphism not type classes. So unsurprisingly the
type system is right because, in my opinion, parametricity is a property
to valuable to lose.  ´╗┐This does have the effect, however, that join
corresponds to the useful function unions with it's same definition only
using different "monad" operations.  Note that, for this particular
example there is a beautiful solution.  We don't really need to take the
union of a -Set- of Sets, all we need to be able to do is traverse the
outer structure.  Taking a hint from my previous reply, we could
specialize to lists and we would end up with mconcat from the Data.Set
instance of Data.Monoid.  If we didn't feel like imposing the conversion
to lists on the user we could write combine = mconcat . toList.
Conveniently, Data.Foldable has a generic toList function, however, even
more conveniently the function we're looking for is simply
Data.Foldable.fold.

> The type
> system won't allow it. (And I know I'm not the first person to notice
> this...) Similar fun and frolics with Functor, and presumably
> Applicative and Foldable (I haven't actually heard of these until just now).
>
> Frankly, the whole "array" thing is slightly crazy to me. There are
> several things which the array libraries ought to support, but don't:


> - Making "slices" of arrays. (I.e., generating a subarray in O(1) by
> using transparent reindexing.)
> - Linked lists of arrays that provide an array-like interface.
> (ByteString.Lazy does this, but only for Word8 or Char.)
> - It really ought to be possible to unbox *any* type. Technically this
> is implementable now, but I can't find details of how...
> - Performing "map" in-place for mutable arrays. (This must surely be a
> very common operation.)
> - Build-in functions for joining arrays together, and splitting at a
> given index.
> - Array sorting. [Arrays have O(1) indexing, which has big implications
> for what sorting algorithm to choose.]
> - Lists have about 5,000,000 functions for processing them. Arrays have,
> like, a dozen. Just how efficient is it to convert an array to a list,
> process it, and then convert it back?

´╗┐With the exception of slicing, none of these are interface issues and
thus are irrelevant to the topic of this thread.  All the functions you
want can be implemented with reasonable efficiency and correct
asymptotic complexity in terms of the provided interface.  Whether these
functions are in the standard library or not has no effect on the
contractual obligations between chunks of code.  Slicing can't be
implemented with the correct asymptotic behaviour in terms of these
operations.  So then it comes down to a cost/benefit analysis of whether
the cost of adding it to the interface is justified by the benefits of
being able to slice generically.  In this case, I think the scales tilt
in favor of adding such support.


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

Re: The container problem

Andrew Coppin
In reply to this post by David Menendez-2
David Menendez wrote:

>
> I wouldn't say that. It's important to remember that Haskell class
> Monad does not, and can not, represent *all* monads, only (strong)
> monads built on a functor from the category of Haskell types and
> functions to itself.
>
> Data.Set is a functor from the category of Haskell types *with
> decidable ordering* and *order-preserving* functions to itself. That's
> not the same category, although it is closely related.
>  

I nominate this post for the September 2008 Most Incomprehensible Cafe
Post award! :-D

Seriously, that sounded like gibberish. (But then, you're talking to
somebody who can't figure out the difference between a set and a class,
so...)

All I know is that sometimes I write stuff in the list monad when the
result really ought to be *sets*, not lists, because

1. there is no senamically important ordering

2. there should be no duplicates

But Haskell's type system forbids me. (It also forbids me from making
Set into a Functor, actually... so no fmap for you!)



PS. Text is unpredictable, so just in case... If this post sounds like a
flame, it isn't meant to be. ;-)

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
12