Re: [boost] [mpl] multiset

Subject: Re: [boost] [mpl] multiset
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2015-03-07 17:47:50

pfultz2 <pfultz2 <at> yahoo.com> writes:

> [...]
> > Regarding the usage of other concepts like Foldable, you say it
> > was suggested that everything could be implemented around folds. 
> 
> I am the one who made the suggestion, however, I didn't say just `Foldable`
> alone. I said they could be implemented using `Foldable` and `Insertable`
> concepts, as these are essentially dual categories.

That's an interesting line of thought. More generally, I think it
is true that any structure that can be folded can be reconstructed
using the dual fold. In category theory these are called catamorphisms 
and anamorphisms, but I'm not there yet :D.

> Looking at this closer, I don't think there is an efficient way 
> (or at least I have yet to find a way) to implement some algorithms 
> (such as `drop`) using just these concepts. 

I have tried hard to do that in the MPL11, and my conclusion was 
that those concepts provide very nice and general abstractions, 
but the implementation has to be dirty and lowlevel internally in 
order to be efficient. That's because the execution model of 
template metaprograms is weird. However, I think this is going 
to be true almost regardless of which abstraction you choose.

> I think a better approach would be how Paul Mensonides defines 
> generic data structures in his Chaos library. Its pretty simple 
> and lightweight.

I'll definitely take a look at this.

> > This is false in general, because stuff like `transform`
> 
> Well, `transform` could be implement using `Foldable` but it may 
> not be the semantics the user expects.

Are you referring to 

    fmap f xs = foldr ((:) . f) [] xs

? If so, Foldable is missing (:) and []. If that is not
what you meant, I must admit that I had no idea `transform`
could be implemented with Foldable alone.

Regards,
Louis