-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtlist.cpp
274 lines (238 loc) · 6.11 KB
/
tlist.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
/* Compile with:
* g++ -Wall -Wextra -Werror -std=gnu++11 -o tlist tlist.cpp
*/
#include <iostream>
#include <cassert>
#include <string>
#include <sstream>
// Template list of ints (cons).
template<int T, class U>
struct tlist
{
typedef int head;
typedef U tail;
};
struct null_type
{};
// Basic pattern matching.
template<class tlist> struct length;
template<> struct length<null_type>
{
enum { value = 0 };
};
template<int T, class U> struct length<tlist<T,U> >
{
enum { value = 1 + length<U>::value };
};
template<class tlist> struct sum;
template<> struct sum<null_type>
{
enum { value = 0 };
};
template<int T, class U> struct sum<tlist<T,U> >
{
enum { value = T + sum<U>::value };
};
// Concatenation of two tlists.
template<class tlist1, class tlist2> struct concat;
template<class tlist2> struct concat<null_type, tlist2>
{
typedef tlist2 result;
};
template<int T, class U, class tlist2> struct concat<tlist<T,U>, tlist2>
{
private:
typedef typename concat<U, tlist2>::result tail;
public:
typedef tlist<T, tail> result;
};
// Build a new list tlist<head, tail> or keep tail.
template<bool B, int head, class tail> struct take;
template<int head, class tail> struct take<true, head, tail>
{
typedef tlist<head, tail> result;
};
template<int head, class tail> struct take<false, head, tail>
{
typedef tail result;
};
// Binary predicates.
template<int lhs, int rhs>
struct is_less
{
enum { value = lhs < rhs };
};
template<int lhs, int rhs>
struct is_ge
{
enum { value = lhs >= rhs };
};
// Filter using binary predicates.
template<
template<int, int> class pred,
int limit,
class tlist >
struct filter;
template<
template<int, int> class pred,
int limit >
struct filter<pred, limit, null_type>
{
typedef null_type result;
};
template<
template<int, int> class pred,
int limit,
int head,
class tail >
struct filter<pred, limit, tlist<head,tail>>
{
private:
typedef typename filter<pred, limit, tail>::result comp_tail;
static const bool should_take = pred<head, limit>::value;
public:
typedef typename take<should_take, head, comp_tail>::result result;
};
// Quicksort.
template<class tlist> struct quicksort;
template<> struct quicksort<null_type>
{
typedef null_type result;
};
template<int head, class tail>
struct quicksort< tlist<head, tail> >
{
private:
typedef typename quicksort<typename filter<is_less, head, tail>::result >::result left;
typedef typename quicksort<typename filter<is_ge, head, tail>::result >::result right;
public:
typedef typename concat<left, tlist<head, right> >::result result;
};
// Alternative implementation of filter and quicksort using nested, templated
// structs to emulate partial application of predicates.
//
// The quicksort bit doesn't compile with gcc 4.7, and might not be valid
// C++11.
template<int rhs>
struct is_less1
{
template<int lhs>
struct lambda {
enum { value = lhs < rhs };
};
};
template<int rhs>
struct is_ge1
{
template<int lhs>
struct lambda {
enum { value = lhs >= rhs };
};
};
template<int input>
struct not_null
{
enum { value = 1 };
};
template<>
struct not_null<0>
{
enum { value = 0 };
};
// Filter using unary predicates.
template<
template<int> class pred,
class tlist >
struct filter1;
template<
template<int> class pred >
struct filter1<pred, null_type>
{
typedef null_type result;
};
template<
template<int> class pred,
int head,
class tail >
struct filter1<pred, tlist<head,tail>>
{
private:
typedef typename filter1<pred, tail>::result comp_tail;
static const bool should_take = pred<head>::value;
public:
typedef typename take<should_take, head, comp_tail>::result result;
};
#if 0
template<class tlist> struct quicksort1;
template<> struct quicksort1<null_type>
{
typedef null_type result;
};
template<int head, class tail>
struct quicksort1< tlist<head, tail> >
{
private:
typedef typename is_less1<head>::lambda pred_left;
typedef typename is_ge1<head>::lambda pred_right;
typedef typename filter1<pred_left, tail>::result partition_left;
typedef typename filter1<pred_right, tail>::result partition_rigth;
typedef typename quicksort1<partition_left>::result left;
typedef typename quicksort1<partition_right>::result right;
public:
typedef typename concat<left, tlist<head, right> >::result result;
};
#endif
// Pretty printing.
template<class tlist> struct format;
template<> struct format<null_type>
{
std::string operator()(){
return "";
}
};
template<int T, class U> struct format<tlist<T,U> >
{
std::string operator()(){
std::stringstream ss;
format<U> print;
ss << T << " " << print();
return ss.str();
}
};
// Simpler building of lists.
template<int...> struct
build_list;
template<> struct
build_list<> {
typedef null_type result;
};
template<int i, int... tail> struct
build_list<i, tail...> {
typedef tlist<i, typename build_list<tail...>::result > result;
};
int main()
{
typedef tlist<1, tlist<5, tlist<2, null_type> > > numlist;
typedef tlist<7, numlist> numlist2;
std::cout << "length 1: " << length<numlist>::value << std::endl;
std::cout << "length 2: " << length<numlist2>::value << std::endl;
std::cout << "sum 1: " << sum<numlist>::value << std::endl;
std::cout << "sum 2: " << sum<numlist2>::value << std::endl;
std::cout << "filtered sum 1: " << sum<filter<is_less, 2, numlist2>::result>::value << std::endl;
typedef concat<numlist, numlist2>::result combined;
std::cout << "sum combined: " << sum<combined>::value << std::endl;
std::cout << "list: " << format<combined>()() << std::endl;
std::cout << "sorted: " << format<quicksort<combined>::result>()() << std::endl;
typedef build_list<1, 3, 0, 5, 2, 1>::result simple_list;
std::cout << "list: " << format<simple_list>()() << std::endl;
std::cout << "sorted: " << format<quicksort<simple_list>::result>()() << std::endl;
// Unary version
std::cout << "cmp: " << is_ge1<3>::lambda<4>::value << " " <<
is_ge1<5>::lambda<4>::value << std::endl;
std::cout << "filtered sum 1: " << sum<filter1<is_less1<2>::lambda, numlist2>::result>::value << std::endl;
std::cout << "filtered: " << format<filter1<not_null, simple_list>::result>()() << std::endl;
#if 0
std::cout << "sorted: " << format<quicksort1<simple_list>::result>()() << std::endl;
#endif
return 0;
}