Building tree expanding and backtracking evaluations within hierarchical scopes.
Based on the Lumiera Forward Iterator concept and using the basic IterAdapter templates, these components allow to implement typical evaluation strategies, like conditional expanding or depth-first exploration of a hierarchical structure. Since the access to this structure is abstracted through the underlying iterator, what we effectively get is a functional datastructure. The implementation is based on the idea of a "state core", which is wrapped right into the iterator itself (value semantics) – similar to the IterStateWrapper, which is one of the basic helper templates provided by iter-adapter.hpp.
Background: Iterators as Monad
The fundamental idea behind the implementation technique used here is the Monad pattern known from functional programming. A Monad is a container holding some arbitrarily typed base value; the monad can be seen as „amplifying“ and enhancing the contained base value by attaching additional properties or capabilities This is a rather detached concept with a wide variety of applications (things like IO state, parsers, combinators, calculations with exception handling but also simple data structures like lists or trees). The key point with any monad is the ability to bind a function into the monad; this function will work on the contained base values and produce a modified new monad instance. In the simple case of a list, "binding" a function basically means to map the function onto the elements in the list. (strictly speaking, it means the flatMap operation)
A Pipeline builder
Based on such concepts, structures and evaluation patterns, the IterExplorer serves the purpose to provide building blocks to assemble a processing pipeline, where processing will happen on demand, while iterating. IterExplorer itself is both a Lumiera Forward Iterator based on some wrapped data source, and at the same time it is a builder to chain up processing steps to work on the data pulled from that source. These processing steps are attached as decorators wrapping the source, in the order the corresponding builder functions were invoked.
- the expand operation installs a function to consume one element and replace it by the sequence of elements (``children'') produced by that »expansion functor«. But this expansion does not happen automatically and on each element, rather it is triggered by issuing a dedicated
expandChildren() call on the processing pipeline. Thus, binding the expansion functor has augmented the data source with the ability to explore some part in more detail when required.
- the transform operation installs a function to be mapped onto each element retrieved from the underlying source
- in a similar vein, the filter operation binds a predicate to decide about using or discarding data
- in concert, expand- and transform operation allow to build hierarchy evaluation algorithms without exposing any knowledge regarding the concrete hierarchy used and explored as data source.
- further special convenience adaptors and terminal functions are provided.
In itself, the IterExplorer is an iterator with implementation defined type (all operations being inlined). But it is possible to package this structure behind a conventional iteration interface with virtual functions. By invoking the terminal builder function IterExplorer::asIterSource(), the iterator compound type, as created thus far, will be moved into a heap allocation, returning a front-end based on IterSource. In addition, the actually returned type, IterExplorerSource, exposes the expandChildren() operation as discussed above.
Rationale
This design leads to a complete separation of the transforming operation from the mechanics how to apply that operation and combine the results. More specifically, we rely on an iterator to represent an abstracted source of data and we expose the combined and transformed results again as such an abstracted data sequence. Thereby, a trend towards separation of concerns is introduced; the data source remains opaque, while the manipulation to apply can be selected at runtime or written inline as Lambda. The iterator itself is a self-contained value and represents partial evaluation state without requiring a container for intermediary results.
some implementation details
The builder operations assemble a heavily nested type, each builder call thereby adding yet another layer of subclassing. The templates involved into this build process are specialised, as driven by the actual functor type bound into each builder step; this functor is investigated and possibly adapted, according to its input type, while its output type determines the value type used in the pipeline "downstream". A functor with an input (argument) type incompatible or unsuitable to the existing pipeline will produce that endless sway of template error messages we all love so much. When this happens, please look at the static assertion error message typically to be found below the first template-instantiation stack sequence of messages.
- Warning
- all builder operations work by moving the existing pipeline built thus far into the parent of the newly built subclass object. The previously existing pipeline is defunct after that move; if you captured it into a variable, be sure to capture the result of the new builder operation as well and don't use the old variable anymore. An insidious trap can be to store references to source iterator state from within the pipeline. Moreover, it should be ensured that any "state core" used within IterExplorer has an efficient move ctor; including RVO, the compiler is typically able to optimise such move calls away altogether.
- See also
- IterExplorer_test
-
iter-adapter.hpp
-
itertools.hpp
-
IterSource (completely opaque iterator)
Definition in file iter-explorer.hpp.
|
| struct | _BaseDetector< SRC, SEL > |
| | Detect or otherwise add BaseAdapter. More...
|
| |
| struct | _BaseDetector< SRC, std::void_t< typename SRC::TAG_IterExplorer_BaseAdapter > > |
| |
| struct | _DecoratorTraits< SRC, SEL > |
| |
| struct | _DecoratorTraits< ISO &, enable_if< is_base_of< IterSource< typename ISO::value_type >, ISO > > > |
| |
| struct | _DecoratorTraits< ISO *&, enable_if< is_base_of< IterSource< typename ISO::value_type >, ISO > > > |
| |
| struct | _DecoratorTraits< ISO *, enable_if< is_base_of< IterSource< typename ISO::value_type >, ISO > > > |
| |
| struct | _DecoratorTraits< SRC, enable_if< is_StateCore< SRC > > > |
| |
| struct | _DecoratorTraits< SRC, enable_if< shall_use_Lumiera_Iter< SRC > > > |
| |
| struct | _DecoratorTraits< SRC, enable_if< shall_wrap_STL_Iter< SRC > > > |
| |
| struct | _ExpanderTraits< SRC, RES > |
| | helper to derive a suitable common type when expanding children More...
|
| |
| struct | _FunTraits< FUN, SRC > |
| |
| struct | _PipelineDetector< SRC, SEL > |
| | Detect if given source was already built by IterExplorer;. More...
|
| |
| struct | _PipelineDetector< SRC, std::void_t< typename SRC::TAG_IterExplorer_Src > > |
| |
| struct | _ReduceTraits< SRC, FUN > |
| |
| struct | _UnstripAdapter< SRC, SEL > |
| | Detect and remove typical adapter layers added by a preceding IterExplorer usage. More...
|
| |
| struct | _UnstripAdapter< COR, std::void_t< typename COR::TAG_CheckedCore_Raw > > |
| |
| struct | _FunTraits< FUN, SRC >::ArgAdapter< ARG, SEL > |
| | adapt to a functor, which accesses the source iterator or embedded "state core" More...
|
| |
| struct | _FunTraits< FUN, SRC >::ArgAdapter< IT, enable_if< __and_< is_base_of< IterSource< typename IT::value_type >, typename IT::Source >, is_base_of< IterSource< typename IT::value_type >, remove_reference_t< Arg > > > > > |
| | adapt to a functor collaborating with an IterSource based iterator pipeline More...
|
| |
| struct | _FunTraits< FUN, SRC >::ArgAdapter< IT, enable_if< __and_< is_convertible< iter::Yield< IT >, Arg >, __not_< is_convertible< IT, Arg > > > > > |
| | adapt to a functor, which accepts the value type of the source sequence ("monadic" usage pattern) More...
|
| |
| class | AutoExpander< SRC > |
| |
| struct | BaseAdapter< SRC > |
| |
| struct | Grouping< SRC, RES, grp >::Buffer |
| |
| class | ChildExpandableSource< VAL > |
| | Interface to indicate and expose the ability for child expansion. More...
|
| |
| class | Expander< SRC, RES > |
| |
| class | Filter< SRC > |
| |
| struct | _FunTraits< FUN, SRC >::FunDetector< F, SEL > |
| | handle all regular "function-like" entities More...
|
| |
| struct | _FunTraits< FUN, SRC >::FunDetector< F, disable_if< _Fun< F > > > |
| | handle a generic lambda, accepting a reference to the SRC iterator More...
|
| |
| class | GroupAggregator< SRC, AGG, GRP > |
| |
| class | Grouping< SRC, RES, grp > |
| |
| class | IterExplorer< SRC > |
| | Adapter to build a demand-driven tree expanding and exploring computation based on a custom opaque state core. More...
|
| |
| struct | IterExploreSource< VAL > |
| | Iterator front-end to manage and operate a IterExplorer pipeline opaquely. More...
|
| |
| class | IterSourceIter< ISO > |
| | Adapt an IterSource to make it iterable. More...
|
| |
| class | MutableFilter< SRC > |
| |
| class | PackagedIterExplorerSource< SRC > |
| |
| class | ScheduledExpander< SRC > |
| |
| class | set< K > |
| | STL class.
|
| |
| struct | shall_use_Lumiera_Iter< SRC > |
| |
| struct | shall_wrap_STL_Iter< SRC > |
| |
| struct | StlRange< CON > |
| | Adapt STL compliant container. More...
|
| |
| struct | StlRange< CON & > |
| |
| struct | StlRange< const CON > |
| |
| class | StopTrigger< SRC > |
| |
| class | Transformer< SRC, RES > |
| |
| class | vector< T > |
| | STL class.
|
| |
Collaboration diagram for _BaseDetector< SRC, SEL >:
1.8.13