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

On 09/13/13 02:28, Michael Snoyman wrote:

On Fri, Sep 13, 2013 at 9:18 AM, Mario Blažević mailto:blamario@acanac.net> wrote:

On 09/13/13 01:51, Michael Snoyman wrote:

On Fri, Sep 13, 2013 at 5:38 AM, Mario Blažević mailto:blamario@acanac.net mailto:blamario@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.