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

[John Lato]

I didn't see this message and replied privately to Michael earlier, so I'm
replicating my comments here.

1.  Sooner or later I expect you'll want something like this:

class LooseMap c el el' where
  lMap :: (el -> el') -> c el -> c el'

It covers the case of things like hashmaps/unboxed vectors that have class
constraints on elements.  Although maybe LooseFunctor or LFunctor is a
better name.

Probably something similar for Traversable would be good also, as would a
default instance in terms of Functor.

2.  IMHO cMapM_ (and related) should be part of the Foldable class.  This
is entirely for performance reasons, but there's no downside since you can
just provide a default instance.

3.  I'm not entirely sure that the length* functions belong here.  I
understand why, and I think it's sensible reasoning, and I don't have a
good argument against it, but I just don't like it.  With those, and
mapM_-like functions, it seems that the foldable class is halfway to being
another monolithic ListLike.  But I don't have any better ideas either.

As to the bikeshed color, I would prefer to just call the classes
Foldable/Traversable.  People can use qualified imports to disambiguate
when writing instances, and at call sites client code would never need
Data.{Foldable|Traversable} and can just use these versions instead.  I'd
still want a separate name for Functor though, since it's in the Prelude,
so maybe it's better to be consistent.  My $.02.


On Wed, Sep 11, 2013 at 3:25 PM, Michael Snoyman <michael at snoyman.com>wrote:

> That's really funny timing. I started work on a very similar project just
> this week:
>
> https://github.com/snoyberg/mono-traversable
>
> 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.
>
> Michael
>
> [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/22362406/attachment.htm>