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
// Transducers -- A transducer library for Rust // Copyright 2014 Ruud van Asseldonk // // This program is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, version 3 of the License. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see <http://www.gnu.org/licenses/>. // TODO: Rich Hickey says: “If you’re trying to produce the next process N, you // _must_ supply the result of step N-1 as the input. If you’re trying to model // this in your type system saying R -> R, that’s _wrong_. Right? Because I can // call the step function five times, and then on the sixth time, take the // return value from the first time, and pass it as the first thing. That’s // wrong. So do you know how to make your type system make that wrong?” // // [Yes Mr Hickey, I do know how to make that wrong. Take R by value in the // step function. If you then put its result into the step function again, then // it has moved there, and you cannot return it any more. If R is not Copy, of // course.] // // Then he goes on about a state machine being a valid state, but a sum type is // wrong, because if X goes in, it is not X | Y | Z that comes out, it is // _always_ Y. // // I think this might need something like associated types? It can become quite // hairy to do it correctly, I think. For now, it is just R -> R. It is wrong. // I know. //! Transducers, a transducer library for Rust. //! //! TODO: Add some examples here. #![warn(missing_docs)] #![feature(fn_traits, unboxed_closures)] pub use compose::{compose, compose_trans}; pub use transform::{Filtering, Identity, Mapping}; mod compose; mod transform; /// An abstract tranformation/reduction of data. /// /// A transducer represents a transformation or reduction like `map`, `filter` /// or `fold`. It specifies how to manipulate the data, independent of the way /// in which that data might arrive. /// /// While the trait (and especially its implementations) may look scary at /// first, you rarely need to deal with this trait directly unless you intend /// to implement your own transformation/reduction functions that cannot be /// expressed as a composition of standard transducers. pub trait Transducer<'t, R, T, U> { /// The type of step that application of the transducer produces. type Step: Fn(R, U) -> R + 't; /// Applies the transducer to the step function to obtain a new step function. fn apply<Step: Fn(R, T) -> R + 't>(&self, step: Step) -> Self::Step; } /// Applies the `fold` reduction operation on `iter` transformed by `trans`. pub fn reduce_iter<'t, R, T, U, I: Iterator<Item = U>, Fold: Fn(R, T) -> R + 't, Trans: Transducer<'t, R, T, U>> (iter: I, seed: R, fold: Fold, trans: Trans) -> R where Trans::Step: 't { let step = trans.apply(fold); let mut state = seed; for t in iter { state = step(state, t); } state } #[test] fn reduce_iter_sum() { let items = [2, 3, 5, 7, 11, 13, 17, 19]; let sum = reduce_iter(items.iter(), 0, |a, x| a + x, Identity::new()); assert_eq!(sum, 77); // TODO: How to make this compile? // let is_even = |&x| x % 2 == 0; // let sum = reduce_iter(items.iter(), 0, |a, x| a + x, Filtering::new(&is_even)); // assert_eq!(sum, 75); } // NOTE: To create a Transduce trait, I think higher-ranked types would be required. // TODO: Transduce into an interator, do not collect immediately. // TODO: We use the size hint of the iterator, but even the min_sz could be an // overestimation due to a filtering transducer. /// Transduces the iterator `iter` with the transducer `trans`. /// /// This is an alternative to methods like `map` and `filter` in the standard /// library. /// /// ``` /// # use transducers::{transduce, Mapping}; /// let v = vec!(2i32, 3, 5, 7, 11); /// let f = |&x| x * 2; /// let v_trans = transduce(&mut v.iter(), Mapping::new(&f)); /// let v_map: Vec<i32> = v.iter().map(f).collect(); /// assert_eq!(v_trans, v_map); /// ``` pub fn transduce<'t, 'i, T: 't, U, I: Iterator<Item = U>, Step: Fn(Vec<T>, U) -> Vec<T>, Trans: Transducer<'t, Vec<T>, T, U, Step = Step>> (iter: &'i mut I, trans: Trans) -> Vec<T> where Trans::Step: 't { // The step function for a vector is simply append. fn append<TT>(mut r: Vec<TT>, t: TT) -> Vec<TT> { r.push(t); r } // Then we transduce the step function into the desired form. let step = trans.apply(append); // The result is obtained by performing a left fold of the step function. let (min_sz, _) = iter.size_hint(); let mut state = Vec::with_capacity(min_sz); for t in iter { state = step(state, t); } state } #[test] fn identity_is_identity_on_iter() { let v = vec!(2i32, 3, 5, 7, 11); let w = transduce(&mut v.clone().into_iter(), Identity::new()); assert_eq!(v, w); } #[test] fn mapping_on_iter() { let u = vec!(2i32, 3, 5, 7, 11); let v = u.clone(); let f = |x: &i32| *x * 2; let g = |x: i32| x * 2; let m = Mapping::new(&f); let n = Mapping::new(&g); let w = transduce(&mut u.iter(), m); let x = transduce(&mut v.into_iter(), n); assert_eq!(w, vec!(4i32, 6, 10, 14, 22)); assert_eq!(w, x); } #[test] fn filtering_on_iter() { let p = |x: &i32| *x % 2 == 0; let q = |x: &i32| *x % 3 != 0; let f = Filtering::new(&p); let h = Filtering::new(&q); let v = vec!(2i32, 3, 5, 6, 7, 11); let w = transduce(&mut v.iter().cloned(), f); let x = transduce(&mut v.iter().cloned(), h); assert_eq!(w, vec!(2i32, 6)); assert_eq!(x, vec!(2i32, 5, 7, 11)); } #[test] fn compose_mapping_filtering() { let f = |x: i32| x * 2; let p = |x: &i32| *x % 4 != 0; let t = compose_trans(Mapping::new(&f), Filtering::new(&p)); let v = vec!(2i32, 3, 4, 5, 6, 7, 11); let w = transduce(&mut v.into_iter(), t); assert_eq!(w, vec!(6i32, 10, 14, 22)); }