[Haskell-cafe] The type class wilderness + Separating instances and implementations into separate packages

[Ryan Newton]

What is the right interface for a queue?  What is the right interface for a
random number generator?

I don't know, but in both cases you will find many packages on hackage
offering different takes on the matter.  In fact, there is a wilderness of
alternative interfaces.  We've had various discussions on this list about
the number of alternative packages.

I'm fine with lots of packages, but I think it would be great if not every
package introduced a new interface as well as a new implementation.  If we
could agree as a community on common interfaces to use for some basics,
that would probably go a long way towards taming the type class wilderness.
 People have mentioned this problem before with respect to "Collections"
generally.

One basic part of reaching such a goal is separating interface from
implementation.  I ran into the following problems just  in the last 24
hours.  In both cases I wanted to use a type class, but didn't want to
depend on the whole package it lived in:

   - I wanted to use the Benchmarkable class in Criterion in my package.
    (Criterion deserving to be a "standard" package.)  But I can't get that
   typeclass without depending on the whole Criterion package, which has
   several dependencies.  And in fact on the machine I was on at the time some
   of those dependencies were broken, so I decided not to use Benchmarkable.
   - I wanted to use, or at least support, an existing class for Queues.  I
   found the following:

http://hackage.haskell.org/packages/archive/queuelike/1.0.9/doc/html/Data-MQueue-Class.html

I have no idea who uses this package.  But because this package (like most
packages) includes the implementation along with the interface it
introduces additional dependency liabilities.  In this case it failed to
build on GHC 7.2 so I quickly gave up on supporting that TypeClass.

How can we enumerate packages that at least purport to provide standard
interfaces that you should both use and pick up to implement?  On a Wiki
page?

  -Ryan

P.S. I'm working on mutable concurrent Deques right now and am trying to
follow my own prescription above by creating an abstract interface in a
separate package.  See below if you would like to offer feedback on that
interface.

--------------------------------------

My ultimate goal is an "abstract-deque" parameterizable interface that
abstracts over bounded/unbounded, concurrent/non-concurrent, single, 1.5,
and double-ended queues, which would include both, say, Michael & Scott
linked queues and the Chase-Lev work-stealing deques.  An aggregated queue
package could use type families to dispatch to the best available queue
implementation for a given configuration.

I've got a couple drafts of how this might work.  They're in different
branches here:


https://github.com/rrnewton/haskell-lockfree-queue/blob/master/AbstractDeque/Data/Concurrent/Deque/Class.hs

https://github.com/rrnewton/haskell-lockfree-queue/blob/one-type-class/AbstractDeque/Data/Concurrent/Deque/Class.hs

One of them uses an associated data type family, the other an unassociated
one.  The type family has a bunch (six) phantom type parameters, and
the unassociated one allows hiding those parameters at the expense of
introducing more type classes.

MegaQueue.hs will be used to aggregate together different queue
implementations.  The end result is that someone can create a new queue by
setting all the switches on the type, as follows:

 test = do
     q :: Deque NT T SingleEnd SingleEnd Bound Safe Int <- newQ
     pushL q 33
     x <- tryPopR q
     print x
     return q

With those settings, requiring only single-ended rather than double-ended
queues, the above code can use the LinkedQueue (Michael and
Scott) implementation included in that repo.
   That little test, by the way, segfaults for me on Mac OS under GHC 7.2.1
even WITHOUT using casMutVar# (It's using Data.CAS.Fake presently.)  I'll
file a bug report after I sanity check it some more.

Disregarding that... the big problem in this case is the* inability to
create overlapping type family instances.  *

In this case what we dearly WANT to do is specialize some subset of the
64-mode configuration space and then have a "fallback".  You can take a
look at my struggling in MegaDeque.  Both of my approaches require
specifying explicitly the modes that you don't cover.

Worse, we may want to specialize on element type as well.  For example, for
simple scalar types (or even Storable types) it may be desirable to use
something foreign, like TBB queues.  But in that case, there's no way to
enumerate the types NOT specialized.  As far as I know there is no way for
type families to accomplish this (specialize, say "Int", and have a
fallback for everything else).  In general, is there a recognized
work-around for this?  For example, is this a place where using functional
dependencies instead might do the trick?

Also, there are some software-engineering issues here with respect to* where
to put the instances*.  It would be nice to put the instances for
DequeClass inside the individual implementations (like LinkedQueue.hs).
 But that leads to problems because it's really the job of MegaQueue.hs to
figure out how to spread implementations over the configuration-space.  And
once you put the instances in LinkedQueue.hs there is of course *no way to
qualify or hide them upon import....*

Feedback welcome.

Cheers,
  -Ryan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111102/d757d678/attachment.htm>