1use core::ops::Add;
2use core::{marker::PhantomData, ops::Sub};
3
4use typenum::{Bit, IsEqual, U0, U1, UInt, Unsigned};
5
6use crate::bool::monoid::{Both, Either};
7use crate::bool::{And, Bool, False, Not, Or, True};
8use crate::collections::Container;
9use crate::num::Addition;
10use crate::traits::applicative;
11use crate::traits::monoid::Monoid;
12use crate::traits::{
13 fold::Foldable,
14 functor::{Map, Mapper},
15 monoid::Mempty,
16 semigroup::Mappend,
17};
18
19#[macro_export]
20macro_rules! list {
21 [$a:ty] => { $crate::collections::list::List<($a, $crate::collections::list::List<()>)> };
22 [$a:ty,$($bs:ty),+] => { $crate::collections::list::List<($a, $crate::list![$($bs),+])> };
23}
24pub type Append<A, B> = <(A, B) as Mappend>::Out;
25pub type Idx<T, N> = <(T, N) as Indexed>::Out;
26pub type Head<T> = <T as Container>::Content;
27pub type Tail<T> = <T as Tailed>::Tail;
28pub type Skip<T, N> = <(T, N) as Skippable>::Out;
29pub type Take<T, N> = <(T, N) as Takeable>::Out;
30
31pub trait IsUnique {
32 type Out;
33}
34impl IsUnique for Empty {
35 type Out = True;
36}
37impl<T, U> IsUnique for List<(T, U)>
38where
39 (U, T): IsContainedBy,
40 <(U, T) as IsContainedBy>::Out: Not,
41 U: IsUnique,
42 (
43 <<(U, T) as IsContainedBy>::Out as Not>::Out,
44 <U as IsUnique>::Out,
45 ): And,
46{
47 type Out = <(
48 <<(U, T) as IsContainedBy>::Out as Not>::Out,
49 <U as IsUnique>::Out,
50 ) as And>::Out;
51}
52
53pub trait IsContainedBy {
54 type Out;
55}
56impl<T> IsContainedBy for (Empty, T) {
57 type Out = False;
58}
59impl<T, U, V> IsContainedBy for (List<(U, V)>, T)
60where
61 T: IsEqual<U>,
62 <T as IsEqual<U>>::Output: Bool,
63 (V, T): IsContainedBy,
64 (
65 <<T as IsEqual<U>>::Output as Bool>::Out,
66 <(V, T) as IsContainedBy>::Out,
67 ): Or,
68{
69 type Out = <(
70 <<T as IsEqual<U>>::Output as Bool>::Out,
71 <(V, T) as IsContainedBy>::Out,
72 ) as Or>::Out;
73}
74
75pub trait Takeable {
76 type Out;
77}
78impl Takeable for (Empty, U0) {
79 type Out = Empty;
80}
81impl<U, B> Takeable for (Empty, UInt<U, B>)
82where
83 U: Unsigned,
84 B: Bit,
85{
86 type Out = Empty;
87}
88impl<H, T> Takeable for (List<(H, T)>, U0) {
89 type Out = Empty;
90}
91impl<H, T, U, B> Takeable for (List<(H, T)>, UInt<U, B>)
92where
93 U: Unsigned,
94 B: Bit,
95 UInt<U, B>: Sub<U1>,
96 (T, <UInt<U, B> as Sub<U1>>::Output): Takeable,
97 (
98 List<(H, Empty)>,
99 <(T, <UInt<U, B> as Sub<U1>>::Output) as Takeable>::Out,
100 ): Mappend,
101{
102 type Out = <(
103 List<(H, Empty)>,
104 <(T, <UInt<U, B> as Sub<U1>>::Output) as Takeable>::Out,
105 ) as Mappend>::Out;
106}
107
108pub trait Skippable {
109 type Out;
110}
111impl<N> Skippable for (Empty, N) {
112 type Out = Empty;
113}
114impl<H, T> Skippable for (List<(H, T)>, U0) {
115 type Out = List<(H, T)>;
116}
117impl<H, T> Skippable for (List<(H, T)>, U1) {
118 type Out = T;
119}
120impl<H, T, U, Ba, Bb> Skippable for (List<(H, T)>, UInt<UInt<U, Ba>, Bb>)
121where
122 U: Unsigned,
123 Ba: Bit,
124 Bb: Bit,
125 UInt<UInt<U, Ba>, Bb>: Sub<U1>,
126 (T, <UInt<UInt<U, Ba>, Bb> as Sub<U1>>::Output): Skippable,
127{
128 type Out = <(T, <UInt<UInt<U, Ba>, Bb> as Sub<U1>>::Output) as Skippable>::Out;
129}
130
131type IntoOnes<T> = <(T, Ones) as Map<<T as Container>::Content, Ones>>::Out;
132pub type Len<T> = <IntoOnes<T> as Foldable<Addition>>::Out;
133pub type All<T> = <T as Foldable<Both>>::Out;
134pub type Any<T> = <T as Foldable<Either>>::Out;
135
136pub trait Indexed {
137 type Out;
138}
139impl<A, B> Indexed for (List<(A, B)>, U0) {
140 type Out = A;
141}
142impl<A, B, T, U> Indexed for (List<(A, B)>, UInt<U, T>)
143where
144 UInt<U, T>: Sub<U1>,
145 (B, <UInt<U, T> as Sub<U1>>::Output): Indexed,
146{
147 type Out = <(B, <UInt<U, T> as Sub<U1>>::Output) as Indexed>::Out;
148}
149
150pub trait Tailed {
151 type Tail;
152}
153impl<A, B> Tailed for List<(A, B)> {
154 type Tail = B;
155}
156
157pub type Empty = List<()>;
158pub struct List<T>(PhantomData<T>);
159impl Container for List<()> {
160 type Content = ();
161}
162impl<T, U> Container for List<(T, U)> {
163 type Content = T;
164}
165
166impl<T> Mempty for List<T> {
167 type Out = List<()>;
168}
169
170impl Mappend for (List<()>, List<()>) {
171 type Out = List<()>;
172}
173impl<A, B> Mappend for (List<()>, List<(A, B)>) {
174 type Out = List<(A, B)>;
175}
176impl<A, B> Mappend for (List<(A, B)>, List<()>) {
177 type Out = List<(A, B)>;
178}
179impl<A, B, C, D> Mappend for (List<(A, B)>, List<(C, D)>)
180where
181 (B, List<(C, D)>): Mappend,
182{
183 type Out = List<(A, <(B, List<(C, D)>) as Mappend>::Out)>;
184}
185
186impl<A, B, C, M> Map<A, M> for (List<(A, List<(B, C)>)>, M)
187where
188 M: Mapper<A> + Mapper<B>,
189 (List<(B, C)>, M): Map<B, M>,
190{
191 type Out = List<(<M as Mapper<A>>::Out, <(List<(B, C)>, M) as Map<B, M>>::Out)>;
192}
193impl<T, M> Map<T, M> for (List<(T, Empty)>, M)
194where
195 M: Mapper<T>,
196 (Empty, M): Map<(), M>,
197{
198 type Out = List<(<M as Mapper<T>>::Out, <(Empty, M) as Map<(), M>>::Out)>;
199}
200impl<M> Map<(), M> for (Empty, M) {
201 type Out = Empty;
202}
203
204impl<T> applicative::Pure<T> for T {
205 type Out = List<(T, Empty)>;
206}
207
208impl<T, U, M> Foldable<M> for List<(T, U)>
209where
210 U: Foldable<M>,
211 M: Monoid<T, <U as Foldable<M>>::Out>,
212{
213 type Out = <M as Monoid<T, <U as Foldable<M>>::Out>>::Mappend;
214}
215impl<M> Foldable<M> for Empty
216where
217 M: Mempty,
218{
219 type Out = <M as Mempty>::Out;
220}
221
222pub struct Ones;
223impl<T> Mapper<T> for Ones {
224 type Out = U1;
225}
226
227pub trait Reversible {
228 type Out;
229}
230impl Reversible for Empty {
231 type Out = Empty;
232}
233impl<T, U> Reversible for List<(T, U)>
234where
235 U: Reversible,
236 (<U as Reversible>::Out, List<(T, Empty)>): Mappend,
237{
238 type Out = <(<U as Reversible>::Out, List<(T, Empty)>) as Mappend>::Out;
239}
240pub type Rev<T> = <T as Reversible>::Out;
241
242pub trait Enumerable<N> {
243 type Out;
244}
245impl<N> Enumerable<N> for Empty {
246 type Out = Empty;
247}
248impl<T, U> Enumerable<U0> for List<(T, U)>
249where
250 U: Enumerable<U1>,
251 (
252 List<(List<(U0, List<(T, Empty)>)>, Empty)>,
253 <U as Enumerable<U1>>::Out,
254 ): Mappend,
255{
256 type Out = <(
257 List<(List<(U0, List<(T, Empty)>)>, Empty)>,
258 <U as Enumerable<U1>>::Out,
259 ) as Mappend>::Out;
260}
261impl<T, U, A, B> Enumerable<UInt<A, B>> for List<(T, U)>
262where
263 UInt<A, B>: Add<U1>,
264 U: Enumerable<<UInt<A, B> as Add<U1>>::Output>,
265 (
266 List<(List<(UInt<A, B>, List<(T, Empty)>)>, Empty)>,
267 <U as Enumerable<<UInt<A, B> as Add<U1>>::Output>>::Out,
268 ): Mappend,
269{
270 type Out = <(
271 List<(List<(UInt<A, B>, List<(T, Empty)>)>, Empty)>,
272 <U as Enumerable<<UInt<A, B> as Add<U1>>::Output>>::Out,
273 ) as Mappend>::Out;
274}
275pub type Enumerate<T> = <T as Enumerable<U0>>::Out;
276
277pub trait Zippable {
278 type Out;
279}
280impl Zippable for (Empty, Empty) {
281 type Out = Empty;
282}
283impl<T, U> Zippable for (Empty, List<(T, U)>) {
284 type Out = Empty;
285}
286impl<T, U> Zippable for (List<(T, U)>, Empty) {
287 type Out = Empty;
288}
289impl<A, B, T, U> Zippable for (List<(A, T)>, List<(B, U)>)
290where
291 (T, U): Zippable,
292 (
293 List<(List<(A, List<(B, Empty)>)>, Empty)>,
294 <(T, U) as Zippable>::Out,
295 ): Mappend,
296{
297 type Out = <(
298 List<(List<(A, List<(B, Empty)>)>, Empty)>,
299 <(T, U) as Zippable>::Out,
300 ) as Mappend>::Out;
301}
302pub type Zip<T, U> = <(T, U) as Zippable>::Out;
303
304#[cfg(test)]
305mod test {
306 use crate::dinosaurs::*;
307
308 use super::*;
309
310 use typenum::{U2, U3, U4, U5, U10, assert_type_eq};
311
312 #[test]
313 #[allow(unused)]
314 fn mappend() {
315 type Left = <(List<(U1, Empty)>, Empty) as Mappend>::Out;
316 type Right = <(Empty, List<(U0, Empty)>) as Mappend>::Out;
317 type Cat2 = <(Left, Right) as Mappend>::Out;
318 type HeadCat2 = Head<Cat2>;
319 assert_type_eq!(HeadCat2, U1);
320 type Last2 = <<Cat2 as Tailed>::Tail as Container>::Content;
321 assert_type_eq!(Last2, U0);
322
323 type Cat3 = <(List<(U2, Empty)>, Cat2) as Mappend>::Out;
324 assert_type_eq!(<Cat3 as Container>::Content, U2);
325 type Mid3 = <<Cat3 as Tailed>::Tail as Container>::Content;
326 assert_type_eq!(Mid3, U1);
327 type Last3 = <<<Cat3 as Tailed>::Tail as Tailed>::Tail as Container>::Content;
328 assert_type_eq!(Last3, U0);
329 type Merged = <(Cat3, Cat2) as Mappend>::Out;
330 type M0 = <Merged as Container>::Content;
331 assert_type_eq!(M0, U2);
332 type M1 = <<Merged as Tailed>::Tail as Container>::Content;
333 assert_type_eq!(M1, U1);
334 type M2 = <<<Merged as Tailed>::Tail as Tailed>::Tail as Container>::Content;
335 assert_type_eq!(M2, U0);
336 type M3 =
337 <<<<Merged as Tailed>::Tail as Tailed>::Tail as Tailed>::Tail as Container>::Content;
338 assert_type_eq!(M3, U1);
339 type M4 = <<<<<Merged as Tailed>::Tail as Tailed>::Tail as Tailed>::Tail as Tailed>::Tail as Container>::Content;
340 assert_type_eq!(M4, U0);
341 }
342
343 #[test]
344 #[allow(unused)]
345 fn map() {
346 type Dinos = list![Pterodactyl, Velociraptor, Stegosaurus];
347 type Mapped = <(Dinos, Ones) as Map<<Dinos as Container>::Content, Ones>>::Out;
348 type First = Idx<Mapped, U0>;
349 type Second = Idx<Mapped, U1>;
350 type Third = Idx<Mapped, U2>;
351 assert_type_eq!(First, U1);
352 assert_type_eq!(Second, U1);
353 assert_type_eq!(Third, U1);
354 }
355
356 #[test]
357 #[allow(unused)]
358 fn fold() {
359 type AList = list![U1, U1];
360 type Folded = <AList as Foldable<Addition>>::Out;
361 assert_type_eq!(Folded, U2);
362
363 type AnotherList = list![U1, U2, U3, U4];
364 type AnotherFold = <AnotherList as Foldable<Addition>>::Out;
365 assert_type_eq!(AnotherFold, U10);
366 }
367
368 #[test]
369 #[allow(unused)]
370 fn list_macro() {
371 type Both = list![U1, U0];
372 type Head2 = <Both as Container>::Content;
373 assert_type_eq!(Head2, U1);
374 type Last2 = <<Both as Tailed>::Tail as Container>::Content;
375 assert_type_eq!(Last2, U0);
376
377 type Three = list![U2, U1, U0];
378 type Head3 = <Three as Container>::Content;
379 assert_type_eq!(Head3, U2);
380 type Mid3 = <<Three as Tailed>::Tail as Container>::Content;
381 assert_type_eq!(Mid3, U1);
382
383 type Last3 = <<<Three as Tailed>::Tail as Tailed>::Tail as Container>::Content;
384 assert_type_eq!(Last3, U0);
385
386 type Moar = list![U2, U1, U0, U1, U0];
387 type M0 = <Moar as Container>::Content;
388 assert_type_eq!(M0, U2);
389 type M1 = <<Moar as Tailed>::Tail as Container>::Content;
390 assert_type_eq!(M1, U1);
391 type M2 = <<<Moar as Tailed>::Tail as Tailed>::Tail as Container>::Content;
392 assert_type_eq!(M2, U0);
393 type M3 =
394 <<<<Moar as Tailed>::Tail as Tailed>::Tail as Tailed>::Tail as Container>::Content;
395 assert_type_eq!(M3, U1);
396 type M4 = <<<<<Moar as Tailed>::Tail as Tailed>::Tail as Tailed>::Tail as Tailed>::Tail as Container>::Content;
397 assert_type_eq!(M4, U0);
398 }
399
400 #[test]
401 #[allow(unused)]
402 fn head() {
403 type Dinos = list![Stegosaurus, Triceratops, Diplodocus];
404 type H = Head<Dinos>;
405 assert_type_eq!(H, Stegosaurus);
406 }
407
408 #[test]
409 #[allow(unused)]
410 fn tail() {
411 type Dinos = list![
412 DaspletosaurusTorosus,
413 NanotyranosaurusLancensis,
414 TeratophoneusCurriei
415 ];
416 type T = Head<Tail<Dinos>>;
417 assert_type_eq!(T, NanotyranosaurusLancensis);
418 }
419
420 #[test]
421 #[allow(unused)]
422 fn idx() {
423 type Dinos = list![Microraptor, Oviraptor, Velociraptor, Herrerasaurus];
424 type A = Idx<Dinos, U0>;
425 type B = Idx<Dinos, U1>;
426 type C = Idx<Dinos, U2>;
427 type D = Idx<Dinos, U3>;
428
429 assert_type_eq!(A, Microraptor);
430 assert_type_eq!(B, Oviraptor);
431 assert_type_eq!(C, Velociraptor);
432 assert_type_eq!(D, Herrerasaurus);
433 }
434
435 #[test]
436 #[allow(unused)]
437 fn append() {
438 type HugeDinos = list![Megalosaurus, Gigantosaurus];
439 type Raptors = list![Velociraptor, Oviraptor, Microraptor];
440 type MergedFw = Append<Raptors, HugeDinos>;
441 type A1 = Idx<MergedFw, U0>;
442 type B1 = Idx<MergedFw, U1>;
443 type C1 = Idx<MergedFw, U2>;
444 type D1 = Idx<MergedFw, U3>;
445 type E1 = Idx<MergedFw, U4>;
446 assert_type_eq!(A1, Velociraptor);
447 assert_type_eq!(B1, Oviraptor);
448 assert_type_eq!(C1, Microraptor);
449 assert_type_eq!(D1, Megalosaurus);
450 assert_type_eq!(E1, Gigantosaurus);
451
452 type MergedRev = Append<HugeDinos, Raptors>;
453 type A2 = Idx<MergedRev, U0>;
454 type B2 = Idx<MergedRev, U1>;
455 type C2 = Idx<MergedRev, U2>;
456 type D2 = Idx<MergedRev, U3>;
457 type E2 = Idx<MergedRev, U4>;
458 assert_type_eq!(A2, Megalosaurus);
459 assert_type_eq!(B2, Gigantosaurus);
460 assert_type_eq!(C2, Velociraptor);
461 assert_type_eq!(D2, Oviraptor);
462 assert_type_eq!(E2, Microraptor);
463 }
464
465 #[test]
466 #[allow(unused)]
467 fn len() {
468 type HugeDinos = list![Megalosaurus, Gigantosaurus];
469 type Raptors = list![Velociraptor, Oviraptor, Microraptor];
470 type NumHuge = Len<HugeDinos>;
471 type NumRaptors = Len<Raptors>;
472 assert_type_eq!(NumHuge, U2);
473 assert_type_eq!(NumRaptors, U3);
474
475 type Dinos = Append<HugeDinos, Raptors>;
476 type NumDinos = Len<Dinos>;
477 assert_type_eq!(NumDinos, U5);
478 }
479
480 #[test]
481 #[allow(unused)]
482 fn rev() {
483 type Dinos = list![Stegosaurus, Triceratops, Pachycephalosaurus];
484 type RevList = Rev<Dinos>;
485 assert_type_eq!(Idx<RevList, U0>, Pachycephalosaurus);
486 assert_type_eq!(Idx<RevList, U1>, Triceratops);
487 assert_type_eq!(Idx<RevList, U2>, Stegosaurus);
488 assert_type_eq!(RevList, list![Pachycephalosaurus, Triceratops, Stegosaurus]);
489 }
490
491 #[test]
492 #[allow(unused)]
493 fn enumerate() {
494 type LongNeckDinos = list![Brachiosaurus, Brontosaurus, Diplodocus];
495 type Enumerated = Enumerate<LongNeckDinos>;
496 assert_type_eq!(Idx<Enumerated, U0>, list![U0, Brachiosaurus]);
497 assert_type_eq!(Idx<Enumerated, U1>, list![U1, Brontosaurus]);
498 assert_type_eq!(Idx<Enumerated, U2>, list![U2, Diplodocus]);
499 }
500
501 #[test]
502 #[allow(unused)]
503 fn zip() {
504 type LongNecks = list![Brachiosaurus, Brontosaurus, Diplodocus];
505 type Raptors = list![Microraptor, Oviraptor, Velociraptor];
506 type Zipped = Zip<LongNecks, Raptors>;
507 assert_type_eq!(Idx<Zipped, U0>, list![Brachiosaurus, Microraptor]);
508 assert_type_eq!(Idx<Zipped, U1>, list![Brontosaurus, Oviraptor]);
509 assert_type_eq!(Idx<Zipped, U2>, list![Diplodocus, Velociraptor]);
510 }
511
512 #[test]
513 #[allow(unused)]
514 fn skip() {
515 type Tyranosaurs = list![
516 TyranosaurusRex,
517 NanotyranosaurusLancensis,
518 DaspletosaurusTorosus,
519 NanuqsaurusHoglundi,
520 TeratophoneusCurriei
521 ];
522 assert_type_eq!(Skip<Tyranosaurs, U0>, Tyranosaurs);
523 assert_type_eq!(Skip<Tyranosaurs, U1>, list![NanotyranosaurusLancensis, DaspletosaurusTorosus, NanuqsaurusHoglundi, TeratophoneusCurriei]);
524 assert_type_eq!(Skip<Tyranosaurs, U2>, list![DaspletosaurusTorosus, NanuqsaurusHoglundi, TeratophoneusCurriei]);
525 assert_type_eq!(Skip<Tyranosaurs, U3>, list![NanuqsaurusHoglundi, TeratophoneusCurriei]);
526 assert_type_eq!(Skip<Tyranosaurs, U4>, list![TeratophoneusCurriei]);
527 assert_type_eq!(Skip<Tyranosaurs, U5>, Empty);
528 }
529
530 #[test]
531 #[allow(unused)]
532 fn take() {
533 type Tyranosaurs = list![
534 TyranosaurusRex,
535 NanotyranosaurusLancensis,
536 DaspletosaurusTorosus,
537 NanuqsaurusHoglundi,
538 TeratophoneusCurriei
539 ];
540 assert_type_eq!(Take<Tyranosaurs, U0>, Empty);
541 assert_type_eq!(Take<Tyranosaurs, U1>, list![TyranosaurusRex]);
542 assert_type_eq!(Take<Tyranosaurs, U2>, list![TyranosaurusRex, NanotyranosaurusLancensis]);
543 assert_type_eq!(Take<Tyranosaurs, U3>, list![TyranosaurusRex, NanotyranosaurusLancensis, DaspletosaurusTorosus]);
544 assert_type_eq!(Take<Tyranosaurs, U4>, list![TyranosaurusRex, NanotyranosaurusLancensis, DaspletosaurusTorosus, NanuqsaurusHoglundi]);
545 assert_type_eq!(Take<Tyranosaurs, U5>, Tyranosaurs);
546 }
547
548 #[test]
549 #[allow(unused)]
550 fn is_contained_by() {
551 type Numbers = list![U0, U1, U2];
552 assert_type_eq!(<(Numbers, U1) as IsContainedBy>::Out, True);
553 assert_type_eq!(<(Numbers, U4) as IsContainedBy>::Out, False);
554 }
555
556 #[test]
557 #[allow(unused)]
558 fn is_unique() {
559 type A = list![U0, U1, U2];
560 type B = list![U0, U0, U1, U2];
561 assert_type_eq!(<A as IsUnique>::Out, True);
562 assert_type_eq!(<B as IsUnique>::Out, False);
563 }
564}