<div>What is the right interface for a queue?  What is the right interface for a random number generator?</div><div><br></div><div>I don&#39;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&#39;ve had various discussions on this list about the number of alternative packages.</div>

<div><br></div><div>I&#39;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 &quot;Collections&quot; generally.</div>


<div><br></div><div><div><div>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&#39;t want to depend on the whole package it lived in:</div>

</div></div><div><ul><li>I wanted to use the Benchmarkable class in Criterion in my package.  (Criterion deserving to be a &quot;standard&quot; package.)  But I can&#39;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.</li>


<li>I wanted to use, or at least support, an existing class for Queues.  I found the following:</li></ul><div><a href="http://hackage.haskell.org/packages/archive/queuelike/1.0.9/doc/html/Data-MQueue-Class.html" target="_blank">http://hackage.haskell.org/packages/archive/queuelike/1.0.9/doc/html/Data-MQueue-Class.html</a></div>


</div><div><br></div><div>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.</div>


<div><br></div><div>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?</div><div><br></div><div>  -Ryan</div><div><br></div>

<div>P.S. I&#39;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.</div>

<div><br></div><div>--------------------------------------</div><div><br></div><div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">My ultimate goal is an &quot;abstract-deque&quot; parameterizable interface that abstracts over bounded/unbounded, concurrent/non-concurrent, single, 1.5, and double-ended queues, which would include both, say, Michael &amp; 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.</div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">I&#39;ve got a couple drafts of how this might work.  They&#39;re in different branches here:</div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">   <a href="https://github.com/rrnewton/haskell-lockfree-queue/blob/master/AbstractDeque/Data/Concurrent/Deque/Class.hs" target="_blank" style="color: rgb(6, 88, 181); ">https://github.com/rrnewton/haskell-lockfree-queue/blob/master/AbstractDeque/Data/Concurrent/Deque/Class.hs</a></div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">   <a href="https://github.com/rrnewton/haskell-lockfree-queue/blob/one-type-class/AbstractDeque/Data/Concurrent/Deque/Class.hs" target="_blank" style="color: rgb(6, 88, 181); ">https://github.com/rrnewton/haskell-lockfree-queue/blob/one-type-class/AbstractDeque/Data/Concurrent/Deque/Class.hs</a></div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">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.</div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">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:</div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><div> test = do </div>

<div>     q :: Deque NT T SingleEnd SingleEnd Bound Safe Int &lt;- newQ</div><div>     pushL q 33</div><div>     x &lt;- tryPopR q</div><div>     print x</div><div>     return q</div></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">

<br></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">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.  </div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">   That little test, by the way, segfaults for me on Mac OS under GHC 7.2.1 even WITHOUT using casMutVar# (It&#39;s using Data.CAS.Fake presently.)  I&#39;ll file a bug report after I sanity check it some more.</div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">Disregarding that... the big problem in this case is the<b> inability to create overlapping type family instances.  </b></div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">In this case what we dearly WANT to do is specialize some subset of the 64-mode configuration space and then have a &quot;fallback&quot;.  You can take a look at my struggling in MegaDeque.  Both of my approaches require specifying explicitly the modes that you don&#39;t cover.</div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">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&#39;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 &quot;Int&quot;, 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?</div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">Also, there are some software-engineering issues here with respect to<b> where to put the instances</b>.  It would be nice to put the instances for DequeClass inside the individual implementations (like LinkedQueue.hs).  But that leads to problems because it&#39;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 <b>no way to qualify or hide them upon import....</b></div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">Feedback welcome.</div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><br></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">Cheers,</div>

<div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">  -Ryan</div></div><div style="font-family: arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); ">

<br></div><div><br></div><div><br></div>