slist/lib.rs
1#![no_std]
2#![warn(missing_docs)]
3//! s(tatic|tack)lists
4//! Experimental algebraic lists with with statically determined size that live on stack.
5//! They can be iterated over, mapped, folded, filtered and have continuous storage.
6//! `#![no_std]`, no const generics, no macros, no unsafe, no heap allocation nor boxing,
7//! no dynamic dispatch, no dependencies, no unstable code used for the implementation.
8//! Just the Rust trait system.
9//!
10//! Lists are constructed kind of like natural numbers in [Peano arithmetic](https://en.wikipedia.org/wiki/Peano_axioms).
11//! For example, the type of a list with 8 elements is
12//! ```
13//! # use slist::List;
14//! # type T = u8;
15//! let l: List<T, List<T, List<T, List<T, List<T, List<T, List<T, List<T, ()>>>>>>>>;
16//! ```
17//!
18//! When the list is filtered, the result can be an arbitrary sublist, so the returned
19//! type is a disjuncion of all lists smaller than the original:
20//! ```
21//! # use slist::{Either, List, Void};
22//! # type T = u8;
23//! let s: Either<List<T, List<T, List<T, List<T, List<T, List<T, List<T, List<T, ()>>>>>>>>, Either<List<T, List<T, List<T, List<T, List<T, List<T, List<T, ()>>>>>>>, Either<List<T, List<T, List<T, List<T, List<T, List<T, ()>>>>>>, Either<List<T, List<T, List<T, List<T, List<T, ()>>>>>, Either<List<T, List<T, List<T, List<T, ()>>>>, Either<List<T, List<T, List<T, ()>>>, Either<List<T, List<T, ()>>, Either<List<T, ()>, Either<(), Void>>>>>>>>>;
24//! ```
25//! Although very cumbersome to write, in the actual implementation, it has linear memory efficienncy and
26//! is only one tag longer than the original, which is as short as it can get, since the length is
27//! determined only on runtime. This way, computations can be performed on lists with variable but bounded length.
28//!
29//! `slist` macro can be used for quick list creation (the actual implementation contains no macros):
30//! ```
31//! use slist::prelude::*;
32//!
33//! let list = slist![0_usize, 3, 10, 19, 12, 22, 28, 13, 6].map(|i| i + 1);
34//! let filtered = list.filter(|u| (u % 2) == 0);
35//! assert_eq!(filtered + slist![3, 4, 5], slist![4, 20, 14, 3, 4, 5]);
36//! assert_eq!(slist![6, 7] * slist![false, true], slist![(6, false), (7, false), (6, true), (7, true)]);
37//!
38//! let mut list = slist![4, 5, 6];
39//! for i in list.as_mut() {
40//! *i += 2;
41//! }
42//! assert_eq!(list, slist![6, 7, 8]);
43//! ```
44//!
45//! Note that when provided with an expression and size, the `slist` macro evaluates the expression
46//! for each element separately. This is different to the array constructor (or the `vec` macro)
47//! and can be used to iteratively build bounded lists, like of numbers from the standard input:
48//! ```
49//! use slist::prelude::*;
50//! # use std::io::BufRead;
51//!
52//! let stdin = std::io::stdin();
53//! let mut inputs = stdin.lock().lines().filter_map(Result::ok).map(|s| s.parse::<u16>().ok());
54//!
55//! let list = slist![inputs.next().flatten(); 4];
56//! let list = list.filter_map(|i| i);
57//! ```
58//!
59//! The macros are only used for convenience and are not necessary for the library to function.
60//! For example, the preceding code gets expanded to:
61//! ```
62//! # use slist::prelude::*;
63//! # use std::io::BufRead;
64//! # let stdin = std::io::stdin();
65//! # let mut inputs = stdin.lock().lines().filter_map(Result::ok).map(|s| s.parse::<u16>().ok());
66//! let list = {
67//! use slist::List;
68//! let list: List<(), List<(), List<(), List<(), List<(), ()>>>>> = Default::default();
69//! list.map(|_| inputs.next().flatten())
70//! };
71//! ```
72//! If you prefer to write natural numbers in Peano form, there is no need for any macros at all.
73//!
74//! Unfortunately, until [generic associated types](https://github.com/rust-lang/rfcs/blob/master/text/1598-generic_associated_types.md)
75//! are stabilised, mapping of lists, resp. creating a list of references from a reference of a list
76//! need to be provided by separate traits, `SlistMap<T, U>`, resp. `SlistAsRef<'a, T>`.
77//! This crate provides a `prelude` module, from which every such trait can be conveniently imported.
78//!
79//! This crate can take a heavy toll on the compiler and using in in production can be adventurous.
80
81/// Implementation of addition and multiplication for lists.
82mod arithmetic;
83/// Implementation of equality traits for lists.
84mod eq;
85/// Implementation of iterators for lists.
86mod iter;
87/// A helper module, exporting all traits for convenient working with lists.
88pub mod prelude {
89 pub use crate::{slist, Slist, SlistAsRef, SlistFlatten, SlistMap, SlistReverse, SlistSum};
90}
91
92mod as_ref;
93mod flatten;
94mod map;
95mod reverse;
96
97pub use as_ref::SlistAsRef;
98pub use flatten::SlistFlatten;
99pub use map::SlistMap;
100pub use reverse::SlistReverse;
101pub use slist_derive::slist_typegen;
102
103use core::cmp::Ordering;
104use core::fmt::{self, Display, Formatter};
105use core::ops::{Add, Index, IndexMut};
106
107/// A trait representing static stack lists.
108pub trait Slist<T>: Sized {
109 /// The largest number of element the type can contain.
110 const MAXLEN: usize = 0;
111 /// A type that is returned when at least one element is filtered out
112 /// via the `filter` method.
113 type Filter;
114 /// Keep only the elements in the list that satisfy the given closure `f`.
115 /// The closure must return `true` or `false`. Only the elemets for which it returns
116 /// `true` are retained.
117 #[inline]
118 fn filter<F: FnMut(&T) -> bool>(self, _f: F) -> Either<Self, Self::Filter> {
119 Either::Left(self)
120 }
121 /// Apply the closure `f` on the list, producing a single, final value.
122 /// `foldr` takes 2 argumetst: an initial value (an `accumulator`) and a closure
123 /// that computes a new value of the accumulator from the old one and an element
124 /// of the list. After going through each element this way, the final value of the
125 /// accumulator is yielded.
126 /// This is the "right" variant of fold, meaning (in the `slist` conventions) that
127 /// the closure is applied on the elements "from left to right".
128 #[inline]
129 fn foldr<U, F: FnMut(U, T) -> U>(self, acc: U, _f: &mut F) -> U {
130 acc
131 }
132
133 /// Apply the closure `f` on the list, producing a single, final value.
134 /// `foldl` takes 2 arguments: an initial value (an `accumulator`) and a closure
135 /// that computes a new value of the accumulator from the old one and an element
136 /// of the list. After going through each element this way, the final value of the
137 /// accumulator is yielded.
138 /// This is the "left" variant of fold, meaning (in the `slist` conventions) that
139 /// the closure is applied on the elements "from right to left".
140 #[inline]
141 fn foldl<U, F: FnMut(U, T) -> U>(self, acc: U, _f: F) -> U {
142 acc
143 }
144
145 /// Run the closure `f` for each element of the list.
146 #[inline]
147 fn for_each<F: FnMut(T)>(self, _f: F) {}
148
149 /// Sum the elements of the list, for types that implement addition.
150 #[inline]
151 fn sum<U>(self) -> U
152 where
153 U: Add<T, Output = U> + Default,
154 {
155 self.foldl(U::default(), U::add)
156 }
157
158 /// Get a reference of the element at `index`, or return `None`
159 /// if `index` is out of the list.
160 #[inline]
161 fn get(&self, _index: usize) -> Option<&T> {
162 None
163 }
164
165 /// Get a mutable reference of the element at `index`, or return `None`
166 /// if `index` is out of the list.
167 #[inline]
168 fn get_mut(&mut self, _index: usize) -> Option<&mut T> {
169 None
170 }
171
172 /// Display elements of the list to the formatter. A convenience method for
173 /// implementing `Display` for list elements.
174 #[inline]
175 fn view(&self, _f: &mut Formatter<'_>) -> fmt::Result
176 where
177 T: Display,
178 {
179 Ok(())
180 }
181
182 /// Get the length of the list.
183 #[inline]
184 fn len(&self) -> usize {
185 Self::MAXLEN
186 }
187
188 /// Returns `true` if the list contains no elements, otherwise returns `false`.
189 #[inline]
190 fn is_empty(&self) -> bool {
191 true
192 }
193}
194
195/// A list type that contains an element of type `T` and another element, which is either another
196/// list type or unit (`()`).
197/// By convention, the given element is considered the last item on the list, although the compiler
198/// is free to rearrange the order as it feels.
199#[derive(Debug, Default)]
200pub struct List<T, N: Slist<T>> {
201 tail: N,
202 head: T,
203}
204
205/// A disjuncion of two possible values.
206/// By nesting of `Either`s, a disjuncion of lists of all lengths up to a certain bound
207/// is created.
208#[derive(Debug)]
209pub enum Either<N, M> {
210 /// Left variant
211 Left(N),
212 /// Right variant
213 Right(M),
214}
215
216/// A type that cannot have an actual value, thus cannot ever be constructed.
217#[derive(Debug)]
218pub enum Void {}
219
220impl<T> Slist<T> for Void {
221 type Filter = Void;
222}
223
224impl<T> Slist<T> for () {
225 type Filter = Void;
226}
227
228/// For soundness reasons, `Slist` should be implemented only for those lists that contain
229/// another lists.
230/// Although this cannot be ensured within the Rust trait system (another type may implement
231/// a public trait) without resorting to private modules, it is at least made sure that `Slist`
232/// is implemented only for those lists, whose `filter` function will return the `Either` variant
233/// containing the list itself if none of its items is filtered out.
234impl<T, N: Slist<T, Filter = S>, S: SlistSum<T, Next = N>> Slist<T> for List<T, N> {
235 const MAXLEN: usize = 1 + N::MAXLEN;
236
237 type Filter = Either<N, N::Filter>;
238
239 #[inline]
240 fn foldr<U, F: FnMut(U, T) -> U>(self, acc: U, f: &mut F) -> U {
241 let acc = self.tail.foldr(acc, f);
242 f(acc, self.head)
243 }
244
245 #[inline]
246 fn foldl<U, F: FnMut(U, T) -> U>(self, acc: U, mut f: F) -> U {
247 self.tail.foldl(f(acc, self.head), f)
248 }
249
250 #[inline]
251 fn filter<F: FnMut(&T) -> bool>(self, mut f: F) -> Either<Self, Self::Filter> {
252 let (head, tail) = self.pop();
253 if f(&head) {
254 tail.filter(f).push(head)
255 } else {
256 Either::Right(tail.filter(f))
257 }
258 }
259
260 #[inline]
261 fn for_each<F: FnMut(T)>(self, mut f: F) {
262 f(self.head);
263 self.tail.for_each(f);
264 }
265
266 #[inline]
267 fn get(&self, index: usize) -> Option<&T> {
268 match index.cmp(&(Self::MAXLEN - 1)) {
269 Ordering::Greater => None,
270 Ordering::Equal => Some(&self.head),
271 Ordering::Less => self.tail.get(index),
272 }
273 }
274
275 #[inline]
276 fn get_mut(&mut self, index: usize) -> Option<&mut T> {
277 match index.cmp(&(Self::MAXLEN - 1)) {
278 Ordering::Greater => None,
279 Ordering::Equal => Some(&mut self.head),
280 Ordering::Less => self.tail.get_mut(index),
281 }
282 }
283
284 #[inline]
285 fn view(&self, f: &mut Formatter<'_>) -> fmt::Result
286 where
287 T: Display,
288 {
289 self.tail.view(f)?;
290 write!(f, "{}, ", &self.head)
291 }
292
293 #[inline]
294 fn is_empty(&self) -> bool {
295 false
296 }
297}
298
299impl<T, N: Slist<T>, M: Slist<T>> Slist<T> for Either<N, M> {
300 const MAXLEN: usize = [N::MAXLEN, M::MAXLEN][(N::MAXLEN < M::MAXLEN) as usize];
301
302 type Filter = Either<N::Filter, M::Filter>;
303
304 #[inline]
305 fn foldr<U, F: FnMut(U, T) -> U>(self, acc: U, f: &mut F) -> U {
306 match self {
307 Either::Left(n) => n.foldr(acc, f),
308 Either::Right(m) => m.foldr(acc, f),
309 }
310 }
311
312 #[inline]
313 fn foldl<U, F: FnMut(U, T) -> U>(self, acc: U, f: F) -> U {
314 match self {
315 Either::Left(n) => n.foldl(acc, f),
316 Either::Right(m) => m.foldl(acc, f),
317 }
318 }
319
320 #[inline]
321 fn filter<F: FnMut(&T) -> bool>(self, f: F) -> Either<Self, Self::Filter> {
322 match self {
323 Either::Left(n) => match n.filter(f) {
324 Either::Left(l) => Either::Left(Either::Left(l)),
325 Either::Right(r) => Either::Right(Either::Left(r)),
326 },
327 Either::Right(m) => match m.filter(f) {
328 Either::Left(l) => Either::Left(Either::Right(l)),
329 Either::Right(r) => Either::Right(Either::Right(r)),
330 },
331 }
332 }
333
334 #[inline]
335 fn for_each<F: FnMut(T)>(self, f: F) {
336 match self {
337 Either::Left(n) => n.for_each(f),
338 Either::Right(m) => m.for_each(f),
339 }
340 }
341
342 #[inline]
343 fn get(&self, index: usize) -> Option<&T> {
344 match self {
345 Either::Left(n) => n.get(index),
346 Either::Right(m) => m.get(index),
347 }
348 }
349
350 #[inline]
351 fn get_mut(&mut self, index: usize) -> Option<&mut T> {
352 match self {
353 Either::Left(n) => n.get_mut(index),
354 Either::Right(m) => m.get_mut(index),
355 }
356 }
357
358 #[inline]
359 fn len(&self) -> usize {
360 match self {
361 Either::Left(n) => n.len(),
362 Either::Right(m) => m.len(),
363 }
364 }
365
366 #[inline]
367 fn is_empty(&self) -> bool {
368 match self {
369 Either::Left(n) => n.is_empty(),
370 Either::Right(m) => m.is_empty(),
371 }
372 }
373}
374
375/// A disjunction of all the list types of type `T`, up to a certain length.
376/// Used for implementing `filter` for lists.
377pub trait SlistSum<T>: Slist<T> {
378 /// The next list that is not in the disjunction.
379 /// The smallest list of type T that is larger than any of the lists in the current type.
380 type Next: Slist<T>;
381 /// Add another element to this list, possibly making it larger.
382 fn push(self, item: T) -> Either<Self::Next, Self>;
383}
384
385impl<T> SlistSum<T> for () {
386 type Next = List<T, ()>;
387
388 #[inline]
389 fn push(self, item: T) -> Either<Self::Next, ()> {
390 Either::Left(List::new(item))
391 }
392}
393
394impl<T> SlistSum<T> for Void {
395 type Next = ();
396
397 #[inline]
398 fn push(self, _: T) -> Either<Self::Next, Self> {
399 Either::Left(())
400 }
401}
402
403impl<T, N: Slist<T, Filter = S>, S: SlistSum<T, Next = N>> SlistSum<T> for Either<N, S> {
404 type Next = List<T, N>;
405
406 #[inline]
407 fn push(self, item: T) -> Either<Self::Next, Self> {
408 match self {
409 Either::Left(l) => Either::Left(List {
410 head: item,
411 tail: l,
412 }),
413 Either::Right(r) => Either::Right(r.push(item)),
414 }
415 }
416}
417
418impl<T> List<T, ()> {
419 /// Create a new list, containing one item.
420 #[inline]pub const
421 fn new(first: T) -> Self {
422 List {
423 head: first,
424 tail: (),
425 }
426 }
427}
428
429impl<T, N: Slist<T, Filter = S>, S: SlistSum<T, Next = N>> List<T, N> {
430 /// Push the `item` at the end of the list.
431 #[inline]pub
432 fn push(self, item: T) -> List<T, Self> {
433 List {
434 head: item,
435 tail: self,
436 }
437 }
438
439 /// "Tear" the list into a tuple, containing the last element and a list
440 /// consting of the rest of the original list.
441 #[inline]pub
442 fn pop(self) -> (T, N) {
443 (self.head, self.tail)
444 }
445}
446
447impl<T, N: Slist<T, Filter = S>, S: SlistSum<T, Next = N>> Index<usize> for List<T, N> {
448 type Output = T;
449 #[inline]
450 fn index(&self, index: usize) -> &T {
451 self.get(index).unwrap()
452 }
453}
454
455impl<T, N: Slist<T, Filter = S>, S: SlistSum<T, Next = N>> IndexMut<usize> for List<T, N> {
456 #[inline]
457 fn index_mut(&mut self, index: usize) -> &mut T {
458 self.get_mut(index).unwrap()
459 }
460}
461
462impl<T, N, M> Index<usize> for Either<N, M>
463where
464 N: Slist<T> + Index<usize, Output = T>,
465 M: Slist<T> + Index<usize, Output = T>,
466{
467 type Output = T;
468 #[inline]
469 fn index(&self, index: usize) -> &T {
470 match self {
471 Either::Left(n) => n.index(index),
472 Either::Right(m) => m.index(index),
473 }
474 }
475}
476
477impl<T, N, M> IndexMut<usize> for Either<N, M>
478where
479 N: Slist<T> + Index<usize, Output = T> + IndexMut<usize>,
480 M: Slist<T> + Index<usize, Output = T> + IndexMut<usize>,
481{
482 #[inline]
483 fn index_mut(&mut self, index: usize) -> &mut T {
484 match self {
485 Either::Left(n) => n.index_mut(index),
486 Either::Right(m) => m.index_mut(index),
487 }
488 }
489}
490
491impl<T: Display, N: Slist<T, Filter = S>, S: SlistSum<T, Next = N>> Display for List<T, N> {
492 #[inline]
493 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
494 write!(f, "[")?;
495 self.tail.view(f)?;
496 write!(f, "{}]", &self.head)
497 }
498}
499
500impl<N: Display, M: Display> Display for Either<N, M> {
501 #[inline]
502 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
503 match self {
504 Either::Left(n) => write!(f, "{}", &n),
505 Either::Right(m) => write!(f, "_{}", &m),
506 }
507 }
508}
509
510impl<T: Clone, N: Clone + Slist<T>> Clone for List<T, N> {
511 #[inline]
512 fn clone(&self) -> Self {
513 List {
514 head: self.head.clone(),
515 tail: self.tail.clone(),
516 }
517 }
518}
519
520impl<T: Copy, N: Copy + Slist<T>> Copy for List<T, N> {}
521
522impl<N: Clone, M: Clone> Clone for Either<M, N> {
523 #[inline]
524 fn clone(&self) -> Self {
525 match self {
526 Either::Left(n) => Either::Left(n.clone()),
527 Either::Right(m) => Either::Right(m.clone()),
528 }
529 }
530}
531
532impl<N: Copy, M: Copy> Copy for Either<N, M> {}
533
534impl<N, M: Default> Default for Either<N, M> {
535 #[inline]
536 fn default() -> Self {
537 Either::Right(M::default())
538 }
539}
540
541impl<N: Default> Default for Either<N, Void> {
542 #[inline]
543 fn default() -> Self {
544 Either::Left(Default::default())
545 }
546}
547
548/// Creates a list containing the arguments.
549///
550/// `slist!` allows the lists to be defined with the same syntax as array expressions.
551/// There are two forms of this macro:
552///
553/// - Create a list containing given elements:
554///
555/// ```
556/// # use slist::slist;
557/// let list = slist![1, 2, 3];
558/// assert_eq!(list[0], 1);
559/// assert_eq!(list[1], 2);
560/// assert_eq!(list[2], 3);
561/// ```
562///
563/// - Create a list from a given expression and size:
564///
565/// ```
566/// # use slist::slist;
567/// let list = slist![1; 3];
568/// assert_eq!(list, slist![1, 1, 1]);
569/// ```
570///
571/// Note that unlike array constructors and the `vec` macro, the given expression
572/// is evaluated for each element separately. This allows building the lists iteratively:
573/// ```
574/// use slist::prelude::*;
575///
576/// let mut i = 0;
577/// let mut f = || {
578/// i += 1;
579/// i
580/// };
581/// let list = slist![f(); 3];
582/// assert_eq!(list.reverse(), slist![1, 2, 3]);
583#[macro_export]
584macro_rules! slist {
585 ($s:expr $(, $x:expr)*) => (
586 $crate::List::new($s)$(.push($x))*
587 );
588 ($elem:expr; $n:expr) => (
589 {
590 use $crate::{slist_typegen, List, SlistMap};
591 let list: $crate::slist_typegen!($n) = Default::default();
592 list.map(|_| $elem)
593 }
594 );
595}