Previously [Weatherhead15], I discussed the use of C++ templates to compile time program some well-known string katas. Template metaprogramming in this way imposes a functional style with the immutability of variables a key consideration. In this article I’m applying the same treatment to combinations of k elements and a variation on Eratosthenes sieve. The foundations for each are built as we go along including holding data within lists, adding and removing items from them, implementing queues, defining sequences and operating on them with sets. There is a bit to it so you may wish to skip ahead to a solution and come back to the detail. Either is fine but you’ll probably want to keep Listing 1 to hand for reference.
Lists
Without arrays and mutability at our disposal, a structure is required that can represent a list and after each operation produces a new variant. It’s common for functional languages to have an operation which adds an element to the beginning of a list and is typically known as cons (short for construct). This functional list differs from the imperative viewpoint of linearly linking elements with a head at one end, a body and a tail at the other. Instead it is woven from a compound pair of pairs. Each pair comprises a head plus tail that splits until a null tail terminates a given path. It’s good to have an appreciation of its recursive nature and the other features it affords see [SICP96]. However, for the most part, this article will attempt to adhere to the metaphor for a single chain.
1 #include <iostream> 2 3 using namespace std; 4 5 struct nop { 6 7 static const char delim = '\0'; 8 9 friend ostream& operator<<( ostream& os 10 , const nop& ) { return os; } 11 }; 12 13 struct nil : nop { 14 15 typedef nil type; 16 17 template< size_t SIZE = 0 > struct size { 18 19 static const size_t value = SIZE; 20 21 friend ostream& operator<<( ostream& os 22 , const size& ) { return os << SIZE; } 23 }; 24 25 template< class RHS > 26 struct append : RHS { typedef RHS type; }; 27 template< class RHS > 28 struct prepend : append< RHS > { }; 29 template< class RHS > 30 struct uunion : append< RHS > { }; 31 template< class RHS > 32 struct except : nop { typedef nil type; }; 33 template< class RHS > 34 struct intrsct : except< RHS > { }; 35 36 template< size_t N, size_t I_SIZE, class O 37 , size_t O_SIZE = 0 > struct kombine_ 38 : conditional< O_SIZE == N, O, nop >::type 39 { }; 40 }; 41 42 template< class HEAD, class TAIL 43 , char DELIM = ',' > struct list_ { 44 45 #define t typename 46 47 typedef list_ type; typedef list_ LHS; 48 typedef HEAD head; typedef TAIL tail; 49 50 static const char delim = DELIM; 51 52 friend ostream& operator<<( ostream& os 53 , const list_& ) { return os 54 << HEAD( ) << tail::delim << TAIL( ); } 55 56 template< size_t SIZE = 0 > struct size 57 : tail::template size< SIZE + 1 > { }; 58 59 template< class RHS > struct append 60 : list_< LHS, RHS, DELIM > { }; 61 template< class RHS > struct prepend 62 : list_< RHS, LHS, DELIM > { }; 63 64 template< class LHS, class RHS > 65 struct append_ 66 : LHS::type::template append< RHS > { }; 67 template< class LHS, class RHS > 68 struct prepend_ 69 : LHS::type::template prepend< RHS > { }; 70 template< class LHS, class RHS > 71 struct except_ 72 : LHS::type::template except< RHS > { }; 73 template< class LHS, class RHS > 74 struct uunion_ 75 : LHS::type::template uunion< RHS > { }; 76 template< class LHS, class RHS > 77 struct intrsct_ 78 : LHS::type::template intrsct< RHS > { }; 79 80 template< class RHS, bool = true > 81 struct uunion 82 : conditional< ( LHS::head::value < 83 RHS::head::value ) 84 , append_< LHS::head 85 , uunion_< LHS::tail, RHS > > 86 , append_< t RHS::head 87 , uunion_< LHS , t RHS::tail > > 88 >::type { 89 typedef HEAD head; typedef TAIL tail; }; 90 91 template< bool NA > struct uunion< nil, NA > 92 : append_< head, tail > { }; 93 94 template< class RHS, bool = true > 95 struct intrsct 96 : conditional< is_same< LHS, RHS >::value 97 , LHS 98 , t conditional< ( LHS::head::value == 99 RHS::head::value ) 100 , append_< LHS::head 101 , intrsct_< LHS::tail, t RHS::tail > > 102 , t conditional< ( LHS::head::value < 103 RHS::head::value ) 104 , intrsct_< LHS::tail, RHS > 105 , intrsct_< LHS , t RHS::tail > 106 >::type 107 >::type 108 >::type { 109 typedef HEAD head; typedef TAIL tail; }; 110 111 template< bool NA > 112 struct intrsct< nil, NA > : nil { }; 113 114 template< class RHS, bool = true > 115 struct except 116 : conditional< is_same< LHS, RHS >::value 117 , nil 118 ,t conditional< ( LHS::head::value < 119 RHS::head::value ) 120 , append_< t LHS::head 121 , except_< LHS::tail, RHS > > 122 , t conditional< ( LHS::head::value > 123 RHS::head::value ) 124 , except_< LHS , t RHS::tail > 125 , except_< LHS::tail, t RHS::tail > 126 >::type 127 >::type 128 >::type { 129 typedef HEAD head; typedef TAIL tail; }; 130 131 template< bool NA > struct except< nil, NA > 132 : append_< head, tail > { }; 133 134 template< size_t N, size_t I_SIZE 135 , class O, size_t O_SIZE > class kkombine_ { 136 137 friend ostream& operator<<( ostream& os 138 , const kkombine_& that ) { 139 140 static const int i_size = I_SIZE - 1; 141 142 return os 143 << t TAIL::template kombine_< N, i_size 144 , prepend_< HEAD, O >, O_SIZE + 1 >( ) 145 << t TAIL::template kombine_< N, i_size 146 , O , O_SIZE >( ); 147 } }; 148 149 template< size_t N, size_t I_SIZE, class O 150 = nop, size_t O_SIZE = 0 > struct kombine_ 151 : conditional< !O_SIZE && I_SIZE == N 152 , prepend_< type, nop > 153 , t conditional< O_SIZE == N, O 154 , t conditional< !I_SIZE, nil 155 , kkombine_< N, I_SIZE, O, O_SIZE > 156 >::type 157 >::type 158 >::type { }; 159 160 template< size_t N > struct kombine 161 : kombine_< N, size< >::value > { }; 162 163 template< size_t N, bool NA = true > 164 struct powerset_ { 165 166 friend ostream& operator<<( ostream& os 167 , const powerset_& that ) { return os 168 << powerset_< N - 1 >( ) 169 << kombine< N >( ); } 170 }; 171 172 template< bool NA > 173 struct powerset_< 0, NA > : nop { }; 174 175 struct powerset 176 : powerset_< size< >::value > { }; 177 178 #undef t 179 }; 180 181 template< class HEAD, class TAIL 182 , char DELIM = ',' > struct list 183 : list_< HEAD, TAIL, DELIM > { }; 184 185 template< class TAIL, char DELIM > 186 struct list_< nop, TAIL, DELIM > : TAIL { 187 188 friend ostream& operator<<( 189 ostream& os, const list_& ) { 190 return os << ' ' << TAIL( ); } 191 }; 192 193 template< class HEAD, char DELIM > 194 struct list< HEAD, nil, DELIM > 195 : list_< HEAD, nil, DELIM > { 196 197 typedef HEAD type; 198 199 friend ostream& operator<<( 200 ostream& os, const list& ) { 201 return os << HEAD::value; } 202 203 template< class RHS > struct append 204 : list< HEAD, RHS, DELIM > { }; 205 template< class RHS > struct prepend 206 : list< RHS, HEAD, DELIM > { }; 207 }; 208 209 template< class T, T V, class VS, char DELIM > 210 struct v 211 : list< v< T, V, nil, DELIM >, VS, DELIM > { 212 static const T value = V; }; |
Listing 1 |
In Listing 1, list_
(42–179) takes a HEAD
element and TAIL
elements; an additional parameter DELIM
defines the separator used between elements when printing. Appending an underscore to a class’s name is the convention used here to indicate internal usage, hence, list
(181–183) exposes list_
. No-operation nop
(5–11) simply places a null marker into the output as a guard element. A specialisation of list_
(185–191) which has nop
as its head element is used to indicate that it’s a list of lists and when printed each list can be delimited by another character. Another list
(193–207) is provided for elements at the end of a list i.e. that’s TAIL
is nil
(13–40) where some functions are overridden whilst nil
implements functions that operate on an empty list. When performingoperations between elements it is convenient to think in terms of what appears on the right and left hand sides, so list_
provides some internal functions that take RHS
and LHS
respectively. A value of type v
(209–212) is itself a list_
with its HEAD
being a single value element of the same type. Thus each element can be operated on in the same way.
Queues
Imperative lists and vectors describe consecutive elements, as does the functional list, and all can be used as the underlying structure of a queue. Removing the HEAD
of a list_
requires a simple reference to the TAIL
elements. To prepend
(28–29, 61–62, 205–206) elements another list_
is created with the new content in the HEAD
and the existing content in the TAIL
; append
(28–29, 59–60, 203–204) just reverses the concatenation of the HEAD
and TAIL
. There are also implementations of these that take explicit left and right hand side arguments – see append_
(65–66) and prepend_
(67–78).
Size
Functional programs don’t have loop constructs so rely on recursion to perform inductive operations. Templates don’t optimise tail recursive calls so each grows the stack, hence compilers place a limit on its depth (note that despite this if an expression is sufficiently long it’s still feasible to exhaust the memory). A classic way to observe this is to use a size function size< >
(17–23, 56–57) that iterates over a list to obtain a count. What’s not always clear is that functors used as default template parameter arguments can be evaluated independently of the template to which they’re applied. Take list_<HEAD, TAIL>::kombine_<N, I_SIZE, O = nop, O_SIZE = 0>
(149–158), if the input size I_SIZE
is defaulted to size<>
one might expect it to be calculated, as per a regular function, on invocation. However, as size<>
’s template parameters are not dependent on kombine_
’s the compiler instantiates it whenever list_
is called. This is okay for k-combinations but would unintentionally execute for primes too. To prevent this the default is wrapped by kombine<N>
(160–161). Alternatively how about having a size attribute i.e. size = 1
for single elements and size = HEAD::size + TAIL::size
as they are combined? This is fine when the HEAD
and TAIL
are lists. However, they are also used for list expressions; size isn’t intrinsic to these and their resultant type is unknown until fully evaluated.
Combinations
The brief is to find all the unique combinations of k elements from a set of distinct values. For the purpose of this discussion each element has its own letter and the input set is in alphabetical order.
In Figure 1 (k-combinations) the input elements are treated as a queue; at each step the last item is removed from the top of the queue and either placed at the bottom of the output queue when branching right or dropped when going left. If the output reaches the desired length before the input queue is exhausted then it forms a terminal node and branching ceases. Further, if the input is of the required length and the output queue is empty then the input can be directly substituted for the output without further branching.
Here k-combinations (Listing 2) are represented with consecutive characters, specified by c
and cs
. As previously mentioned list_<HEAD, TAIL>::kombine<N>
(160–161) wraps the initial call list_<HEAD, TAIL>::kombine_<N, size< >, nop, 0>
. This takes parameters for the desired combination length, the size of the input list which when first called is the size of the initial list, the output list and its size which are initially empty. The underlying definition list_<HEAD, TAIL>::kombine_<N, I_SIZE, O, O_SIZE>
(149–158) makes several checks. The first sees if the output can be directly substituted with the input. Otherwise a check is made to see if the output list has reached the desired length. If neither of these are satisfied list_<HEAD, TAIL >::kkombine_<N, I_SIZE, O, O_SIZE>
(134–147) is called to branch left and right. If the end of the input list is reached i.e. nil::kombine_<N, size<>, nop, 0>
(36–39) branching ceases with or without the output having reached the specified length. The powerset
(175–176) is implemented as all the combinations of k for 0 to n elements.
… template< char C, class CS = nil , char DELIM = '\0' > struct c : v< char, C, CS, DELIM > { }; template< char C, char... CS > struct cs : c< C, cs< CS... > > { }; template< char C > struct cs< C > : c< C > { }; int main( ) { /* kombine('abcd', 2)=' ab ac ad bc bd cd' * * powerset('abcd')=' a b c d ab ac ad bc * * bd cd abc abd acd bcd abcd' */ cout << "\nkombine('abcd', 2)='" << cs<'a','b','c','d'>::kombine<2>( )<< "'" << "\npowerset('abcd')='" << cs<'a','b','c','d'>::powerset( ) << "'"; } |
Listing 2 |
It can be seen from the enumeration of elements that the permutations, whilst not strictly necessary, are in lexicographic order. Another way of representing combinations is in binary whereby each bit set maps to a corresponding value to print. Investigation of this is left as an additional exercise.
Member template specialisation
You may have noticed that there are a number of member template functors that take an additional, seemingly redundant, parameter; in each case these have a specialisation. For example the power set is all the subsets of an input set including itself and the empty set. In the general case this is lists between the length of the input list powerset_<N>
to powerset_<1>
(163–170). A specialisation powerset_<0>
(172–173) terminates the set with an empty list. Nested classes are dependent on their enclosing template types, hence if explicitly specialised the enclosing classes need to be too. A work-around to this restriction is to provide partial specialisations by adding a dummy parameter.
Sequences
Lists can be long; however, if the content is not arbitrarily distributed then it can be described as a function rather than with individual elements. Evaluating the function and generating the list can then be deferred until first use. This is the case for sieving ranges of numbers with set intervals.
In Listing 3 (Sequences & Sets) a cons of integers i
is defined for use as a sequence seq
. The common case produces all integers in ascending order between a low LO
and high HI
value. The interval I
can be altered to increase the step size. Reversing direction by beginning at a high value, ending with a low value and specifying a negative increment will produce a sequence in descending order. At each step the current value is appended to the list and, whilst within bounds, the next step is defined as a sequence of itself with an incremented starting range.
… template< int I, class IS = nil , char DELIM = ',' > struct i : v< int, I, IS, DELIM > { }; template< int I, int... IS > struct is : i< I, is< IS... > > { }; template< int I > struct is< I > : i< I > { }; template< int LO, int HI, int I = 1 , char DELIM = ',' > struct seq : conditional< ( I > 0 ? LO + I <= HI : LO >= HI - I ) , i< LO, seq< LO + I, HI, I, DELIM > > , i< LO > >::type { }; int main( ) { /* seq(-3, 3, 2).uunion(seq(-2, 2, 2))= * * -3,-2,-1,0,1,2,3 * * seq(-3, 3).intrsct(seq(-2, 2, 2))= * * -2,0,2 * * seq(-3, 3).except(seq(-2, 2, 2))= * * -3,-1,1,3 */ cout << "\nseq(-3, 3, 2).uunion(seq(-2, 2, 2))=" << seq<-3, 3, 2>::uunion< seq<-2, 2, 2>>( ) << "\nseq(-3, 3).intrsct(seq(-2, 2, 2))=" << seq<-3, 3>::intrsct<seq< -2, 2, 2>>( ) << "\nseq(-3, 3).except(seq(-2, 2, 2))=" << seq<-3, 3>::except<seq<-2, 2, 2>>( ); } |
Listing 3 |
Sets
In addition to sequences some set theory is required to sieve. Union, intersection and difference of ascending ordered sets are provided (a description of each follows) although not all will be required. When combining operations it’s feasible that earlier operations result in an empty list, hence the member templates for sets (30–34) in nil
.
Union
The general case list<HEAD, TAIL>::uunion<RHS>
(80–89) determines which HEAD
, the LHS
or RHS
, is less than the other. Whichever is chosen becomes the HEAD
of a new list with the rest being the union of its TAIL
with the other list. The union of a list with an empty list is the list itself (91–92). As it isn’t fully defined at the point of parsing its creation is delayed with a concatenation operation i.e. append_<HEAD, TAIL>
.
Intersection
The general case list<HEAD, TAIL>::intrsct<R>
(94–109) determines whether the LHS
and RHS
’s HEAD
s are of equal value; if they are one becomes the HEAD
of the resulting list with the rest comprising the intersection of the respective list’s TAIL
s. Otherwise, the HEAD
with least value is discarded and the intersection between the remaining elements is performed. Intersection with an empty list (111–112) is, of course, nil
.
Set difference
Known here as list<HEAD, TAIL>::except<R>
(114–129) it is the equivalent of minus where any elements in the LHS
that also appear in the RHS
are removed. If both the LHS
and RHS
are identical then they cancel one another out resulting in the empty list nil
; otherwise, the HEAD
of each is compared. If the LHS
is less than the RHS
then it becomes the HEAD
of a new list with the rest being the set difference between its TAIL
and the RHS
’s. If it’s greater the RHS
’s HEAD
is removed and if equal both HEAD
s are removed with the set difference calculated between the remaining elements. If the RHS
is an empty list then there is nothing to minus (131–132); as with union the list isn’t fully defined at the point of parsing so a concatenation operation i.e. append_<HEAD, TAIL>
delays its creation.
Sieves
Eratosthenes proposed a simple way for finding primes up to a specified integer using the efficient principal of sieving. There are other well-known variations such as Euler’s sieve. The basic mechanism removes multiples of each integer between 2 and n thereby leaving only those that are divisible by one and themselves. There are some quick ways to refine this algorithm which also reduce recursive calls. All even numbers with the exception of 2 can be removed from the initial range; that is all multiples seeded from an even index and every other value from those with an odd. Further, as in table 1, higher order progressions have some values that overlap with lower ones. Thus sequences can begin at the square of their seed. Similarly it is unnecessary to go beyond an index that is √n as if n is not prime it must have a divisor less than or equal to √n [SICP96]. Table 1 shows the arithmetic progressions required to sieve integers between 2 and 100.
|
||||||||||||||||||||||||||||||||||||||||
Table 1 |
A common solution is to have an array of elements indexed from 1 to n, marking 1 for removal, then generating multiples from 2 to the square root of n, beginning each sequence with the square of its index and marking these for removal too, and finally printing all unmarked values. Instead the algorithm can be conceived in terms of operations on ordered sets.
In Listing 4 (Eratosthenes Sieve) the template parameter HI
is the limit value, N
is the current sieving multiple beginning at 3 and incrementing by 2 for odd intervals. O
is the output list which will be successively sieved; it begins as a list of a fixed value of 2 followed by the sequence of odd numbers up to and including the limit value. Whilst the square of the multiple i.e. LO = N * N
is less than or equal to the HI
boundary every other odd multiple N + N
is sieved from the output list.
… template< int HI, int N = 3 , class O = i< 2, seq< 3, HI, 2 > > , int LO = N * N > struct primes : conditional< LO <= HI , primes< HI, N + 2 , typename O::type::template except< seq< LO, HI, N + N > > > , O >::type { }; int main( ) { /* primes(350)=2,3,5,7,11,13,17,19,23,29,31 * * ,37,41,43,47,53,59,61,67,71,73,79,83,89 * * ,97,101,103,107,109,113,127,131,137,139 * * ,149,151,157,163,167,173,179,181,191,193 * * ,197,199,211,223,227,229,233,239,241,251 * * ,257,263,269,271,277,281,283,293,307,311 * * ,313,317,331,337,347,349 */ cout << "\nprimes(350)=" << primes<350>( ); } |
Listing 4 |
Summary
In [Weatherhead15] I covered ASCII to integer conversion, roman numerals and palindromes. Each used a variant of the list construct to represent strings. Here it was used to generate combinations with a queue and to sieve sequences by applying set operations. Representative of the way runtime classes are developed the data and methods were encapsulated for reuse. Further ways to experiment with this include implementing other sieves and adding functions to filter and sort.
Note
All the code in this article compiles with GCC 4.9.2 and Clang 3.5.2 using -std=c++11. However, your mileage may vary with other compilers. Also whilst a null character should not be displayed in a terminal, some platforms show them as a space.
References
[SICP96] Harold Abelson and Gerald Jay Sussman with Julie Sussman. Structure and Interpretation of Computer Programs Second Edition pp.53–54, 116, 139–145, The MIT Press, 1996.
[Weatherhead15] Nick Weatherhead. Template Programming Compile Time String Functions, Overload 128, August 2015.
Further reading
Chris Oldwood. List incomprehension, CVu Volume 26 Issue 2 pp.7–8, May 2014.
Stuart Golodetz. Functional Programming Using C++ Templates (Part 1), Overload 81, October 2007.
Acknowledgements
I’d like to thank the Overload review team for providing their feedback which enabled me to elevate the content presented in this article.
Overload Journal #131 - February 2016 + Programming Topics
Browse in : |
All
> Journals
> Overload
> o131
(7)
All > Topics > Programming (877) Any of these categories - All of these categories |