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

Mario Blažević blamario at acanac.net
Fri Sep 13 09:07:57 CEST 2013

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.

     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.

More information about the Haskell-Cafe mailing list