[Haskell-cafe] Monomorphic containers, Functor/Foldable/Traversable WAS: mapM_ for bytestring

Michael Snoyman michael at snoyman.com
Wed Sep 11 22:25:28 CEST 2013

That's really funny timing. I started work on a very similar project just
this week:


It's not refined yet, which is why I haven't discussed it too publicly, but
it's probably at the point where some review would make sense. There's been
a bit of a discussion on a separate Github issue[1] about it.

A few caveats:

   - The names are completely up for debate, many of them could be improved.
   - The laws aren't documented yet, but they mirror the laws for the
   polymorphic classes these classes are based on.
   - The Data.MonoTraversable module is the main module to look at. The
   other two are far more nascent (though I'd definitely appreciate feedback
   people have on them).

I think this and mono-foldable have a lot of overlap, I'd be interested to
hear what you think in particular John.


[1] https://github.com/snoyberg/classy-prelude/issues/18

On Wed, Sep 11, 2013 at 11:05 PM, John Lato <jwlato at gmail.com> wrote:

> I agree with everything Edward has said already.  I went through a similar
> chain of reasoning a few years ago when I started using ListLike, which
> provides a FoldableLL class (although it uses fundeps as ListLike predates
> type families).  ByteString can't be a Foldable instance, nor do I think
> most people would want it to be.
> Even though I would also like to see mapM_ in bytestring, it's probably
> faster to have a library with a separate monomorphic Foldable class.  So I
> just wrote one:
> https://github.com/JohnLato/mono-foldable
> http://hackage.haskell.org/package/mono-foldable
> Petr Pudlak has done some work in this area.  A big problem is that
> foldM/mapM_ are typically implemented in terms of Foldable.foldr (or
> FoldableLL), but this isn't always optimal for performance.  They really
> need to be part of the type class so that different container types can
> have specialized implementations.  I did that in mono-foldable, using
> Artyom's map implementation (Artyom, please let me know if you object to
> this!)
> pull requests, forks, etc all welcome.
> John L.
> On Wed, Sep 11, 2013 at 1:29 PM, Edward Kmett <ekmett at gmail.com> wrote:
>> mapM_ is actually implemented in terms of Foldable, not Traversable, and
>> its implementation in terms of folding a ByteString is actually rather slow
>> in my experience doing so inside lens and isn't much faster than the naive
>> version that was suggested at the start of this discussion.
>> But as we're not monomorphizing Foldable/Traversable, this isn't a think
>> that is able to happen anyways.
>> -Edward
>> On Wed, Sep 11, 2013 at 2:25 PM, Henning Thielemann <
>> lemming at henning-thielemann.de> wrote:
>>> On Wed, 11 Sep 2013, Duncan Coutts wrote:
>>>  For mapM etc, personally I think a better solution would be if
>>>> ByteString and Text and other specialised containers could be an
>>>> instance of Foldable/Traversable. Those classes define mapM etc but
>>>> currently they only work for containers that are polymorphic in their
>>>> elements, so all specialised containers are excluded. I'm sure there
>>>> must be a solution to that (I'd guess with type families) and that would
>>>> be much nicer than adding mapM etc to bytestring itself. We would then
>>>> just provide efficient instances for Foldable/Traversable.
>>> I'd prefer to keep bytestring simple with respect to the number of type
>>> extensions. Since you must implement ByteString.mapM anyway, you can plug
>>> this into an instance definition of Traversable ByteString.
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://www.haskell.org/mailman/listinfo/libraries
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130911/115c1534/attachment.htm>

More information about the Haskell-Cafe mailing list