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

Michael Snoyman michael at snoyman.com
Fri Sep 13 09:36:51 CEST 2013

On Fri, Sep 13, 2013 at 10:07 AM, Mario Blažević <blamario at acanac.net>wrote:

> On 09/13/13 02:28, Michael Snoyman wrote:
>> On Fri, Sep 13, 2013 at 9:18 AM, Mario Blažević <blamario at acanac.net<mailto:
>> blamario at acanac.net>> wrote:
>>         On 09/13/13 01:51, Michael Snoyman wrote:
>>         On Fri, Sep 13, 2013 at 5:38 AM, Mario Blažević
>>         <blamario at acanac.net <mailto:blamario at acanac.net>
>>         <mailto:blamario at acanac.net <mailto:blamario at acanac.net>>> wrote:
>>             On 09/11/13 19:37, John Lato wrote:
>>                 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.
>>                     If monolithic classes bother you, my monoid-subclasses
>>             package manages to break down the functionality into several
>>             classes. One big difference is that everything is based
>>         off Monoid
>>             rather than Foldable, and that has some big effects on the
>>         interface.
>>         I'd point out what I'd consider a bigger difference: the type
>>         signatures have changed in a significant way. With
>>         MonoFoldable, folding on a ByteString would be:
>>             (Word8 -> b -> b) -> b -> ByteString -> b
>>         With monoid-subclasses, you get:
>>             (ByteString -> b -> b) -> b -> ByteString -> b
>>         There's certainly a performance issue to discuss, but I'm more
>>         worried about semantics. Word8 tells me something very
>>         specific: I have one, and precisely one, octet. ByteString
>>         tells me I have anywhere from 0 to 2^32 or 2^64  octets. Yes,
>>         we know from context that it will always be of size one, but
>>         the type system can't enforce that invariant.
>>         All true, but we can also use this generalization to our
>>     advantage. For example, the same monoid-subclasses package
>>     provides ByteStringUTF8, a newtype wrapper around ByteString. It
>>     behaves the same as the plain ByteString except its atomic factors
>>     are not of size 1, instead it folds on UTF-8 encoded character
>>     boundaries. You can't represent that in Haskell's type system.
>> I can think of two different ways of achieving this approach with
>> MonoFoldable instead: by setting `Element` to either `Char` or
>> `ByteStringUTF8`. The two approaches would look like:
>> newtype ByteStringUTF8A = ByteStringUTF8A S.ByteString
>> type instance Element ByteStringUTF8A = Char
>> instance MonoFoldable ByteStringUTF8A where
>>     ofoldr f b (ByteStringUTF8A bs) = ofoldr f b (decodeUtf8 bs)
>>     ofoldl' = undefined
>> newtype ByteStringUTF8B = ByteStringUTF8B S.ByteString
>> type instance Element ByteStringUTF8B = ByteStringUTF8B
>> instance MonoFoldable ByteStringUTF8B where
>>     ofoldr f b (ByteStringUTF8B bs) = ofoldr (f . ByteStringUTF8B .
>> encodeUtf8 . T.singleton) b (decodeUtf8 bs)
>>     ofoldl' = undefined
>> I'd personally prefer the first approach, as that gives the right
>> guarantees at the type level: each time the function is called, it will be
>> provided with precisely one character. I believe the second approach
>> provides the same behavior as monoid-subclasses does right now.
>     Right now monoid-subclasses actually provides both approaches. You're
> correct that it provides the second one as instance FactorialMonoid
> ByteStringUTF8, but it also provides the former as instance TextualMonoid
> ByteStringUTF8. The TextualMonoid class is basically what you'd get if you
> restricted MonoFoldable to type Elem=Char. I wanted to keep the package
> extension-free, you see.
Got it, that makes sense.

>     My main point is that it's worth considering basing MonoFoldable on
> FactorialMonoid, because it can be considered its specialization. Methods
> like length, take, or reverse, which never mention the item type in their
> signature, can be inherited from the FactorialMonoid superclass with no
> change whatsoever. Other methods would differ in their signatures (and
> performance), but the semantics would carry over.
My immediate concern is that this would enforce a number of restrictions on
what could be a MonoFoldable. For example, you couldn't have an instance
for `Identity a`. Being able to fold over any arbitrary container, even if
it's not a Monoid, can be very useful.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130913/037b070e/attachment.htm>

More information about the Haskell-Cafe mailing list