Boost logo

Boost :

Subject: Re: [boost] [mpl] multiset
From: pfultz2 (pfultz2_at_[hidden])
Date: 2015-03-08 16:29:21


> 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.

Yes. Catamorphism is used to "destroy" the list, and anamorphism is used to
build the list. Now, `Iterable` and `Foldable` can both be considered
catamorphic, since folding can be built on top of `Iterable`. This is the
same
way unfolding can be built on top of `Insertable`. So using the lower level
concepts such as `Iterable` and `Insertable`, we can do some algorithms more
efficiently.

> > 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.

Now in the Chaos library, it has these functions:

* CONS - push_front
* HEAD - front
* TAIL - pop_front
* NIL - An empty data structure(perhaps called remove_all)
* IS_NIL - is_empty

However, all these functions could be written using `Iterable` and
`Insertable` as well:

Iterable:
* front
* pop_front

Insertable:
* push_front

So the other two methods(`remove_all` and `is_empty`) can be derived from
the
above three methods:

template<class Sequence>
using is_empty = is_same<Sequence, pop_front&lt;Sequence>>;

template<class Sequence>
using remove_all = if_<is_empty&lt;Sequence>, Sequence,
remove_all<pop_front&lt;Sequence>>>;

> Are you referring to? 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.

No, I am referring to the fact that you would return a new Foldable sequence
that would do the transform while it folds.

Paul

--
View this message in context: http://boost.2283326.n4.nabble.com/mpl-multiset-tp4672187p4672849.html
Sent from the Boost - Dev mailing list archive at Nabble.com.

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk